Javascript - 更快的功能:线性列表搜索或获取对象值

Javascript - What's faster: a linear list search or getting an object value?

本文关键字：搜索 列表 获取 取对象 线性 功能 Javascript      更新时间：2023-09-26

考虑

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!')
  }
}

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

相关文章：