javascript - 具有唯一值的数组 : indexOf vs new Set

Question

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

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 更改我的代码。如果不是，为什么？

Answer 1

"Is the indexOf what's making the option 1 slower?"

是的。 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) 并且 Array.from 是 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)。

Another question: if option 1 is faster, should I change my code from option 1 => option 2. If not, why?

选项 1 并不快，但如果我们假装它是那么答案是视情况而定。选项 1 肯定不会像选项 2 那样扩展，但这并不意味着选项 1 对于足够小的阵列可能不会更快(尽管我对此表示怀疑)。无论哪种方式，这都是过早的优化。如果您的代码运行缓慢，并且您分析了您的代码并将这 部分确定为瓶颈，那么您应该担心它。

编辑:

Small typo, I meant if option 2 is faster. There are no bottlenecks,

因此，关于过早优化的相同论点仍然适用。但就个人而言，我可能会改变它。它的影响似乎相当小，如果有的话，可以说，它可能对选项 2 有更清晰的意图。

虽然 - 请考虑浏览器对 Set 的支持。它相对较新，不被旧浏览器支持。 See here .