报名参加CloudWeGo黑客松,奖金直推双丰收! 了解详情
写点什么

前端进阶: 总结几个常用的 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:473877

评论

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

nginx路径匹配踩坑

hasWhere

Vue进阶(幺贰叁):v-for 实现一行展示 n 个元素

No Silver Bullet

Vue 9月日更

Elasticsearch 源码学习(1)源码编译调试

Se7en

架构实战营-模块八作业

老实人Honey

《转》搭建websocket消息推送服务

hasWhere

古董系统的并发安全改造

hasWhere

中秋晴朗夜,我们与星月相见

白洞计划

TCP/IP参考模型与标准协议

Regan Yue

TCP/IP 9月日更

【LeetCode】最后一个单词的长度Java题解

Albert

算法 LeetCode 9月日更

Vue进阶(幺贰肆):前端用户体验提升(一)

No Silver Bullet

用户体验 9月日更

产品分析:如何给出解决方案?

石云升

产品经理 产品思维 9月日更

【架构设计模块八】:设计消息队列存储消息数据的 MySQL 表格

Ryoma

JavaScript进阶(六)继承

Augus

JavaScript 9月日更

RabbitMQ的高级特性和消息补偿机制,字节跳动面试真题

Java 程序员 后端

过滤器、拦截器、监听器

hasWhere

技术圈的【多肉小达人】,一篇文章你就能做到

梦想橡皮擦

9月日更

模块八作业

河马先生

架构实战营

P8级别的顶级“并发编程”宝典,面试完腾讯我才发现这些知识点竟然没掌握全

Java 程序员 后端

架构设计的一些思考

hasWhere

缓存系统设计与实现

hasWhere

模块四作业

Geek_fc100d

「架构实战营」

JVM启动参数学习笔记三

风翱

JVM 9月日更

PDF超过6000页,2021最新Java面试题及答案

Java 程序员 后端

架构实战营模块八作业

宁静志远

架构实战营

高可用延迟队列设计与实现

万俊峰Kevin

微服务 延迟队列 microservice Go 语言 定时队列

架构训练营-模块八作业

hello

架构训练营

架构训练营模块八作业

喻高咏        

架构训练营

SpringMVC源码分析-HandlerAdapter(2)-RequestMappingHandlerAdapter的初始化

Brave

源码 springmvc 9月日更

模块8作业

Geek_ywh40v

手机测试岗位常见面试问题汇总(持续更新中)

IT蜗壳-Tango

9月日更

Ember.js 项目开发之 Ember Data

devpoint

ember.js 9月日更

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