javascript - Javascript - 更快：线性列表搜索或获取对象值？

Question

考虑

a = ['1','2','3','4','5']
for(var i = 0; i < a.length; i++) { if (a[i] == 3) console.log('found it!') }

和

a = {'1': true, '2': true, '3': true, '4': true}
a['3']

哪个会更快，为什么？

score 5 · Accepted Answer

在尝试查找随机元素时，对象查找平均会快得多，尤其是在您搜索大量项目时。这是因为这样做的底层算法是B 树搜索，其时间复杂度为 O(log n)，并允许它快速查找项目成员资格，而无需针对对象中的每个元素进行检查。

这与在数组中搜索时相反，您必须在确定是否不在具有 O(n) 线性时间复杂度的数组之前检查每个元素。

这是显示对象查找速度更快的基准：http: //jsperf.com/array-vs-objv2/6

score 2 · Accepted Answer

在比较它们在 jsPerf http://jsperf.com/array-vs-objv2中的性能之前，我修改了如下代码以使这两个代码等效

测试1：

测试设置：

var a = [];
var b = {};

for (var i = 1; i <= 100000; i++) {
   a.push(i);
   b[''+i] = true;
}

使用数组：

for(var i = 0; i < a.length; i++) { 
  if (a[i] === 99999) {
     console.log(true);
     return;
  }
}

使用对象：（更快）

console.log(b['99999']);

测试 2：

使用数组：（更快）

a = ['1','2','3','4','5']
for(var i = 0; i < a.length; i++) { 
  if (a[i] === 3) {
     console.log(true);
     return;
  }
}

使用对象：

a = {'1': true, '2': true, '3': true, '4': true, '5': true};
console.log(a['3']);

结果：（正如特雷弗指出的那样）数组搜索对于较少的项目会更快，但是在查找更大的列表时..由于线性搜索，数组会更慢。

score 2 · Accepted Answer

在不了解 JavaScript 的所有黑魔法工作原理的情况下，我可以说类似的东西a['3']不使用线性搜索。

JavaScript 是否直接引用了该元素，因此它甚至不需要进行搜索？也许。如果确实如此，它会使用它来a['3']比线性搜索更快地找到，即使它可能会花费更多的内存。（我认为这就是它的实际作用。）

如果没有，它实际上会搜索您的数据结构，几乎可以肯定它不使用简单的线性搜索。可能有一些内部工作，或者某种二叉树搜索或其他一些混乱。

score 1 · Accepted Answer

关联数组将执行得更快，它只需要一个逻辑操作。尽管要实现这一点，它需要更多地存储在内存中以将键与值链接起来。这大致相当于哈希表与数组参数。

缺点，较慢的插入和较高的内存使用。查找的速度取决于引擎。

设置和搜索的完整分析：http: //jsperf.com/array-vs-objv2/5

score 1 · Accepted Answer

看看这个基准图

对象属性和数组项的访问时间接近

在您的第一种情况下，有 3 次访问数组项

在第二种情况下，只有一次访问对象属性

所以我认为第二个应该更快

score 0 · Accepted Answer

a = {'1': true, '2': true, '3': true, '4': true}
if (a['3'] === true) {
  console.log("found it");
}

在大多数情况下会更快，然后

a = ['1','2','3','4','5']
for(var i = 0; i < a.length; i++) { 
  if (a[i] == 3) {
    console.log('found it!')
  }
}

因为第二个可能需要遍历数组的所有值。

6 回答 6