前言

今天讓我們來繼續(xù)聊一聊js算法，通過接下來的講解，我們可以了解到搜索算法的基本實現(xiàn)以及各種實現(xiàn)方法的性能，進而發(fā)現(xiàn)for循環(huán)，forEach，While的性能差異，我們還會了解到如何通過web worker做算法分片，極大的提高算法的性能。

1.for循環(huán)搜索

基本思路：通過for循環(huán)遍歷數(shù)組，找出要搜索的值在數(shù)組中的索引，并將其推進新數(shù)組。

代碼實現(xiàn)如下：

const getFnRunTime = require('./getRuntime');

 /**
  * 普通算法-for循環(huán)版
  * @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次穩(wěn)定后的結(jié)果如圖：

2.forEach循環(huán)

基本思和和for循環(huán)類似：

/**
  * 普通算法-forEach循環(huán)版
  * @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循環(huán)(先暫且這么說哈，本質(zhì)也是如此)。

3.while循環(huán)

代碼如下：

/**
  * 普通算法-while循環(huán)版
  * @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循環(huán)性能差不多，都很優(yōu)秀，但也不是說forEach性能就不好，就不使用了。foreach相對于for循環(huán)，代碼減少了，但是foreach依賴IEnumerable。在運行時效率低于for循環(huán)。但是在處理不確定循環(huán)次數(shù)的循環(huán)，或者循環(huán)次數(shù)需要計算的情況下，使用foreach比較方便。而且foreach的代碼經(jīng)過編譯系統(tǒng)的代碼優(yōu)化后，和for循環(huán)的循環(huán)類似。

4.二分法搜索

二分法搜索更多的應(yīng)用場景在數(shù)組中值唯一并且有序的數(shù)組中，這里就不比較它和for/while/forEach的性能了。

基本思路：從序列的中間位置開始比較，如果當(dāng)前位置值等于要搜索的值，則查找成功;若要搜索的值小于當(dāng)前位置值，則在數(shù)列的前半段中查找;若要搜索的值大于當(dāng)前位置值則在數(shù)列的后半段中繼續(xù)查找，直到找到為止。

代碼如下：

/**
   * 二分算法
   * @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';
  }

在數(shù)據(jù)量很大的場景下，二分法效率很高，但不穩(wěn)定，這也是其在大數(shù)據(jù)查詢下的一點小小的劣勢。

5.哈希表查找

哈希表查找又叫散列表查找，通過查找關(guān)鍵字不需要比較就可以獲得需要記錄的存儲位置，它是通過在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系f，使得每個關(guān)鍵字key對應(yīng)一個存儲位置f(key)。

哈希表查找的使用場景：

• 哈希表最適合的求解問題是查找與給定值相等的記錄。
• 哈希查找不適合同樣的關(guān)鍵字對應(yīng)多條記錄的情況。
• 不適合范圍查找，比如查找年齡18~22歲的同學(xué)。

在這我先給出一個最簡版的hashTable，方便大家更容易的理解哈希散列：

/**
 * 散列表
 * 以下方法會出現(xiàn)數(shù)據(jù)覆蓋的問題
 */
function HashTable() {
  var table = [];

  // 散列函數(shù)
  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;
  }
}

該方法可能會出現(xiàn)數(shù)據(jù)沖突的問題，不過也有解決方案，由于這里涉及的知識點比較多，后期我會專門推出一篇文章來介紹：

• 開放定址法
• 二次探測法
• 隨機探測法

使用web worker優(yōu)化

通過以上的方法，我們已經(jīng)知道各種算法的性能和應(yīng)用場景了，我們在使用算法時，還可以通過web worker來優(yōu)化，讓程序并行處理，比如將一個大塊數(shù)組拆分成多塊，讓web worker線程幫我們?nèi)ヌ幚碛嬎憬Y(jié)果，最后將結(jié)果合并，通過worker的事件機制傳給瀏覽器，效果十分顯著。

總結(jié)

對于復(fù)雜數(shù)組查詢，for/while性能高于forEach等數(shù)組方法。

二分查找法的O(logn)是一種十分高效的算法。不過它的缺陷也很明顯：必須有序，我們很難保證我們的數(shù)組都是有序的。當(dāng)然可以在構(gòu)建數(shù)組的時候進行排序，可是又落到了第二個瓶頸上：它必須是數(shù)組。數(shù)組讀取效率是O(1)，可是它的插入和刪除某個元素的效率卻是O(n)。因而導(dǎo)致構(gòu)建有序數(shù)組的時候會降低效率。

哈希表查找的基本用法及使用場景。

條件允許的話，我們可以用web worker來優(yōu)化算法，讓其在后臺并行執(zhí)行。

好啦，這篇文章雖然比較簡單，但十分重要，希望大家對搜索算法有更加直觀的認識，也希望大家有更好的方法，一起探討交流。