JavaScript 高性能数组去重

  

  

JavaScript 高性能数组去重

中午和同事吃饭,席间讨论到数组去重这一问题

我立刻就分享了我常用的一个去重方法,随即被老大指出这个方法效率不高

回家后我自己测试了一下,发现那个方法确实很慢

于是就有了这一次的高性能数组去重研究

 

一、测试模版

数组去重是一个老生常谈的问题,网上流传着有各种各样的解法

为了测试这些解法的性能,我写了一个测试模版,用来计算数组去重的耗时


// distinct.js

let arr1 = Array.from(new Array(100000), (x, index)=>{
    return index
})

let arr2 = Array.from(new Array(50000), (x, index)=>{
    return index+index
})

let start = new Date().getTime()
console.log('开始数组去重')

function distinct(a, b) {
    // 数组去重
}

console.log('去重后的长度', distinct(arr1, arr2).length)

let end = new Date().getTime()
console.log('耗时', end - start)
复制代码

这里分别创建了两个长度为 10W 和 5W 的数组

然后通过 distinct() 方法合并两个数组,并去掉其中的重复项

数据量不大也不小,但已经能说明一些问题了

 

二、Array.filter() + indexOf

这个方法的思路是,将两个数组拼接为一个数组,然后使用 ES6 中的 Array.filter() 遍历数组,并结合 indexOf 来排除重复项

function distinct(a, b) {
    let arr = a.concat(b);
    return arr.filter((item, index)=> {
        return arr.indexOf(item) === index
    })
}

这就是我被吐槽的那个数组去重方法,看起来非常简洁,但实际性能。。。

是的,现实就是这么残酷,处理一个长度为 15W 的数组都需要 8427ms

 

三、双重 for 循环

最容易理解的方法,外层循环遍历元素,内层循环检查是否重复

当有重复值的时候,可以使用 push(),也可以使用 splice()

复制代码
function distinct(a, b) {
    let arr = a.concat(b);
    for (let i=0, len=arr.length; i<len; i++) {
        for (let j=i+1; j<len; j++) {
            if (arr[i] == arr[j]) {
                arr.splice(j, 1);
                // splice 会改变数组长度,所以要将数组长度 len 和下标 j 减一
                len--;
                j--;
            }
        }
    }
    return arr
}
复制代码

但这种方法占用的内存较高,效率也是最低的

 

 

四、for...of + includes()

双重for循环的升级版,外层用 for...of 语句替换 for 循环,把内层循环改为 includes()

先创建一个空数组,当 includes() 返回 false 的时候,就将该元素 push 到空数组中 

类似的,还可以用 indexOf() 来替代 includes()

复制代码
function distinct(a, b) {
    let arr = a.concat(b)
    let result = []
    for (let i of arr) {
        !result.includes(i) && result.push(i)
    }
    return result
}
复制代码

这种方法和 filter + indexOf 挺类似

只是把 filter() 的内部逻辑用 for 循环实现出来,再把 indexOf 换为 includes

所以时长上也比较接近

 

  

五、Array.sort()

首先使用 sort() 将数组进行排序

然后比较相邻元素是否相等,从而排除重复项

复制代码
function distinct(a, b) {
    let arr = a.concat(b)
    arr = arr.sort()
    let result = [arr[0]]

    for (let i=1, len=arr.length; i<len; i++) {
        arr[i] !== arr[i-1] && result.push(arr[i])
    }
    return result
}
复制代码

这种方法只做了一次排序和一次循环,所以效率会比上面的方法都要高

 

  

六、new Set()

ES6 新增了 Set 这一数据结构,类似于数组,但 Set 的成员具有唯一性

基于这一特性,就非常适合用来做数组去重了

function distinct(a, b) {
    return Array.from(new Set([...a, ...b]))
}

那使用 Set 又需要多久时间来处理 15W 的数据呢?

喵喵喵??? 57ms ??我没眼花吧??

然后我在两个数组长度后面分别加了一个0,在 150W 的数据量之下...

居然有如此高性能且简洁的数组去重办法?!

 

七、for...of + Object

这个方法我只在一些文章里见过,实际工作中倒没怎么用

首先创建一个空对象,然后用 for 循环遍历

利用对象的属性不会重复这一特性,校验数组元素是否重复

复制代码
function distinct(a, b) {
    let arr = a.concat(b)
    let result = []
    let obj = {}

    for (let i of arr) {
        if (!obj[i]) {
            result.push(i)
            obj[i] = 1
        }
    }

    return result
}
复制代码

当我看到这个方法的处理时长,我又傻眼了

15W 的数据居然只要 16ms ??? 比 Set() 还快???

然后我又试了试 150W 的数据量...

emmmmmmm.... 惹不起惹不起...

  

  

