数组的性能包括映射到对象并在JavaScript中访问该对象

Question

根据CS的基本原理，未排序列表的search功能必须在O(n)时间内发生，而对于HashMaps，直接访问数组将在O(1)时间内发生。

那么，是将数组映射到字典，然后直接访问元素，还是应该只使用include？这个问题是专门针对JavaScript的，因为我相信这将归结到includes()和{}如何实现的核心实现细节。

let y = [1,2,3,4,5]
y.includes(3)

或者..。

let y = {
          1: true,
          2: true
          3: true
          4: true
          5: true
        }
5 in y

Answer 1

确实，对象查找是在固定时间内进行的- O(1) -因此使用对象属性而不是数组是一种选择，但如果您只是想检查集合中是否包含一个值，则使用Set会更合适，它是一个(通常是无序的)值集合，也可以在线性时间内查找。(使用普通对象将要求除了键之外还有值，这一点您并不关心-因此，请使用Set。)

​

const set = new Set(['foo', 'bar']);
console.log(set.has('foo'));
console.log(set.has('baz'));

​

当您必须查找同一Set的多个值时，这将非常有用。但是，向Set添加项(就像向对象添加属性一样)是O(N)，所以如果只查找单个值，那么这一点和对象技术都没有好处，还不如使用数组includes测试。

Answer 2

更新于2020年4月29日

正如评论者正确地指出的那样，看起来V8正在优化包含调用的数组。分配给var并使用它的An updated version会产生更多预期的结果。在这种情况下，Object address最快，其次是Set has，排在第三位的是Array includes (在我的系统/浏览器上)。

尽管如此，我仍然坚持我最初的观点，即如果进行微优化，那么就值得测试假设。只需确保您的测试是有效的;)

原始

井。尽管人们明显期望Object address和Set has应该优于Array includes，但针对Chrome的基准测试表明，实现胜过了预期。

在我运行的长椅上，Chrome Array includes无疑是表现最好的。

我还在本地使用Node进行了测试，并获得了更多预期结果。在对象地址wins中，紧随其后的是Set has，那么数组includes比两者都要慢一些。

底线是，如果您正在进行微优化(不建议这样做)，则值得进行基准测试，而不是假设哪种优化最适合您的特定情况。正如你的问题所暗示的，最终归结到实现上。因此，针对目标平台进行优化是关键。

这是我得到的结果：：

节点(12.6.0)：

ops for Object address 7804199
ops for Array includes 5200197
ops for Set has        7178483

Chrome (75.0)：

https://jsbench.me/myjyq4ixs1/1

​

​