为什么 JavaScript 中 array.includes 比 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

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

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

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

编辑：我已经更新了测试以对结果进行洗牌，以免过多地导致提前停止array.includes()- 虽然不再慢 10 倍，但仍然慢很多倍，非常相关，并且超出了我的预期。

Answer 1

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

底层算法的时间复杂度仅在非常（非常）大的数字上才成为有意义的因素，并且根据经验，1000 肯定不是这么大的数字，特别是对于简单的整数值数组。

在少量的毫秒级操作中，您将在相似的时间范围内在引擎中发生许多其他事情，这将严重影响您的测量结果。优化、意外开销等等。

例如，我通过简单地将数组的大小增加到 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

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