具有唯一值的数组：indexOf vs new Set

Question

具有唯一值的数组：indexOf vs new Set

4

假设我们有一个包含重复项的数组，如下所示：

var items = ['a', 'd', 'e', 'b', 'c', 'd', 'e', 'f', 'g', 'd', 'f', 'g', 'd', 'j', 'k', 'l', 'd', 'e', 'c', 'd', 'e', 'f', 'g', 'd','c', 'd', 'e', 'f', 'g', 'd'];

如果您必须循环遍历项（可能没有意义，但这是场景要求），那么最快的方法是创建一个新数组并将值存入其中。

选项1：

var list = [];
items.forEach(function(item) {
    if(list.indexOf(item) == -1)
      list.push(item);
});

选项2：

var list = [];
items.forEach(function(item) {
    list.push(item);
});

list = Array.from(new Set(list));

我已经使用 console.time 进行了一些测试，结果显示选项2比选项1快5倍。但我不确定这个console.time有多可靠。

有什么见解？是indexOf使选项1变慢吗？

Fiddle: https://jsfiddle.net/q9opqvsm/

编辑：另一个问题：如果选项2更快，我应该将代码从选项1改为选项2吗？如果不是，为什么？

- yBrodsky

5

在你的第二个例子中，为什么要迭代items并将所有元素都推入到list中? 为什么不直接使用 list = Array.from(new Set(items));呢？ - Matt Burland

indexOf，我认为会遍历整个数组，这样你就要多做一些工作。集合（Set）使用哈希来确定元素是否已经存在，因此查找时间复杂度为O(1)。另外，你不需要遍历数组，只需使用Array.from(new Set(items))即可。 - Cruiser

@Matt Burland 这就是情景。可能没有意义，这只是某个更大事物的简化版本。 - yBrodsky

“indexOf是导致选项1变慢的原因吗？” - 是的。indexOf是O(n)，这意味着您在循环内部有一个循环，从而使您的总体复杂度为O(n2)。在选项2中，在集合中查找值是O(1)，而Array.from是O(n)，因此您的总体复杂度为O(n)。 - Matt Burland

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matt Burland · Accepted Answer

“indexOf” 是导致选项1变慢的原因吗？是的，“indexOf”的时间复杂度为O(n)，这意味着您在循环中有一个嵌套循环，总体时间复杂度为O(n2)。使用“indexOf”相当于执行以下操作：

function indexOf(item, array) {
    for (var i=0; i < array.length; i++) {
        if (array[i] === item) {
            return true;
        }
    }
    return false;
}

您可以看到，在最坏的情况下（该项尚未在数组中），必须遍历整个数组。这是无法避免的。如果您正在搜索数组中的值，则必须查看每个项目，直到找到它或没有项目可用。

在选项2中，在集合中查找值的时间复杂度为O(1)，而从数组创建新数组的时间复杂度为O(n)，因此总时间复杂度为O(n)。

创建一个集合与执行以下操作有些相似（请注意，这实际上并不会产生一个集合，而是一个对象，因此并不完全相同）：

function makeSet(array) {
    var set = {};
    for (var i=0; i < array.length; i++) {
        if (set[array[i]] === undefined) {   // indexing `set` is O(1)
            set[array[i]] = true;
        }
    }
}

所以它的时间复杂度是O(n)。从中创建一个数组只需要遍历集合并将其加载到数组中，这也是O(n)。因此总体上是O(n)。

另一个问题：如果选项1更快，我应该将代码从选项1更改为选项2吗？如果不是，为什么？

选项1不会更快，但是如果我们假装它更快，那么答案就是取决于情况。选项1肯定不会像选项2一样扩展得那么好，但这并不意味着选项1对于足够小的数组可能不会更快（尽管我很怀疑）。无论哪种方式，这都是过早优化。如果您的代码运行缓慢，并且您分析了代码并确定了此部分作为瓶颈，那么您应该担心它。

编辑：

有个小错别字，我是指如果选项2更快。没有瓶颈，

因此，有关过早优化的相同论点仍然适用。但是就个人而言，我可能会进行更改。它似乎影响不大，如果有任何影响，可能会因选项2具有更清晰的意图而更好。

虽然 - 请考虑浏览器对Set的支持。它相对较新，不受旧版浏览器的支持。在这里查看。