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

徐小夕 等级 428 0 0

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

前言

文中所有代码位于位于此代码仓库中,大家可以下载代码进行学习、推敲和改进。另,如果觉得这些用心推敲的代码对你有帮助的话,欢迎 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相关的底层知识,这里就先不介绍了,后期需要的话可以专门上一篇文章介绍~

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

收藏
评论区

相关推荐

《前端算法系列》数组去重
虽然算法在前端开发中很少会得以使用,但是了解常用的算法,熟悉各种算法的性能和优劣,将会让你在前端的道路上走的更远。 前言 文中所有代码位于位于此代码仓库中(https://link.zhihu.com/?targethttps%3A//github.com/MrXujiang/dataAndMethods),大家可以下载代码进行学习、推敲和改进。
flutter -- dart基础之dart简介和安装
Dart介绍: Dart是由谷歌开发的计算机编程语言,它可以被用于web、服务器、移动应用 和物联网等领域的开发。 Dart诞生于2011年,号称要取代JavaScript。但是过去的几年中一直不温不火。直到Flutter的出现现在被人们重新重视。 要学Flutter的话我们必须首先得会Dart。 da
前端进阶之从零到一实现单向 & 双向链表
前言 前端工程师对于算法和数据结构这块的知识的掌握程度,是进阶高级工程师的非常重要的标志之一,为了总结一下数据结构和算法方面的知识,笔者今天继续把链表这一块的知识补上,也作为自己知识体系的一个梳理,笔者早在去年就写过一篇关于使用javascript实现二叉树和二叉搜索树的文章,如果感兴趣或者想进阶高级的朋友们可以参考学习一下: JavaScript 中的二
Javascript 常用代码优化和重构的方法
简介 主要介绍以下几点: 1. 提炼函数 2. 合并重复的条件片段 3. 把条件分支语句提炼成函数 4. 合理使用循环 5. 提前让函数退出代替嵌套条件分支 6. 传递对象参数代替过长的参数列表 7. 少用三目运算符 8. 合理使用链式调用 9. 分解大型类 10. 活用位操作符 11. 纯函数 本文会不断更新,不足之处欢迎
面试官在“逗”你系列:数组去重你会几种呀?
前言 数组去重是一个老生常谈的话题,也是前端童鞋在面试时的一道高频题。本文将深入的探索数组去重的原理及实现,为各位小伙伴提供多种可以反手“调戏”面试官的解决方案。 话不多说,上去就来一梭子... 数组去重核心原理 价值100W的核心原理上来就给你了...,记得留言点赞鸭! 1. 一般我们都会创建临时变量tmp,存储不重复的元素(以数组元素存储或对
基于Vue实现一个有点意思的拼拼乐小游戏
笔者去年曾写过一个类似的拼拼乐小游戏,技术栈采用自己的Xuery框架和原生javascript实现的,脚手架采用gulp来实现,为了满足对vue的需求,笔者再次使用vue生态将其重构,脚手架采用比较火的vuecli。 前言 为了加深大家对vue的了解和vue项目实战,笔者采用vue生态来重构此项目,方便大家学习和探索。技术栈如下: vuecli4
14个优秀 JS 前端框架、库、工具及其使用时机
  这篇文章主要描述现今流行的一些 Javascript web 前端框架,库以及它们的适用场景。   新的 Javascript 库层出不穷,从而Web 社区愈发活跃、多样、在多方面快速发展。详细去描述每一种主流的 Javascript 框架和库近乎
js去除字符串
js去除字符串js<DOCTYPE html<html<head <title</title</head<body</body<script type"text/javascript" function delHtmlTag(str){   return str.replace(/<^/g,""); } var s
JavaScript 是什么?
前言 引用《JavaScript 高级程序设计第四版》中说的话 ——“从简单的输入验证脚本到强大的编程语言,JavaScript 的崛起没有任何人预测到。它很简单,学会用只要几分钟;它又很复杂,掌握它要很多年。要真正学好用好 JavaScript,理解其本质、历史及局限性是非常重要的”。 面试官:JavaScript 是什么? 我:
一段代码被老大要求重构了六次,我心态崩了
前言Hi,大家好,我是麦洛。我又回来啦🙈进来给大家八卦一段,看看我自己都去干啥了?话说最近公司接了一个农产品交易网站新项目,因为一段代码重构问题差点和老大干起来,本来以为是老大故意刁难我。最后还是发现是我太菜了😏,事情是这个样子滴!在周例会上,老大告知我们最近接了一个农产品交易平台,主要用于全省农产品线上交易。首当其中,就是要把我们甘肃省的黄河蜜推销出去,我
面试官:JavaScript的数据类型你了解多少?
前言作为JavaScript的入门知识点,Js数据类型在整个JavaScript的学习过程中其实尤为重要。最常见的是边界数据类型条件判断问题。我们将通过这几个方面来了解数据类型: 概念 检测方法 转换方法 概念undefined、Null、Boolean、String、Number、Symbol、BigInt为基础类型;Ob
重学JavaScript第1集|变量提升
变量提升就好比JavaScript引擎用一个很小的代码起重机将所有var声明和function函数声明都举起到所属作用域(所谓作用域,指的是可访问变量和函数的区域)的最高处。这句话的意思是:如果在函数体外定义函数或使用var声明变量。则变量和函数的作用域会提升到整个代码的最高处,此时任何地方访问这个变量和调用这个函数都不会报错;而在函数体内定义函数或使用va
重学JavaScript(函数)闭包
序言学习JavaScript切勿好高骛远。正所谓贪多嚼不烂,前端标准和工具这几年的飞速发展,以及不时冒出的“新鲜玩意”让众多前端从业者惊呼:“学不动啦学不动啦!学习速度跟不上技术发展速度!我感到手忙脚乱、力不从心……"如果你有以上“症状”,请勿着急,这不过是你内心不安造成的。你为何追新?你又何苦追新?在根基不牢的情况下,就算盖楼盖到18层,再往上堆一块砖,都
了解什么是 TypeScript
内容纲要 了解什么是 TypeScript TypeScript 基本语法 TypeScript 介绍 TypeScript 是什么TypeScript 是 JavaScript 的强类型版本。然后在编译期去掉类型和特有语法,生成纯粹的 JavaScript代码。由于最终在浏览器中运行的仍然是 JavaScript,所以 TypeScript 并
一次搞懂-JavaScript之异步编程
前言异步,就是非同步....这节内容可能会有点枯燥,但是却是 JavaScript 中非常重要的概念,非常有必要去学习。 目的 提升开发效率,编写易维护的代码 引子问题 请求时候为什么页面卡死??js$.ajax( url: "www.xx.com/api", async: false, // true success: function(result