一般来说是建立一个哈希表,类似这样
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来说是否还有更加高效?
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;
};
我对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输出的汇编
http://underscorejs.org/#uniq
不建议自己写
必须是原生的吗? jQuery里有个unique方法