js基本搜索算法实现与170万条数据下的性能测试

徐小夕 等级 804 0 0

js基本搜索算法实现与170万条数据下的性能测试

前言

今天让我们来继续聊一聊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次稳定后的结果如图:

js基本搜索算法实现与170万条数据下的性能测试

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依赖IEnumerable。在运行时效率低于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去除字符串
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实践教程-02-javascript入门
本节目标1. 掌握如何编写javascript代码。2. 掌握javascript的3个弹框。3. 掌握javascript的注释。4. 掌握浏览器的调试工具控制台。 内容摘要本篇介绍了如何在网页上编写js代码,如何引入外部js代码文件,js的3个弹框、注释语法,还有浏览器调试工具的控制台使用。阅读时间1520分钟。 script标签如果我们需要在网页中编写
JS 折线图
JS 折线图  echarts 折线图。需要引入:echarts.min.js <script src="${ctxStatic}/common/echarts.min.js" charset="utf-8" type="text/javascript"></script> JS调用后台方法,得到数据 Map<String, Obj
JSON学习笔记(二、语法)
#### JSON和js关系 欲学JSON先学js,那么JSON和js的关系是什么样的呢? .JSON 使用 JavaScript 语法来描述数据对象,但是 JSON 仍然独立于语言和平台。 .JSON 语法是 JavaScript 语法的子集 #### 基本语法 .数据在名称/值对中 .数据由逗号分隔 .大括号保存对象 .中括号保
JS导出页面为PDF文件,该如何操作?来看一眼就明白啦!
废话不多说,直接上代码。 1.资源文件或依赖 <script type="text/javascript" src="https://my.oschina.net//u/4265132/blog/4054317/js/canvg2.js"></script><script type="text/javascript" src="https://m
JS的常用属性
JS-------定义:基于事件和对象驱动,并具有安全性能的脚本语言。 引入:<script  type=”text/javascript”>具体js代码</script> <script  type=”text/javascript” src=”js文件”></script> 大小写敏感:例如:A与a是两个不同的东东 注释://  单
Java序列化JSON时long型数值不准确
### 现象 项目中用到了唯一ID生成器.生成出的ID时long型的(比如说4616189619433466044). 通过某个rest接口中返回json数据后,发现浏览器解析完变成了4616189619433466000 ### 原因 大致描述:java中得long能表示的范围比js中number大,也就意味着部分数值在js中存不下(变成不准确的
java中ajax的用法简单案例
1.index.html <!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title>Insert title here</title> <script type="text/javascript" src="js/jquery-2.1.0.js">
Html5添加三联切换仿3D效果旋转木马jQuery插件教程
一、使用方法 <script type="text/javascript" src="js/jquery.min.js"></script> <script type="text/javascript" src="js/gallery.js"></script>    二、Html结构 <div id="wrapper"> <div id="mai
JQValidate使用说明
JQuery Validate使用总结: 一、导入js库 <script src="../js/jquery.js" type="text/javascript"></script> <script src="../js/jquery.validate.js" type="text/javascript"></script> 二、默认校验规则
JQuery
一、jq简介 jq其实就是js的一个文件。 二、jq书写步骤 1、先引入jq文件(min的文件) <script type="text/javascript" src="file:///C|/jquery/jquery-3.3.1.min.js"></script> 2、换新的一行写js代码 <script type="text/javascri
JavaScript八张思维导图
**![](https://oscimg.oschina.net/oscnet/17104907-a0f0-4b40-ac9d-9c40d9b13157.jpg)** **目录** * JS基本概念 * JS操作符 * JS基本语句 * JS数组用法 * Date用法 * JS
JavaScript学习笔记
JavaScript学习笔记 ============== 和HTML和CSS不一样,它是一门编程语言。 JS简介 ---- JS是一个客户端脚本语言,不需要编译,每一个浏览器都有JS的解析引擎。可以增强用户和HTML页面的交互,使网页产生动态。 JS的生成是在当时网速所限,必须在客户端就完成一些表单的校验等工作以减少客户端和服务器端的通信次数的实际
Javascript核心对象
JavaScript的实现包括以下3个部分: 1)核心(ECMAScript):描述了JS的语法和基本对象。 2)文档对象模型 (DOM):处理网页内容的方法和接口 3)浏览器对象模型(BOM):与浏览器交互的方法和接口 ECMAScript扩展知识: ① ECMAScript是一个标准,JS只是它的一个实现,其他实现包括ActionScript。
Springmvc异步上传文件
<script src="js/jquery.js" type="text/javascript"></script><script src="js/jquery.ext.js" type="text/javascript"></script><script src="js/jquery.form.js" type="text/javascript"