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

徐小夕 等级 494 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基础 1. 用js打印一个乘法表 这一题面试官考察的是你关于js的打印相关基础api的熟悉程度,以及基本的数学常识,送分题 console.log( 111 212 224 313 326 339 414 428 4312 4416 515 5210 5315 5420 5525
js基本搜索算法实现与170万条数据下的性能测试
前言 今天让我们来继续聊一聊js算法,通过接下来的讲解,我们可以了解到搜索算法的基本实现以及各种实现方法的性能,进而发现for循环,forEach,While
项目实战之---AES 加密
ajax/index.js import axiosApi from '../js/fetch'; import { baseUrl, headerParams } from '../js/baseUrl'; // import引用AES源码js import CryptoJS from 'cryptojs/cryptojs'; console.lo
JavaScript基础加ES6语法
JavaScript 一、什么是JavaScript 当下最流行的脚本语言,在世界上的所有浏览器中都有js的身影,是一门脚本语言,可以用于我们与web站点和web应用程序的交互,还可以用于后台服务器的编写,例如node.js 二、语法特点 基于对象和事件驱动的松散型,解释型语言 单线程异步 三、JavaScript作用 页面的交
JS - typeof 与 instanceof
一、typeof typeof 操作符返回一个字符串,表示未经计算的操作数的类型 使用方法如下: typeof operand typeof(operand) operand表示对象或原始值的表达式,其类型将被返回 举个例子 typeof 1 // 'number' typeof '1' // 'string'
几个常用js库,别再重复造轮子了
年底了,总结下今年用到的一些有意思的《js轮子》(只是大概列出些比较有意思的库,每个标题都是超链接,可点击自行查阅) 希望能对您有用! 如有意思的 轮子 可以在评论列出一起讨论下 color(https://links.jianshu.com/go?tohttps%3A%2F%2Fwww.npmjs.com%2Fpackage%2Fco
前端面试题自检 JS CSS 部分
JS类型 JavaScript的简单数据类型Number , String , Boolean , Undefined , Null , Symbol typeof 操作符的返回值 number string boolean undefined object function
js异步的5种样式
js异步的5种样式 1.定时器 2.AJAX 3.Promise 4.Generator 5.asyns和awite  1.定时器     setTimeout() : 延时器        可以传入三个分别是            1)code:必
「组件」返回顶部按钮
样式如图1:在components文件夹下新建BackTop.vue js<template <div class"backTopBtn" <a href"javascript:;" <div vif"btnFlag" class"btn" @click"backTop"TOP</div
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
js删除表格中的某一行
点击表格中的内容,删除某一行正文js代码如下 function removeTd(obj) { obj.parentNode.parentNode.remove();}
只听说过CSS in JS,怎么还有JS in CSS?
CSS in JS是一种解决css问题想法的集合,而不是一个指定的库。从CSS in JS的字面意思可以看出,它是将css样式写在JavaScript文件中,而不需要独立出.css、.less之类的文件。将css放在js中使我们更方便的使用js的变量、模块化、treeshaking。还解决了css中的一些问题,譬如:更方便解决基于状态的样式,更容易追溯依赖关
秒懂js作用域与作用域链
JavaScript 中有一个被称为作用域(Scope)的特性。虽然对于许多新手开发者来说,作用域的概念并不是很容易理解,本文我会尽我所能用最简单的方式来解释作用域和作用域链,希望大家有所收获!好了下面开始我们的正文作用域常见的解释(什么是作用域)1. 一段程序代码中所用到的名字并不总是有效,而限定它的可用性的范围就是这个名字的作用域;2. 作用域规定了
从 生成器 到 promise+async
本文主要讲解js中关于生成器的相关概念和作用,以及到后面结合 promise 实现 es7中的 async 原理,你将学习到js中异步流程控制相关知识 1、认识生成器思考如下代码:javascript let x 1 function foo() x++ bar() console.log(x) // 3 function bar(
javascript实践教程-02-javascript入门
本节目标1. 掌握如何编写javascript代码。2. 掌握javascript的3个弹框。3. 掌握javascript的注释。4. 掌握浏览器的调试工具控制台。 内容摘要本篇介绍了如何在网页上编写js代码,如何引入外部js代码文件,js的3个弹框、注释语法,还有浏览器调试工具的控制台使用。阅读时间1520分钟。 script标签如果我们需要在网页中编写