写点什么

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

评论

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

隐语纵向联邦 SecureBoost Benchmark白皮书

隐语SecretFlow

大数据 AI 数据安全 隐私计算 开源社区

和鲸科技为临床医学科研场景打造可供多角色协同的低代码研究平台

ModelWhale

人工智能 低代码 数据科学 在线编程 临床研究

量化智能机器人开发,炒币机器人功能部署搭建

V\TG【ch3nguang】

量化交易机器人开发 炒币机器人

开源微服务如何选型?Spring Cloud、Dubbo、gRPC、Istio 详细对比

阿里巴巴云原生

阿里云 云原生 dubbo

基于 Argo CD 与 Argo Workflows 的 GreptimeDB 云端自动化升级实践

Greptime 格睿科技

rust 时序数据库 云原生数据库 国产时序数据库 自动升级

Dropzone 4 for Mac(文件拖拽操作增强工具) 4.6.8中文激活版

mac

苹果mac Windows软件 Dropzone 4 文件管理器

质押挖矿模式系统开发,矿池系统部署搭建

V\TG【ch3nguang】

挖矿矿池系统开发案例 质押挖矿

文心一言 VS 讯飞星火 VS chatgpt (81)-- 算法导论7.4 6题

福大大架构师每日一题

福大大架构师每日一题

Node.js 的 Buffer 是什么?面向开发者的指南

Liam

JavaScript node.js 程序员 后端 buffer

九科信息成功签约中咨数据有限公司RPA项目

九科Ninetech

动态规划-编辑距离-两字符串集合重排序

alexgaoyh

重排序 动态规划 编辑距离 文本对齐 编辑距离变化过程

ARTS 打卡第二周

直须

个人成长 前端 ARTS 打卡计划

业财融合背景下,全面预算管理的发展之路

智达方通

业财融合 全面预算管理 全面预算管理系统 企业全面预算管理

HoudahSpot最新中文版+补丁安装教程

胖墩儿不胖y

Mac软件 文件搜索 搜索工具 搜索软件

高效数据传输与管理利器:镭速传输方案助力企业提升效率与安全

镭速

数据传输 分发数据 管理数据 镭速数据传输

购买矿机产出代币模式系统开发搭建

V\TG【ch3nguang】

代币 挖矿矿池系统开发案例

基于云原生网关的流量防护实践

阿里巴巴云原生

阿里云 云原生

使用EF Core更新与修改生产数据库

高端章鱼哥

EF Core .net6

隐语小课|私有信息检索(PIR)及其应用场景

隐语SecretFlow

AI 数据安全 隐私计算 开源社区 数据要素

关于工厂数字孪生应用实例的解析

3DCAT实时渲染

数字孪生 实时渲染

10倍性价比,万物新生基于 StarRocks 无缝直替 Trino

StarRocks

数据库 数据仓库 StarRocks trino

BetterZip 5中文下载+BetterZip 5注册码

mac大玩家j

Mac软件 解压缩工具 压缩软件

避坑PCB的常见设计问题

华秋电子

PCB

Footprint Analytics 与 GasZero 达成合作,将打造 “0 Gas” 区块链生态系统的未来

Footprint Analytics

区块链 web3

一劳永逸,解决.NET发布云服务器的时区问题

互联网工科生

.net 云服务器 时区

钱包量化多币种质押挖矿系统开发合约源代码详情

V\TG【ch3nguang】

钱包系统开发 质押挖矿

浪潮信息 KeyarchOS 助力 IT 企业安全管理业务完成 CentOS 迁移替换 | 龙蜥案例

OpenAnolis小助手

开源 操作系统 IT 浪潮信息 龙蜥案例

ARTS 打卡第二周

直须

个人成长 前端 ARTS 打卡计划

mysql基础——认识索引

树上有只程序猿

MySQL 索引

说点大实话丨知名技术博主 Kirito 测评云原生网关

阿里巴巴云原生

阿里云 微服务 云原生

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