写点什么

前端进阶: 总结几个常用的 JS 搜索算法和性能对比

  • 2020-12-07
  • 本文字数:2532 字

    阅读完需:约 8 分钟

前端进阶: 总结几个常用的 JS 搜索算法和性能对比

前言


今天让我们来继续聊一聊 JS 算法,通过接下来的讲解,我们可以了解到搜索算法的基本实现以及各种实现方法的性能,进而发现 for 循环,forEach,While 的性能差异,我们还会了解到如何通过 Web Worker 做算法分片,极大的提高算法的性能。


同时我还会简单介绍一下经典的二分算法哈希表查找算法,但这些不是本章的重点,之后我会推出相应的文章详细介绍这些高级算法,感兴趣的朋友可以关注我的专栏,或一起探讨。


对于算法性能,我们还是会采用上一章 《前端算法系列》如何让前端代码速度提高60倍 中的 getFnRunTime 函数,大家感兴趣的可以查看学习,这里我就不做过多说明。


在上一章 《前端算法系列》如何让前端代码速度提高60倍 我们模拟了 19000 条数据,这章中为了让效果更明显,我将伪造 170 万条数据来测试,不过相信我,对 js 来说这不算啥。。。


1. for 循环搜索


基本思路:通过 for 循环遍历数组,找出要搜索的值在数组中的索引,并将其推进新数组


代码实现如下:


const getFnRunTime = require('./getRuntime');
/** * 普通算法-for循环版 * @param {*} arr * 耗时:7-9ms */ function searchBy(arr, value) { let result = []; for(let i = 0, len = arr.length; i < len; i++) { if(arr[i] === value) { result.push(i); } } return result } getFnRunTime(searchBy, 6)
复制代码


测试 n 次稳定后的结果如图:



2. forEach 循环


基本思路和 for 循环类似:


/**  * 普通算法-forEach循环版  * @param {*} arr   * 耗时:21-24ms  */ function searchByForEach(arr, value) {    let result = [];    arr.forEach((item,i) => {        if(item === value) {            result.push(i);        }    })   return result}
复制代码


耗时 21-24 毫秒,可见性能不如 for 循环(先暂且这么说哈,本质也是如此)。


3. while 循环


代码如下:


/**  * 普通算法-while循环版  * @param {*} arr   * 耗时:11ms  */ function searchByWhile(arr, value) {     let i = arr.length,     result = [];    while(i) {        if(arr[i] === value) {            result.push(i);        }        i--;    }       return result}
复制代码


可见 while 和 for 循环性能差不多,都很优秀,但也不是说 forEach 性能就不好,就不使用了。forEach 相对于 for 循环,代码减少了,但是 forEach 依赖 Enumerable。在运行时效率低于 for 循环。但是在处理不确定循环次数的循环,或者循环次数需要计算的情况下,使用 forEach 比较方便。而且 forEach 的代码经过编译系统的代码优化后,和 for 循环的循环类似。


4. 二分法搜索


二分法搜索更多的应用场景在数组中值唯一并且有序的数组中,这里就不比较它和 for/while/forEach 的性能了。


基本思路:从序列的中间位置开始比较,如果当前位置值等于要搜索的值,则查找成功;若要搜索的值小于当前位置值,则在数列的前半段中查找;若要搜索的值大于当前位置值则在数列的后半段中继续查找,直到找到为止


代码如下:


/**   * 二分算法   * @param {*} arr    * @param {*} value    */  function binarySearch(arr, value) {    let min = 0;    let max = arr.length - 1;        while (min <= max) {      const mid = Math.floor((min + max) / 2);        if (arr[mid] === value) {        return mid;      } else if (arr[mid] > value) {        max = mid - 1;      } else {        min = mid + 1;      }    }      return 'Not Found';  }
复制代码


在数据量很大的场景下,二分法效率很高,但不稳定,这也是其在大数据查询下的一点小小的劣势。


5. 哈希表查找


哈希表查找又叫散列表查找,通过查找关键字不需要比较就可以获得需要记录的存储位置,它是通过在记录的存储位置和它的关键字之间建立一个确定的对应关系 f,使得每个关键字 key 对应一个存储位置 f(key)


哈希表查找的使用场景:


  • 哈希表最适合的求解问题是查找与给定值相等的记录

  • 哈希查找不适合同样的关键字对应多条记录的情况

  • 不适合范围查找,比如查找年龄 18~22 岁的同学


在这我先给出一个最简版的 hashTable,方便大家更容易的理解哈希散列:


