javascript - 是否值得将数组转换为集合以在 NodeJS 中进行搜索

Question

我想知道是否值得将数组转换为集合以便使用 NodeJS 进行搜索。

我的用例是这种搜索进行了很多次，但在大数据集上不是必需的(有时可以在数组中增加约 2000 个项目)。

在列表中寻找特定的 ID。

哪种方法更好:

const isPresent = (myArray, id) => {
   return Boolean(myArray.some((arrayElement) => arrayElement.id === id);
}

或

const mySet = new Set(myArray)
const isPresent = (mySet, id) => {
   return mySet.has(id);
}

我知道理论上第二种方法更好，因为第一种方法的复杂度为 O(1) 和 O(n)。但是集合的实例化能否抵消小型阵列的增益？

Answer 1

@jonrsharpe - 特别是对于您的情况，我发现将 2k 的数组转换为 Set 本身需要 ~1.15ms。毫无疑问，搜索 Set 比 Array 更快，但在您的情况下，这种额外的转换可能成本不高。

您可以在浏览器控制台中运行以下代码进行检查。 new Set(arr) 大约需要 ~1.2ms

var  arr = [], set = new Set(), n = 2000;
for (let i = 0; i < n; i++) {
  arr.push(i);
};

console.time('Set'); 
set = new Set(arr);
console.timeEnd('Set');

在 Set 中添加元素总是代价高昂的。下面的代码显示了在数组/集合中插入一个项目所需的时间。这表明 Array 插入比 Set 快。

var  arr = [], set = new Set(), n = 2000;
console.time('Array'); 
for (let i = 0; i < n; i++) {
  arr.push(i);  
};
console.timeEnd('Array');

console.time('Set'); 
for (let i = 0; i < n; i++) {
  set.add(i);  
};
console.timeEnd('Set');

我运行以下代码来分析在数组和集合中定位元素的速度。发现set比array快8-10倍。

您可以将此代码复制粘贴到您的浏览器中以进一步分析

var arr = [], set = new Set(), n = 100000;
for (let i = 0; i < n; i++) {
  arr.push(i);
  set.add(i);
}

var result;
console.time('Array'); 
result = arr.indexOf(12313) !== -1; 
console.timeEnd('Array');
console.time('Set'); 
result = set.has(12313); 
console.timeEnd('Set');

所以对于你的情况 array.some 更好!