在JavaScript中搜索数组地图的最有效方法

Question

我有一个JavaScript中的数字数组映射表。我的目标是获取包含某个数字的值的键。我也可以考虑使用不同的数据结构来提高效率。

let bookCategory = {
    "fantasy": [10064, 10066, 10071],
    "scifi": [10060, 10037, 10061],
    "history": [10001, 10003, 10004, 10005],
    "biography": [10032, 10006, 10002, 10028, 10009, 10030, 100031],
    "educational": [10025]
};

每个数字只会出现一次，但每个数组可以包含接近一百个数字，并且可能会有大量增长。由于我的数据是静态的，因此这些数组可以是不可变的。

目前我有以下代码，但它似乎并不高效。

let category;
let keys = _.keys(categories);
let theNumber = 10032;

for(let j = 0; j < keys.length; j++) {
    if(_.includes(categories[keys[j]], theNumber)) {
        category = keys[j];
        break;
    }
}

- diplosaurus

---

10001和300的输出应该是什么？ - Salvador Dali

@SalvadorDali 这些数字不在任何数组中，因此类别将保持“未定义”。 - diplosaurus

如果它们不同 - 创建一个从值到类别的映射。 - zerkms

一个数字可以属于多个类别吗？ - Nina Scholz

@NinaScholz 不是的。每个数字只会出现一次，如果有的话。 - diplosaurus

Answer 1

lodash库有很多有用的函数。使用它，您有以下选项：

1. 二分查找

创建一个新结构，其中包含排序后的数字数组。在查找数字时，应用二分查找。
_.sortedIndexOf()方法在数组中使用二分查找。

var bookCategory = {
 "fantasy": [10064, 10066, 10071],
 "scifi": [10060, 10037, 10061],
 "history": [10001, 10003, 10004, 10005],
 "biography": [10032, 10006, 10002, 10028, 10009, 10030, 100031],
 "educational": [10025]
};

var binaryMap = _.mapValues(bookCategory, function(category) {
  return category.sort(function(num1, num2) { 
    return num1 - num2; 
  });
});

//then search using binary algorithm    
var number = 10032;
var keyForNumber = _.findKey(binaryMap, function(numbers) {
  return _.sortedIndexOf(numbers, number) !== -1;
});

keyForNumber // prints "biography"

请查看工作中的演示。

2. 创建地图对象

由于数字只会出现一次，因此很容易创建一个大的哈希对象，其中键是数字，值是类别。它需要更多的内存，因为复制了类别字符串，但它运行得相当快。
这个解决方案不需要lodash。

var bookCategory = {
 "fantasy": [10064, 10066, 10071],
 "scifi": [10060, 10037, 10061],
 "history": [10001, 10003, 10004, 10005],
 "biography": [10032, 10006, 10002, 10028, 10009, 10030, 100031],
 "educational": [10025]
};

var map = _.reduce(bookCategory, function(result, numbers, key) {
  _.each(numbers, function(number) {
    result[number] = key;
  });
  return result;
}, {});

// or alternative without lodash
var mapAlternative = Object.keys(bookCategory).reduce(function(result, key) {
  bookCategory[key].forEach(function(number) {
    result[number] = key;
  });
  return result;
}, {});


var number = 10003;
map[number]; // prints "history"

检查工作中的 演示。

- Dmitri Pavlutin

---

Lodash对于第二个命题并不是必需的。 - oldergod

Answer 2

对数组进行排序并使用二分查找。您可以使用lodash库轻松完成。

- ramon.liu

---

排序难道不比简单地迭代查找答案花费更长时间吗？或者排序是比我想象中更快的操作。 - diplosaurus

@diplosaurus，我们不知道你在想什么。 - zerkms

Answer 3

我建议使用哈希表来处理这些数字。

var bookCategory = {
        "fantasy": [10064, 10066, 10071],
        "scifi": [10060, 10037, 10061],
        "history": [10001, 10003, 10004, 10005],
        "biography": [10032, 10006, 10002, 10028, 10009, 10030, 100031],
        "educational": [10025]
    },
    numbers = function (data) {
        var r = Object.create(null);
        Object.keys(data).forEach(k => data[k].forEach(a => r[a] = k));
        return r;
    }(bookCategory)

document.write('<pre>' + JSON.stringify(numbers, 0, 4) + '</pre>');

- Nina Scholz

Answer 4

回答那个问题有太多的“假设”，最大的一个是：数据会被更新和读取的频率是多少。

如果数据将更频繁地被读取，那么首先迭代遍历bookCategory并创建一个稀疏数组/对象，将数字链接回类别。

（我会选择对象）：

// Generate this programatticly, of course.
bookCategoryLinkback = {
    10064: "fantasy",
    10066: "fantasy",
    10071: "fantasy"
};

- Jeremy J Starcher

---

我的数组是完全静态的。如果我使用类似于“Immutable”的东西，我可以完全冻结它们。没有任何更新。 - diplosaurus

然后我会使用一个循环，类似于您所拥有的，并且只需创建一个新的反向引用对象，就像我上面展示的那样。 - Jeremy J Starcher