120 字之内
全部评论(0)
推荐阅读,请笑纳
天寒 天寒 2017-11-26

哀伤 | 契诃夫

密密层层的大雪渐渐变得灰暗了。黄昏已经来临。“我这是往哪儿赶呀?”旋匠突然惊醒过来,该把她埋了,我却去医院,……像变傻了!”旋匠又掉转雪橇,又抽起马来。老马鼓足全身的劲,喷着鼻子,开始小跑起来。旋匠接二连三地抽它的背……身后响起撞击声,他虽然没有回头,也知道那是死去的老太婆的头在撞着雪橇。天色变得越来越黑,风变得越来越冷,越来越刺骨……“再从头活一次就好了……”旋匠想道,“我要添置一套新工具,接受定货……把钱都交给老太婆……是的!”后来他无意中把缰绳弄丢了。他寻找起来,想把缰绳捡起来,却怎么也不行。他的手活动不了了……“算了……”他心想,“反正马认路,它会拉回家的。这会儿真想睡一觉……趁下葬以前,安魂祭以前,最好歇一歇。”旋匠闭上眼睛,开始打盹。不久他听到马站住不走了。他睁眼一看,自己面前有一堆黑糊糊的东西,像是小木屋,又像大草垛……他真想从雪橇上爬下来,弄清楚是这么回事,可是全身懒得宁愿冻死,也不想动弹了……于是他安静地睡着了。

收藏 0 推荐 0 评论 0 阅读 761
天寒 天寒 2017-11-27

变色龙 | 契诃夫

警官奥楚美洛夫穿着新的军大衣,手里拿着个小包,穿过市集的广场。他身后跟着个警察,生着棕红色头发,端着一个粗罗,上面盛着没收来的醋栗,装得满满的。四下里一片寂静。……广场上连人影也没有。小铺和酒店敞开大门,无精打采地面对着上帝创造的这个世界,象是一张张饥饿的嘴巴。店门附近连一个乞弓都没有。“你竟敢咬人,该死的东西!”奥楚美洛夫忽然听见说话声。“伙计们,别放走它!如今咬人可不行!抓住它!哎哟,……哎哟!”狗的尖叫声响起来。奥楚美洛夫往那边一看,瞧见商人彼楚京的木柴场里窜出来一条狗,用三条腿跑路,不住地回头看。在它身后,有一个人追出来,穿着浆硬的花布衬衫和敞开怀的坎肩。他紧追那条狗,身子往前一探,扑倒在地,抓住那条狗的后腿。紧跟着又传来狗叫声和人喊声:“别放走它!”带着睡意的脸纷纷从小铺里探出来,不久木柴场门口就聚上一群人,象是从地底下钻出来的一样。“仿佛出乱子了,官长!……”警察说。奥楚美洛夫把身子微微往左边一转,迈步往人群那边走过去。在木柴场门口,他看见上

收藏 0 推荐 0 评论 0 阅读 934
天寒 天寒 2017-11-27

变色龙 | 契诃夫

“不过也可能是将军家的狗……”警察把他的想法说出来。“它脸上又没写着。……前几天我在他家院子里就见到过这样一条狗。”“没错儿,是将军家的!”人群里有人说。“嗯!……你,叶尔迪陵老弟,给我穿上大衣吧。……好象起风了。……怪冷的。……你带着这条狗到将军家里去一趟,在那儿问一下。……你就说这条狗是我找着,派你送去的。……你说以后不要把它放到街上来。也许它是名贵的狗,要是每个猪猡都拿雪茄烟戳到它脸上去,要不了多久就能把它作践死。狗是娇嫩的动物嘛。……你,蠢货,把手放下来!用不着把你那根蠢手指头摆出来!这都怪你自己不好!……”“将军家的厨师来了,我们来问问他吧。……喂,普罗霍尔!你过来,亲爱的!你看看这条狗。……是你们家的吗?”“瞎猜!我们那儿从来也没有过这样的狗!”“那就用不着费很多工夫去问了,”奥楚美洛夫说。“这是条野狗!用不着多说了。……既然他说是野狗,那就是野狗。……弄死它算了。”“这条狗不是我们家的,”普罗霍尔继续说。“可这是将军哥哥的狗

收藏 0 推荐 0 评论 0 阅读 920
天寒 天寒 2018-02-08

坏孩子 | 契诃夫

