JS基本搜索算法實現與170萬條數據下的性能測試
前言
今天讓我們來繼續聊一聊js算法，通過接下來的講解，我們可以了解到搜索算法的基本實現以及各種實現方法的性能，進而發現for循環，forEach，While的性能差異，我們還會了解到如何通過web worker做算法分片，極大的提高算法的性能。
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次穩定后的結果如圖：
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來優化算法，讓其在后臺并行執行。
好啦，這篇文章雖然比較簡單，但十分重要，希望大家對搜索算法有更加直觀的認識，也希望大家有更好的方法，一起探討交流。