/** * 散列表 * 以下方法会出现数据覆盖的问题 */function HashTable() {  var table = [];
// 散列函数 var loseloseHashCode = function(key) { var hash = 0; for(var i=0; i<key.length; i++) { hash += key.charCodeAt(i); } return hash % 37 };
// put this.put = function(key, value) { var position = loseloseHashCode(key); table[position] = value; }
// get this.get = function(key) { return table[loseloseHashCode(key)] }
// remove this.remove = function(key) { table[loseloseHashCode(key)] = undefined; }}
复制代码


该方法可能会出现数据冲突的问题,不过也有解决方案,由于这里涉及的知识点比较多,后期我会专门推出一篇文章来介绍:


  • 开放定址法

  • 二次探测法

  • 随机探测法


使用 Web Worker 优化


通过以上的方法,我们已经知道各种算法的性能和应用场景了,我们在使用算法时,还可以通过 Web Worker 来优化,让程序并行处理,比如将一个大块数组拆分成多块,让 Web Worker 线程帮我们去处理计算结果,最后将结果合并,通过 Worker 的事件机制传给浏览器,效果十分显著。


总结


  1. 对于复杂数组查询,for/while 性能高于 forEach 等数组方法

  2. 二分查找法的 O(logn) 是一种十分高效的算法。不过它的缺陷也很明显:必须有序,我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序,可是又落到了第二个瓶颈上:它必须是数组。数组读取效率是 O(1),可是它的插入和删除某个元素的效率却是 O(n)。因而导致构建有序数组的时候会降低效率。

  3. 哈希表查找的基本用法及使用场景。

  4. 条件允许的话,我们可以用 Web Worker 来优化算法,让其在后台并行执行。


好啦,这篇文章虽然比较简单,但十分重要,希望大家对搜索算法有更加直观的认识,也希望大家有更好的方法,一起探讨交流。



作者:徐小夕,未经授权不可转载。

原文链接前端进阶: 总结几个常用的js搜索算法和性能对比

2020-12-07 13:473926

评论

发布
暂无评论
发现更多内容

吹水、面试、进阶齐飞!Github霸榜的阿里分布式设计实录也太香了

Java架构师迁哥

前端性能优化实践 | 百度APP个人主页优化

百度开发者中心

大前端 百度app

HashMap从入门到精通,原创好文,值得收藏!

wljslmz

Java hashmap java8 HashMap底层原理

4轮技术面+1轮HR面,成功拿到腾讯40k*16的Offer ,详解面试流程和真题解析

Java 程序员 架构 面试

金九银十面试必备,“全新”突击真题宝典,阿里腾讯字节都稳了

Java 编程 程序员 架构 面试

一周信创舆情观察(6.28~7.4)

统小信uos

北鲲云超算平台——让科技更好地服务于用户

北鲲云

32岁的我裸辞了,八年Java老鸟,只因薪水被应届生倒挂,在闭关三个月后拿到阿里Offer,定级P7!

Java架构师迁哥

TDengine JDBC整合Druid

山石道人

涛思数据 tdengine Druid Spring MVC taos-jdbc

使用tar 命令进行文件的归档和压缩

学神来啦

云计算 Linux 运维 linux运维

KDD CUP 2021首届图神经网络大赛放榜,百度飞桨PGL获得2金1银

百度大脑

神经网络 百度

GNURadio报错Unable to create context(windows10环境)

allu

问题总结

智邦国际ERP系统31.99版本发布,解锁精准高效协同管理模式!

叶落便知秋

2021年,BAT接连入局!“低代码”为何能备受资本追捧?

优秀

低代码

永续合约交易所开发,虚拟币合约交易系统源码

不愧是阿里内部“SpringCloudAlibaba学习笔记”看完直接斩获12家offer

Java 编程 架构 面试 微服务

底层技术支撑智慧出行,汽车智能化发展下区块链大放异彩

旺链科技

区块链产业

腾讯二面:Linux操作系统里一个进程最多可以创建多少个线程?

白亦杨

【工作感悟】2021最值得加入的互联网公司有哪些

欢喜学安卓

android 程序员 面试 移动开发

GitHub星标70K阿里大佬手写的Spring Boot实战手册

Java架构师迁哥

教你给场景添加天空盒,超简单!

ThingJS数字孪生引擎

大数据 大前端 开发 可视化 数字孪生

免费分享JDBC与MyBatis的优秀图书

Java入门到架构

Java

Hightopo可视化入局“智慧工厂”,助力企业改革创新

一只数据鲸鱼

数据可视化 绿色工业 3D数据可视化 高炉炼铁 智慧工业

DataPipeline实时数据融合平台V3.0里程碑版发布!澎湃新动能

DataPipeline数见科技

大数据 数据融合 数据管理

什么?C语言也能try...catch!

实力程序员

我删库跑路失败了

程序员鱼皮

Java c++ Python Linux 服务器

DataWorks赋能企业一站式数据开发治理能力

阿里云大数据AI技术

一位年薪 180 万的蚂蚁金服大佬扔给我的笔记,建议看完

Java架构师迁哥

越学越有趣:『手把手带你学NLP』系列项目07 ——机器翻译的那些事儿

百度大脑

机器学习 nlp

统一缓存帝国 - 实战 Spring Cache

悟空聊架构

缓存 passjava 悟空聊架构 7月日更 Spring Cache

【工作感悟】Android大厂高级面试题灵魂100问

欢喜学安卓

android 程序员 面试 移动开发

前端进阶: 总结几个常用的 JS 搜索算法和性能对比_大前端_徐小夕_InfoQ精选文章