考虑
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']
哪个会更快,为什么?
尝试查找随机元素时,对象查找平均会快得多,尤其是在搜索大量项目时。这是因为这样做的底层算法是 B 树搜索,其时间复杂度为 O(log n),并允许它快速查找项目成员资格,而无需根据对象中的每个元素进行检查。
这与在数组中搜索时相反,您必须检查每个元素,然后再决定是否不在线性时间复杂度为 O(n) 的数组中。
以下是显示对象查找速度更快的基准测试: http://jsperf.com/array-vs-objv2/6
我像下面这样修改了代码,使两个代码等效,然后再比较它们在 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']);
Resut:(正如特雷弗指出的那样)对于更少的项目,数组搜索会更快,但是当查找更大的列表时。由于线性搜索,数组速度较慢。
在不了解 JavaScript 的所有黑魔法工作原理的情况下,我可以说像 a['3']
这样的东西不使用线性搜索。
JavaScript 是否直接引用了该元素,因此它甚至不需要进行搜索?或。如果是这样,它会使用它来查找a['3']
比线性搜索更快,即使它可能花费更多的内存。(我认为这就是它的实际作用。
如果没有,它实际上会搜索您的数据结构,几乎可以肯定它不会使用简单的线性搜索。可能有一些内部工作原理,或者某种二叉树搜索或其他一些混淆。
查看此基准图
对象属性和数组项的访问时间接近
在第一种情况下,对数组项有三次访问
在第二种情况下,只有一次访问对象属性
所以我认为第二个应该更快
关联数组的执行速度会更快,它只需要一个逻辑操作。尽管要实现这一点,它需要在内存中存储更多以将键与值链接。这大致相当于哈希表与数组参数。
缺点,插入速度较慢,内存使用量较高。查找速度取决于引擎。
https://developers.google.com/v8/design
对设置和搜索进行全面分析:http://jsperf.com/array-vs-objv2/5
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!')
}
}
因为第二个可能需要遍历数组的所有值。