阅读 625

《前端算法系列》数组去重

虽然算法在前端开发中很少会得以使用,但是了解常用的算法,熟悉各种算法的性能和优劣,将会让你在前端的道路上走的更远。

前言

文中所有代码位于位于此代码仓库中,大家可以下载代码进行学习、推敲和改进。另,如果觉得这些用心推敲的代码对你有帮助的话,欢迎 star 一下代码仓库,众筹博主的小星星。

另外,本文中使用如下函数对代码进行性能测试:

module.exports = async function getFnRunTime(fn) {
    let startTime = Date.now(), endTime;
    let result = await fn();
    endTime = Date.now();
    console.log(`total time:${endTime-startTime}ms`,
                'test array\'length:' + len, 
                result.length
    );
}

复制代码

为了衡量性能,我们引入代码时间复杂度的概念,用大写O()来表现算法时间复杂度的记法,我们称之为大O记法。一般情况下,随着n的增大,T(n)增长最慢的算法为最优算法。

1.双重for循环去重

如果有相同的值则跳过,不相同则push进数组

function distinct1(arr = testArr) {
    let result = [],
           len = arr && arr.length;
    for (let i=0; i< len; i++) {
        for (let j=i+1; j< len; j++) {
            if (arr[i] === arr[j]) {
                j = ++i;
            }
        }
        result.push(arr[i])
    }
    return result
}
复制代码

由于使用了双层for循环,根据代码可知时间复杂度为O(n^2),用测试函数测的19815条数据的去重时间为:7-8ms;

2.利用indexOf和forEach/for循环去重

function distinct2(arr = testArr) {
    let result = [];
    arr.forEach((v, i, array) => {
        array.indexOf(v, i+1) === -1 && result.push(v)
    });
    return result
}
复制代码

可以看到该方法的代码很简洁,时间复杂度为O(n),但是indexOf会进行额外的性能消耗,测试相同的数据耗时为:4-5ms

3.对象法

通过利用对象建名的唯一性去去重

function distinct3(arr = testArr) {
    let result = [], resultObj = {}, len = arr.length;
    for(let i=0; i< len; i++) {
        let val = arr[i],
           type = typeof val;
        if(!resultObj[val]) {
            result.push(val);
            resultObj[val] = [type];
        } else if(!resultObj[val].indexOf(type) < 0) {
            result.push(val);
            resultObj[val] = [type];
        }
    }
    return result
}
复制代码

该方法很快,时间复杂度为O(n),但是由于会多创建一个对象,会带来额外的内存开销,尤其是数据量大的情景下,测试相同的数据耗时为:5ms

4.filter去重方法一

利用filter和indexOf来查询

function distinct4(arr = testArr) {
    return arr.filter((v, i, array) => array.indexOf(v, i+1) < 0)
}
复制代码

该方法也很简洁,测试相同的数据耗时为:4-5ms,关键优化点是利用indexOf的第二个参数去避免不必要的查询。

5.filter去重方法二

和方法4的区别是利用数组的索引的唯一性来去重

function distinct5(arr = testArr) {
    return arr.filter((v, i, array) => array.indexOf(v) === i)
}
复制代码

该方法同4,但是性能远不如方法4,因为数组每次调用indexOf都会重新查找整个数组,但这是必须要做的操作,否则就不能利用数组索引的唯一性了。耗时:16ms(小伙伴们都惊呆了)

6.利用es6的set方法

function distinct6(arr = testArr) {
    return [...new Set(arr)]
}
复制代码

此方法耗时1ms,但是局限性很大,针对相同类型的数据很快,但是不同类型的数据去重,将非常慢,这涉及到js相关的底层知识,这里就先不介绍了,后期需要的话可以专门上一篇文章介绍~

好啦,其实数组去重有很多种方法,只有你想不到的,没有实现不了的,如果你有更好更快的方法,欢迎一起交流探讨哦~

我们组建的vue-react-小程序-node交流学习群,已经有数百位各企业的前端伙伴加入,欢迎大家关注 趣谈前端公众号,加入前端大家庭,一起探索前端的边界

关注下面的标签,发现更多相似文章
评论