为什么在Java脚本中，array.includes比set.has快一个数量级？ [英] Why is array.includes an order of magnitude faster than set.has in javascript?

问题描述

我是在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

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

可以预见，动态创建集合的版本比直接测试包含数组的速度要慢。(虽然我想知道为什么Chrome不对数组进行JIT优化--我也测试过使用文字数组和文字数组，而使用变量在速度上根本不重要)。 然而，即使是预构造集也比数组包含测试慢一个数量级：即使是在最负面的情况下(条目不在数组内)。

为什么会这样？发生了什么黑魔法？

编辑：我已经更新了测试以混洗结果，以便不会太偏离array.includes()的早期停止-虽然不再慢10倍，但它仍然慢了许多倍，非常相关，超出了我的预期。

推荐答案

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

底层算法的时间复杂性仅在非常(非常)大的数字上成为一个有意义的因素，根据经验，1000肯定不是一个很大的数字，特别是对于一个简单的整数值数组。

在少量毫秒时间的操作中，您将在引擎中以类似的时间尺度发生许多其他事情，这将使您的测量结果严重偏离。优化、意外管理费用等。

例如，Iedited 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

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

这篇关于为什么在Java脚本中，array.includes比set.has快一个数量级？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！