JavaScript中用于数组的unique()函数

Question

众所周知，在 JavaScript 中没有内置函数可以删除数组中的重复项。我注意到在 jQuery 中也缺少这种功能（它仅为 DOM 选择提供了唯一的函数），而我发现最常见的代码片段会为每个元素检查整个数组和其子集（我认为不太有效率），如下所示:

for (var i = 0; i < arr.length; i++)
    for (var j = i + 1; j < arr.length; j++)
        if (arr[i] === arr[j])
            //whatever

所以我自己制作了一个：

function unique (arr) {
    var hash = {}, result = [];
    for (var i = 0; i < arr.length; i++)
        if (!(arr[i] in hash)) { //it works with objects! in FF, at least
            hash[arr[i]] = true;
            result.push(arr[i]);
        }
    return result;
}

我想知道是否有其他算法被接受为这种情况的最佳算法（或者是否存在明显的缺陷可以修复），或者当您需要在JavaScript中使用此功能时应该怎么做（我知道jQuery不是唯一的框架，其他一些可能已经具备了此功能）。

- maltalef

---

这些数组只包含标量值，还是有可能包含对象和数组？ - Justin Johnson

还有假设已排序或未排序的假设吗？ - Justin Johnson

Answer 1

使用对象字面量正是我会做的。 很多 人经常错过这种技巧，而选择像你展示的代码一样典型的数组遍历方法。唯一的优化是避免每次查找 arr.length。除此之外，O(n) 大约是你可以得到的最好的去重方法，比原来的 O(n^2) 的例子要好得多。

function unique(arr) {
    var hash = {}, result = [];
    for ( var i = 0, l = arr.length; i < l; ++i ) {
        if ( !hash.hasOwnProperty(arr[i]) ) { //it works with objects! in FF, at least
            hash[ arr[i] ] = true;
            result.push(arr[i]);
        }
    }
    return result;
}

// * Edited to use hasOwnProperty per comments

时间复杂度总结

  f()    | unsorted | sorted | objects | scalar | library
____________________________________________________________
unique   |   O(n)   |  O(n)  |   no    |  yes   |    n/a
original |  O(n^2)  | O(n^2) |   yes   |  yes   |    n/a
uniq     |  O(n^2)  |  O(n)  |   yes   |  yes   | Prototype
_.uniq   |  O(n^2)  |  O(n)  |   yes   |  yes   | Underscore

与大多数算法一样，需要权衡取舍。如果您只需要对标量值进行排序，则修改原始算法会得到最优解。然而，如果您需要对非标量值进行排序，则使用或模仿讨论的任何一个库的 uniq 方法是最佳选择。

- Justin Johnson

---

最好使用 hash.hasOwnProperty(arr[i])。in 运算符会返回继承的属性，比如 toString。例如 ("toString" in {}) => true。 - Chetan S

对于已排序的列表，unique函数的时间复杂度也是O(n)吗？ - Xavi

抱歉，是的。复制粘贴让我失误了。 - Justin Johnson

根据这个答案回答的另一个问题，使用result[result.length] = arr[i];可能比push()更好。 - Tobbe

这是完全有效的，但这只是微小的优化。我们在这里考虑的优化是关于复杂度的级别。 - Justin Johnson

Answer 2

玩转函数式编程

function uniqueNum(arr) {
    return Object.keys(arr.reduce(
        function(o, x) {o[x]=1; return o;}, {})).map(Number);
}  

- Manav

Answer 3

我认为当数组中有对象或函数提供字符串表示时，你的版本将无法工作，例如[Object object]。因为在对象中只能使用字符串作为键（在这里是“哈希”对象）。您需要循环遍历结果数组以查找新条目是否已存在。它仍然比第一种方法快。

Prototype JS拥有一个“uniq”方法，您可以从中获得灵感。

- Fabien Ménager

---

好的观点，我没有考虑到toString问题。 - Justin Johnson

第一种方法也不能用于对象，如果我理解正确的话。IOW === 在对象上不起作用。所以假设数组只包含可以直接使用==或===进行比较的“标量”（例如整数、浮点数、布尔值、字符串），你还认为第二种方法行不通吗？ - Roatin Marth

嗯，等等。我想在对象引用上“==”也可以正常工作。那就算了！ - Roatin Marth

所有被比较的对象都将被视为相等，这在第一种方法中是错误的。但是如果数组只包含标量值，则第二种方法将起作用并且速度会更快。 - Fabien Ménager

Fabien：总的来说，第一个在一般情况下更好，而第二个在“标量”情况下更好。 - Roatin Marth

我查看了Prototype的代码，它的实现与Underscore相同，对于已排序的数组，时间复杂度为O(n)，对于未排序的数组，时间复杂度为O(n^2)。 - Justin Johnson

Answer 4

我并不是算法专家，但我一直关注underscore.js。他们将此作为一个名为uniq的函数：

http://documentcloud.github.com/underscore/#uniq

我查看了他们库中的代码，并在此引用（这不是我的代码，这段代码属于underscore.js）：

// Produce a duplicate-free version of the array. If the array has already
// been sorted, you have the option of using a faster algorithm.
_.uniq = function(array, isSorted) {
    return _.reduce(array, [], function(memo, el, i) {
        if (0 == i || (isSorted === true ? _.last(memo) != el : !_.include(memo, el))) memo.push(el);
        return memo;
    });
};

编辑：您需要浏览其余的underscore.js代码，我几乎因此将此代码删除。我仍然保留了代码片段，以防这仍然有用。

- jeremyosborne

---

我确定！_.include 也会从头开始迭代数组。 - Roatin Marth

我之前没有听说过这个库，所以我浏览了一下代码，特别是看了 _.include 和 _.last。看起来排序数组的时间复杂度为 O(n)，而未排序的则为 O(n^2)，因此它并没有带来恒定的改进。 - Justin Johnson

Justin：偵查得好。OP的程式碼樣本（第一個）似乎假設陣列已經排序。它從當前索引+1開始內部迴圈。 - Roatin Marth

结果证明，这是以与原型实现uniq相同的方式实现的。 - Justin Johnson

Answer 5

不幸的是，JS对象没有从语言中访问的标识 - 正如其他帖子所提到的，当不同的对象具有相等的字符串表示并且语言中没有id()函数时，在字典中使用对象作为键将失败。

如果您可以修改对象，则有一种方法可以避免O(n^2)所有对===身份的检查。选择一个随机字符串，遍历数组一次以检查是否有对象具有该名称的属性，然后只需为每个i执行arr[i][randomPropertyName]=1。如果数组中的下一个对象已经具有该属性，则它是重复的。

不幸的是，上述方法仅适用于可修改的对象。对于不允许属性设置的数组值（例如整数，42['random']=1就行不通 :( ）

- Rafał Dowgird