为什么 array.includes 比 javascript 中的 set.has 快一个数量级？

Question

我是在 C++ 中长大的，所以我总是很清楚什么算法适合什么。因此，当我注意到应用程序开始在手机上运行缓慢时，我立即开始研究数据结构及其表示方式。

我注意到一个非常奇怪的效果 Array.includes 比 Set.has 快一个数量级。尽管 Set.has 更有可能针对查找进行优化：这是使用集合的全部想法。

我的初始化代码是（这段代码在测试时间之外）：

function shuffle(a) {
    for (let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [a[i], a[j]] = [a[j], a[i]];
    }
}

const arr = []
for (let i = 0; i < 1000; i+=1) {
    arr.push(i);
};

shuffle(arr);
const prebuildset=new Set(arr);

测试是：

(new Set(arr)).has(-1); //20.0 kOps/s
arr.includes(-1); //632 kOps/s
(new Set(arr)).has(0); //20.0 kOps/s
arr.includes(0); //720 kOps/s
prebuildset.has(-1); //76.7 kOps/s
prebuildset.has(0); //107 kOps/s

使用 chrome 73.0.3683.103 在 Ubuntu 18.04 上使用 https://jsperf.com/set-array-has-test/1

进行了测试

我可以预期动态创建集合的版本比直接测试包含的数组要慢。（虽然我想知道为什么 chrome 不 JIT 优化数组 - 我还测试了使用文字数组和文字数组与使用变量在速度上根本无关紧要）。然而，即使是预构建集也比数组包含测试慢一个数量级：即使是最负面的情况（条目不在数组内）。

这是为什么？发生了什么黑魔法？

编辑：我已经更新了测试以打乱结果，以免过分偏向提前停止 array.includes()- 虽然不再慢 10 倍，但仍然慢很多倍，非常相关且超出我的预期。

Answer 1

首先我要声明我不是 JavaScript 引擎实现和性能优化方面的专家；但总的来说，您不应该相信这些测试可以为您提供可靠的性能评估。

基础算法的时间复杂度仅在非常（非常）大的数字上成为一个有意义的因素，根据经验，1000 肯定不是一个大数字，尤其是对于一个简单的整数值数组。

在少量的毫秒计时操作中，您将在引擎中以类似的时间尺度发生许多其他事情，这将使您的测量结果大打折扣。优化、意外开销等。

例如，我 edited your tests 通过简单地将数组的大小增加到 100,000。我可怜的旧笔记本电脑上的结果如下所示：

arr.includes(-1); //3,323 Ops/s
arr.includes(0); //6,132 Ops/s
prebuildset.has(-1); //41,923,084 Ops/s
prebuildset.has(0); //39,613,278 Ops/s

这显然与您的结果大相径庭。我的观点是，不要试图衡量小任务的微观性能。使用对你的项目最有意义的数据结构，保持你的代码干净合理，如果你需要扩展，相应地准备。

为什么 array.includes 比 javascript 中的 set.has 快一个数量级？

Why is array.includes an order of magnitude faster than set.has in javascript?

javascript

lookup

performance