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的事件机制传给浏览器，效果十分显著。

总结

对于复杂数组查询，for/while性能高于forEach等数组方法
二分查找法的O(logn)是一种十分高效的算法。不过它的缺陷也很明显：必须有序，我们很难保证我们的数组都是有序的。当然可以在构建数组的时候进行排序，可是又落到了第二个瓶颈上：它必须是数组。数组读取效率是O(1)，可是它的插入和删除某个元素的效率却是O(n)。因而导致构建有序数组的时候会降低效率。
哈希表查找的基本用法及使用场景。
条件允许的话，我们可以用web worker来优化算法，让其在后台并行执行。

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

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