伊凡·伊凡内奇·拉普金,一个讨人喜欢的年轻人和安娜·谢苗诺夫娜·扎姆布里茨卡娅,一个翘鼻子的年轻姑娘,双双走下陡峭的河岸,坐到一张长椅上。长椅临水而立,藏在密密的柳丛里。好一处绝妙的地方!您若往这儿一坐,您就与世隔绝了--能看见您的只有鱼儿,还有那水面上闪电般跑来跑去的水蜘蛛。这对年轻人随身带着鱼竿,抄网,装蚯蚓的小罐和其他鱼具。坐下后,他们立即开始垂钓。“我真高兴,咱俩总算能单独在一块儿了,”拉普金东张西望着开始说,“我有许多话要告诉您,安娜·谢苗诺夫娜……许多许多话……当我第一次见到您的时候……鱼咬您的钩了……我立即就明白:我为什么活着,我崇拜的偶像在哪儿,我应当为谁献出我清白而勤劳的一生……咬钩的可能是一条大鱼……见着您后,我才第一次爱上一个人,爱得发狂!……等一会儿您再拉竿……让它咬死了……请告诉我,我亲爱的,我向您发誓,我能否指望--啊,我不是指望相互爱慕,不是的!--这个我不配,我连想都不敢这样想--我能否指望……您快拉竿呀!”安娜·谢苗诺夫娜提起握着的钓竿,

收藏 0 推荐 0 评论 0 阅读 712
天寒 天寒 2017-11-27

我的“她”| 契诃夫

她,按照我的双亲和上司的权威说法,比我出生得早。且不管他们说得对不对,但我只知道,在我的有生之年中,没有一天不从属于她,不感到她对我的控制。她日日夜夜不离开我,我也从未表示过要离她而去的意思,因此这种结合是坚实而牢固的……然而请不要嫉妒,年轻的女性读者!这种令人感动的结合没有给我带来任何好处,只有种种不幸。首先,我的“她”日日夜夜厮守着我,不让我干点正经事情。她妨碍我阅读,写作,游玩,欣赏大自然风光……我才写了几行字,她就老来碰我的胳膊时,分分秒秒都在引诱我到床榻上去,不亚于古代的克莉奥佩特拉引诱古代的安东尼①。其次,她像法国妓女,害得我倾家荡产。由于她的恋恋不舍,我为她牺牲了一切:前程,荣誉,舒适……多蒙她的关照,我住便宜的租屋,穿得破烂,吃得糟糕,用淡墨水写作。她吞噬一切,一切,这个贪得无厌的东西!我憎恨她,蔑视她……早该跟她分手了,但我却至今没有跟她分手,倒不是因为莫斯科的律师们办离婚案要收费四千……我们目前没有孩子……您想知道她的名字吗?好吧……名字富于诗意,它使人联想起莉丽娅,

收藏 0 推荐 0 评论 1 阅读 718
天寒 天寒 2018-02-08

相识的男人 | 契诃夫

漂亮迷人的万达,或者照身份证上的记载:荣誉公民娜斯塔西娅·卡纳夫金娜,刚出医院就落人前所未遇的困境:既无安身之处,又身无分文。怎么办?她头一件事就是跑到信贷所,把她唯一的宝物--一枚绿松石戒指典当了。他们付给她一个卢布,可是……一个卢布能买什么呀?这点钱买不了时髦的外套,买不了漂亮的高帽,买不了古铜色的鞋子,而没有这些东西她总觉得就像光着身子一样。她感到不只是行人,就连那些马和狗也盯着她看,嘲笑她这身不像样的衣服。她一心只想着穿戴,至于吃饭住宿问题倒一点也不让她着急。“只要遇到一个相识的男人……”她心想,“我就有钱了……谁也不会拒绝我,因为……”可是相识的男人一个也没有遇到。晚上在“文艺复兴”俱乐部倒不难碰见他们,不过现在她穿着这身难看的衣服,也不戴帽子,人家是不放她进门的。怎么办?经过长时间的折腾,她也走累了,坐腻了,想烦了。万达决定使出最后一招:干脆找上门去,跟某个相识的男人讨点钱。“找谁好呢?”她寻思,“米沙不行,他是有家室的人……红毛老头子正在上

收藏 0 推荐 0 评论 0 阅读 782
天寒 天寒 2018-02-08

相识的男人 | 契诃夫

“请进!”女仆说着把她领进诊室,“医生马上就来……您坐呀。叫万达坐进软椅里。“我这么对他说:请借我几个钱!”她心想,“这样体面些,毕竟我们是熟人。只是这个女仆最好出去。当着女仆的面多么难为情……她老站在这儿干什么?”过了四五分钟,房门开了,芬克尔走了进来。这是个肤色发黑、身材高大的犹太人,腮帮子肥嘟嘟的,眼睛鼓出。那脸蛋,眼睛,肚子,粗壮的大腿--他身上的一切都显得那么臃肿、讨厌、冷漠。在“文艺复兴”俱乐部和德国俱乐部,他通常喝得醉醺醺的,肯在女人身上大把花钱,心甘情愿受她们的嘲弄(比如,那次万达往他头上倒了一杯啤酒,他只是微微一笑,伸出一个手指吓唬她一下)。眼前的他却是脸色阴沉,睡眼惺松,看上去一本正经,神情冷淡,像个官僚。他嘴里还嚼着什么东西。“您有何吩咐?”他问,正眼不看万达。万达看看女仆那严肃的面孔,再看看芬克尔大腹便便的身子,显然他认不出她来了,她不禁脸红了……“您有何吩咐?”牙医再问时已经生气了。“牙……牙疼……”万达

