unique() 用于 javascript 中的数组

unique() for arrays in javascript

提问by maltalef

As everybody knows there's no built-in function to remove the duplicates from an array in javascript. I've noticed this is also lacking in jQuery (which has a unique function for DOM selections only), and the most common snippet I found checks the entire array and a subset of it for each element (not very efficient I think), like:

众所周知，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

so I made my own:

所以我自己做了：

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;
}

I wonder if there's any other algorithm accepted as the best for this case (or if you see any obvious flaw that could be fixed), or, what do you do when you need this in javascript (I'm aware that jQuery is not the only framework and some others may have this already covered).

我想知道是否有任何其他算法被认为是最适合这种情况的算法（或者您是否看到任何可以修复的明显缺陷），或者，当您在 javascript 中需要它时，您会怎么做（我知道 jQuery 不是只有框架和其他一些可能已经涵盖了这一点）。

回答by Justin Johnson

Using the object literal is exactly what I would do. A lotof people miss this technique a lotof the time, opting instead for typical array walks as the original code that you showed. The only optimization would be to avoid the arr.lengthlookup each time. Other than that, O(n) is about as good as you get for uniqueness and is much better than the original O(n^2) example.

使用对象字面量正是我会做的。 很多人错过这个技术有很多的时间，转而选择典型的阵列散步的原始代码，您呈现。唯一的优化是避免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

Time complexities to summarize

时间复杂度总结

  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

As with most algorithms, there are trade offs. If you are only sorting scalar values, you're modifications to the original algorithm give the most optimal solution. However, if you need to sort non-scalar values, then using or mimicking the uniqmethod of either of the libraries discussed would be your best choice.

与大多数算法一样，需要权衡取舍。如果您只是对标量值进行排序，则您对原始算法的修改会提供最佳解决方案。但是，如果您需要对非标量值进行排序，那么使用或模仿所uniq讨论的任一库的方法将是您的最佳选择。

回答by Fabien Ménager

I think your version won't work when you'll have objects or function in the array that give string representation like [Object object]. Because you can only have strings as keys in objects (in the "hash" object here). You'll need to loop into the result array to find if the new entry already exists. It will still be faster than the first method.

我认为当数组中的对象或函数提供像[Object object]. 因为您只能将字符串作为对象中的键（在此处的“散列”对象中）。您需要循环到结果数组中以查找新条目是否已存在。它仍然会比第一种方法更快。

Prototype JS has a "uniq" method, you may get inspiration from it.

Prototype JS 有一个“ uniq”方法，你可以从中得到启发。

回答by Manav

fun with fun (ctional)

有趣的乐趣（动作）

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

回答by jeremyosborne

I'm not an algorithm expert by any means, but I've been keeping an eye on underscore.js. They have this as a function called uniq:

我无论如何都不是算法专家，但我一直在关注 underscore.js。他们有一个叫做 uniq 的函数：

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

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

I looked at the code in their library, and copied it here for reference (not my code, this code belongs to underscore.js):

我查看了他们库中的代码，复制到这里供参考（不是我的代码，这段代码属于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;
    });
};

EDIT: You need to walk through the rest of the underscore.js code, and I almost took this code out because of it. I left the code snippet in just in case this was still useful.

编辑：您需要遍历 underscore.js 代码的其余部分，因此我差点把这段代码拿掉。我留下了代码片段以防万一这仍然有用。

回答by Rafa? Dowgird

Unfortunately JS objects have no identity accessible from the language - as other posters have mentioned, using objects as keys in a dictionary will fail when different objects have equal string representations and there is no id()function in the language.

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

There is a way to avoid the O(n^2) all-pairs check for ===identity if you can modify the objects. Pick a random string, walk the array once to check that no object has a property by that name, then just do arr[i][randomPropertyName]=1for each i. If the next object in the array already has that property, then it is a duplicate.

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

Unfortunately, the above will only work for modifiable objects. It fails for array values that don't allow property setting (e.g. integers, 42['random']=1just doesn't work :( )

不幸的是，以上仅适用于可修改的对象。对于不允许属性设置的数组值（例如整数，42['random']=1只是不起作用：()