js如何实现高效的数组去重

Question

一般来说是建立一个哈希表，类似这样

var arr = [1, 2, 2, 3, 4, 5, 6, 6];

function getArray(a) {
 var hash = {},
     len = a.length,
     result = [];

 for (var i = 0; i < len; i++){
     if (!hash[a[i]]){
         hash[a[i]] = true;
         result.push(a[i]);
     } 
 }
 return result;
}

getArray(arr); // 输出[1， 2， 3， 4， 5， 6]

里面有对对象属性的查询，这个性能肯定不是最好的，所以问对js来说是否还有更加高效？

Answer 1

我对4种库进行了测试：

• 楼主的提供的
• google closure的goog.array.removeDuplicates
• Sizzle.uniqueSort
• underscore.uniq

测试环境是Linux Sandybridge i5 x86-64下的chrome 26(下称v8）和firefox 20（下称ionmonkey）

测试数据有3种：

// 纯数字
var mkArr = function(len, dev) {
    var xs = new Array(len);
    for (var i = 0; i < len; ++i) {
        xs[i] = Math.floor(Math.random() * dev);
    }
    return xs;
};

// 字符串和数字混在一起
var mkMixedArr = function(len, dev) {
    var xs = new Array(len);
    for (var i = 0; i < len; ++i) {
        var t = Math.floor(Math.random() * dev);
        xs[i] = Math.random() > 0.5 ? t : String(t);
    }
    return xs;
};

// 纯object
var mkObjArr = function(len, dev) {
    var allObjs = new Array(dev);
    for (var i = 0; i < dev; ++i) {
        allObjs[i] = {x: /* For debugging */ i};
    }
    var xs = new Array(len);
    for (var i = 0; i < len; ++i) {
        xs[i] = allObjs[Math.floor(Math.random() * dev)];
    }
    return xs;
};

实验数据：

• v8/mkArr(3000, 3000)

  • 楼主提供的：<1ms
  • google closure: 3ms
  • underscore: 16ms
  • Sizzle: 526ms

• v8/mkMixedArr(3000, 3000)

  • 楼主提供的：输出错误
  • google closure: 4ms
  • underscore: 48ms
  • Sizzle: 输出错误

• v8/mkObjArr(10000, 10000)

  • 楼主提供的：输出错误
  • google closure: 9ms
  • underscore: 159ms
  • Sizzle: 488ms

• ionmonkey/mkArr(3000, 3000)

  • 楼主提供的：<1ms
  • google closure: 2ms
  • underscore: 33ms
  • Sizzle: 7ms

• ionmonkey/mkMixedArr(3000, 3000)

  • 楼主提供的：输出错误
  • google closure: 2ms
  • underscore: 64ms
  • Sizzle: 输出错误

• ionmonkey/mkObjArr(10000, 10000)

  • 楼主提供的：输出错误
  • google closure: 10ms
  • underscore: 367ms
  • Sizzle: 12ms

结论：

• 在处理纯数字的数组时，楼主的方法的速度是最快的
• google closure的速度在不同情况下都比较稳定，时间复杂度是O(n)，不过它的一个缺点是会往数组里的每个object上添加一个attribute用来充当object的hash。
• ionmonkey下的Sizzle也不错。在v8下很慢。。

测试的不足

• 还需要测试更多的情况，而且也许我测试的数组大小太小了..
• 需要搞清楚Sizzle在v8和ionmonkey上的区别是为什么
• 也许需要分析v8和ionmonkey的JIT输出的汇编

Answer 2

必须是原生的吗？ jQuery里有个unique方法

Answer 3

underscorejs的效率好低，将之前的元素push入一个新数组，然后再每次判断元素是否已存在这个数组内。

• 感谢HJin.me的提示，underscorejs是做了是否有序的判断，有则和jQuery的uniqueSort一样，没有则判断是否存在。

underscorejs的代码如下：

_.uniq = _.unique = function(array, isSorted, iterator, context) {
    if (_.isFunction(isSorted)) {
      context = iterator;
      iterator = isSorted;
      isSorted = false;
    }
    var initial = iterator ? _.map(array, iterator, context) : array;
    var results = [];
    var seen = [];
    each(initial, function(value, index) {
      if (isSorted ? (!index || seen[seen.length - 1] !== value) : !_.contains(seen, value)) {
        seen.push(value);
        results.push(array[index]);
      }
    });
    return results;
  };

---

jQuery的方法是先排序，然后从第二个元素开始只循环一次，每次和上一元素比较。 并且只记录需要删除的下标，然后删除原数组中的重复项，这样避免了元素太大而导致的效率问题，应该是最高效的了

• 这种方法仅仅在无所谓顺序时是最高效的。

jQuery的代码如下

        Sizzle.uniqueSort = function(results) {
            var elem,
            duplicates = [],
                i = 1,
                j = 0;

            // Unless we *know* we can detect duplicates, assume their presence
            hasDuplicate = !support.detectDuplicates;
            results.sort(sortOrder);

            if (hasDuplicate) {
                for (;
                (elem = results[i]); i++) {
                    if (elem === results[i - 1]) {
                        j = duplicates.push(i);
                    }
                }
                while (j--) {
                    results.splice(duplicates[j], 1);
                }
            }

            return results;
        };

Answer 4

http://underscorejs.org/#uniq

不建议自己写