收藏 0 推荐 0 评论 0 阅读 842
天寒 天寒 2017-11-27

她这么可爱,还是试着走下去吧

有个姑娘,在她快生了的时候,我才知道她怀孕的。她一直不敢跟家里的人说,到了差不多九个月的时候,她家里人才知道的,因为这个时候她终于鼓起勇气跟家里人说明白了,然而家里的人并没有怪罪她,还叫她生下来,好好培养,一开始,大家以为都是个男孩子,最后大家都不错了,生了一个可爱的妹妹。我们一直以为她很幸福,那家人对她还有生活都挺开心的,就算家境不如意,至少有妹妹的欢声笑语。但是我们又错了,她并不怎么如意。我也是最近才知道的,因为不直觉间,她跟我说了很多。她说,在她怀孕的前三个月,那家人一直没有问侯过她,也没有关心过她。她那时候很伤心很伤心,打算不要了这个孩子。不过她说现在看到妹妹可爱的笑脸,还好当时下定了决心,她并没有后悔生下妹妹,而是后悔跟他生下了。我在想,她说出这句话的时候,是多么伤心,多么地对那个人失去了信心。他姐说这个姑娘怀了他家的人也没有问过也没有表态过,知道姑娘的心里不好受。姑娘跟那个男的说,你家人都是没有想要过这个孩子,如果这样的话,我就不要了。然而男的死活不让,最后姑

收藏 0 推荐 0 评论 0 阅读 696
加油少年 加油少年 2018-02-15

过年的意义

回家过年,过年回家,是一个沉甸甸的话题。每逢年关将近,许许多多身在异乡的人们对思归会越来越浓。    没有流浪过的人,又怎能明白游子们酸涩而甜美的乡愁。对养育自己的那块土地的剪不断的情谊,对家深切的眷恋,对亲人强烈的思念。    不管是山高路远,艰难险阻,都阻挡不住一个人回家的心。一张回家的车票,是一份堆积了一年的迫切之心。    路途是变幻的光影,寒冷的北风、飞舞的雪花,巍峨的山,冰封的河流,以及拥挤的列车上宣泄的热泪与疲惫的笑容。    走在故乡的土地上,呼吸着那难以忘怀的空气,是多么的亲密温馨。亲切的乡音在耳边萦绕,熟悉的每一条街道,每一个角落都有少年时的痕迹,又怎能不让人铭记在心底。    踏进家门的一刻,时间刹那被定格,记忆的河流里流淌着曾经那段最美好的时光,影像一页页在眼前翻过,猝然一股暖意袭来,泪水顿时如泉水一涌而出。    当看到父母的那一刻,我又瞬间变成了六七岁的孩童。父母脸上那慈祥的笑容,是许久了的挂念与盼望。  

收藏 0 推荐 0 评论 2 阅读 864
天寒 天寒 2017-11-28

她陷入了他那里,再怎么深,也得出来了

群里有个高三的妹子说她喜欢一个男的很久了,他们是同班的,女的叫小蜜,男的叫小凡。但是小蜜是单相思的,也就是一直暗恋着小凡,这件事她除了她的舍友的知道,谁都不告诉,所以小凡就从来都不知道有个女孩子暗恋着她。暗恋的滋味,每个人都知道是很痛苦的一件事情。还好的是,她们两个是同班的同学,很奇葩的是,她们还是同桌,而且是同桌了两年,从分文理科的时候就坐在一起了。或许是因为日久真的可以生情,谁能说得清楚小凡就没有希望过小蜜呢。就从小凡每天早上都给小蜜买早餐,每天中午两个人一起下课,晚上自习完成后一起走回宿舍,如果不是两个人从来没有牵过手,也没有表过态在一起,班里所有的人就以为他们是情侣,不过确实像情侣一样两点一线得努力着。其实能够跟小凡这样过着每一天,小蜜的心里是很是开心的。至少他接触自己的时间,和陪着自己的时间是最多的。但是,这种局面最好是两个人都不要打破。有些事情揭开了,如果并不如意,或许会有着难以迈过的隔阂。高三的时间总是那么的紧迫而又飞速。小蜜,还是小凡都还没有来得及告白

收藏 0 推荐 0 评论 0 阅读 701