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

徐小夕
• 阅读 1139

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来优化算法,让其在后台并行执行。

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

接下来会推出更多优秀的算法,敬请期待哦~

更多推荐

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Jacquelyn38 Jacquelyn38
2年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Wesley13 Wesley13
2年前
Java获得今日零时零分零秒的时间(Date型)
publicDatezeroTime()throwsParseException{    DatetimenewDate();    SimpleDateFormatsimpnewSimpleDateFormat("yyyyMMdd00:00:00");    SimpleDateFormatsimp2newS
Stella981 Stella981
2年前
Android So动态加载 优雅实现与原理分析
背景:漫品Android客户端集成适配转换功能(基于目标识别(So库35M)和人脸识别库(5M)),导致apk体积50M左右,为优化客户端体验,决定实现So文件动态加载.!(https://oscimg.oschina.net/oscnet/00d1ff90e4b34869664fef59e3ec3fdd20b.png)点击上方“蓝字”关注我
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
2年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
2个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这