A-A+

JS数组去重

2016年04月17日 JavaScript 暂无评论 阅读 294 次

JS数组去重

 

  1. 一般来说是建立一个哈希表,类似这样
  2. var arr = [1, 2, 2, 3, 4, 5, 6, 6];
  3. function getArray(a) {
  4. var hash = {},
  5.      len = a.length,
  6.      result = [];
  7. for (var i = 0; i < len; i++){
  8. if (!hash[a[i]]){
  9.          hash[a[i]] = true;
  10.          result.push(a[i]);
  11.      }
  12.  }
  13. return result;
  14. }
  15. getArray(arr); // 输出[1, 2, 3, 4, 5, 6]

 

我对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输出的汇编

前几日在做js-assessment时,发现其数组这一章里也有数组去重的这一问题:这个问题说起来十分简单,就是把数组中重复的元素去除。其实个人感觉数组去重问题实际上就是排序的升级版,目前开来最好的去重方法就是字典去重,这一点和排序中的基数排序不谋而合。下面就简单的说一说自己解决这个问题的思路。

编写AOP时间函数

对于解决数组去重算法的好坏,最终效率是第一位的,所以需要编写一个计算函数运行时间的切面函数。实现如下:

Function.prototype.time = function() {
    var t1 = +new Date()
    ,   foo = this()
    ,   t2 = +new Date()
    return t2 - t1     //返回单位为毫秒
}

但是写完这个方法之后发现,对于要测试运行的函数而言,在进行测试之前不能够运行(即只能写成foo.time() 的样子),这样就不能用普通传参的方法对其进行参数传递。突然想到了在前几日看到过prototypejs中的源码中有一个 bind 函数,其功能就在与给一个函数绑定特定上下文,且返回函数本身而不立即执行,于是就马上实现了这样一个函数,代码如下:

Function.prototype.bind = function(ob) {
    var fn = this
    ,   slice = Array.prototype.slice
    ,   args = slice.call(arguments, 1)
    return function(){
        return fn.apply(ob, args.concat(slice.apply(arguments)))
    }   
}

写完这两个,我们就可以对测试函数进行运行时间计算,假如数组为 arr ,测试函数为 delrep ,则在实际操作中可以这样实现:delrep.bind(arr).time() (执行函数的同时输出运算时间)。

双重循环去重

在就去重方法讨论的文章中,愚人码头的文章里说到过这个方法,当然,作者本身也承认,这种双重for循环嵌套的方法在大数据量的情况下十分耗时。作者的源代码引用如下:

Array.prototype.delRepeat=function(){
    var newArray=new Array();
    var len=this.length;
    for (var i=0;i<len ;i++){
        for(var j=i+1;j<len;j++){
            if(this[i]===this[j]){
                j=++i;
            }
        }
        newArray.push(this[i]);
    }
    return newArray;
}

这里我也用ECMAScript中声明的 forEach 方法和 indexOf 方法模拟实现一下双重循环:

function delrep1() {
    var n = []

    this.forEach(function(v) {
        if (n.indexOf(v) == -1) 
            n.push(v)
    })  
    return n
}

作者的代码看起来像极了冒泡排序:每一次操作都会冒出一个没有重复元素的,放入新的数组(对应冒泡排序冒出最小的)。而冒泡排序的时间复杂度是O(n^2),可以想见这个算法的效率着实不高。而在我的算法中采用了 indexOf 的方法,没想这个遍历的效率要高很多,最终执行的时间要比作者的方法高不少。这里贴一下最终运行的时间(用随机生成的15w长度的数组进行测试,编译器使用的是想向大家极力推荐的nodejs,虽然这里只用了它一个小小的功能):

malcolm@malcolm:~/test/aop$ node aop.js 
method0: 1389ms    #我的方法
method1: 9087ms    #作者的方法

各中原理,还需要仔细的分析才行。

字典去重

之后作者提了一个字典去重的方法,我用自己的方法简化了一下:

function delrep2() {
    var n = {}
    ,   r = []

    this.forEach(function(v){
        if (!n[v]) {
            n[v] = true
            r.push(v)
        }
    })
    return r
},

这个一看就很脸熟——传说中时间复杂度只有O(n)的基数排序么!类似与扑克牌的发牌,一次遍历什么的不是最快捷了么。当然这里用到了“空间换时间”的策略,多出来一个庞大的字典,但是为了效率,做一点牺牲也是必要的。运行的时间也令人叹为观止:

malcolm@malcolm:~/test/aop$ node aop.js
method0: 1389ms
method1: 9087ms
method2: 9ms

但是令人遗憾的是,这个方法是有bug的:你把所有的元素都转化成字典的键值key,也就是字符串,那必然会出现1和'1'的问题。在数组中他们并不是重复元素,而这里只能保留一个。这可怎么办呢?在愚人码头帖子的回复中,马上有人提到了,既然键值转化为字符串后失去了类型,那如果在转化之前给他加上类型会怎么样呢?代码如下:

function delrep3() {
    var n = {}
    ,   r = []

    this.forEach(function(v){
        if (!n[typeof(v) + v]) {
            n[typeof(v) + v] = true
            r.push(v)
        }
    })
    return r
},

不过作者在回复里说,这个方法的效率和两重循环的差不多,难道真的是这样么?实际测试了一下:

malcolm@malcolm:~/test/aop$ node aop.js 
method0: 1389ms
method1: 9087ms
method2: 9ms
method3: 56ms

明显已经好了不少啊~可是可以看出因为 typeof 的原因,效率比第二个方法低了不少,但是没有bug的优势足以弥补这一缺憾。

排序遍历

问题说到这里好像已经解决了,但是实际上背后的算法问题我自己还是没有搞清楚,希望以后能把详细的原因补上。这里也写一个我自己最初想到的方法:要去重先遍历,依靠javascript自身的sort函数先帮我们过一关。据说这个函数用的是O(nlgn)的快速排序,显然是已经比冒泡要好不少了。排完序之后重复的数据都叠在一起,排头向栈里压数据,遇到与栈顶相同的元素则不压。我的算法如下:

function delrep4() {
    var n = []

    this.sort()
    n.push(this[0])
    this.forEach(function(v) {
        if (v !== n[0])
            n.unshift(v)
    })
    return n
}

最终的时间还是比较可观的,不过还是没有方法2的改进版本好,数据如下:

malcolm@malcolm:~/test/aop$ node aop.js 
method0: 1389ms
method1: 9087ms
method2: 9ms
method3: 56ms
method4: 88ms

看起来还不错~

在完成测试的同时参考了这篇文章:JS数组去重问题,文中还提到了用排序之后用splice删除重复元素的方法,不得不承认这样确实节省了一部分空间,但是js的splice方法,要涉及删除后的数组整列移动,道爷可是在蝴蝶书中点名说本方法“大型数组中效率较低”的。自己在测试的时候发现在15w数据量的时候用splice还是效率还是可以,再多的话就明显不如我自己的方法了。不过综合来说,如果可以保证数组内部是纯数值,用字典排序绝对还是最明智的选择。

希望下周可以补上对各个算法时间复杂度的简要说明。

https://segmentfault.com/q/1010000000197274

http://www.ituring.com.cn/article/49791

http://blog.csdn.net/anno_domini/article/details/9043369

http://www.oschina.net/code/snippet_1424777_44391

http://blog.jobbole.com/33099/

标签:

给我留言

Copyright © web前端技术开发个人博客 保留所有权利  京ICP备14060653号 Theme  Ality

用户登录