今天讓我們來繼續聊一聊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)
/**
* 普通算法-forEach循環版
* @param {*} arr
* 耗時：21-24ms
*/
function searchByForEach(arr, value) {
let result = [];
arr.forEach((item,i) => {
if(item === value) {
result.push(i);
}
})
return result
}
/**
* 普通算法-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';
}
/**
* 散列表
* 以下方法會出現數據覆蓋的問題
*/
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線程幫我們去處理計算結果，最後將結果合併，通過worker的事件機制傳給瀏覽器，效果十分顯著。
總結對於複雜數組查詢，for/while性能高於forEach等數組方法
二分查找法的O(logn)是一種十分高效的算法。不過它的缺陷也很明顯：必須有序，我們很難保證我們的數組都是有序的。當然可以在構建數組的時候進行排序，可是又落到了第二個瓶頸上：它必須是數組。數組讀取效率是O(1)，可是它的插入和刪除某個元素的效率卻是O(n)。因而導致構建有序數組的時候會降低效率。
哈希表查找的基本用法及使用場景。
條件允許的話，我們可以用web worker來優化算法，讓其在後臺並行執行。
好啦，這篇文章雖然比較簡單，但十分重要，希望大家對搜索算法有更加直觀的認識，也希望大家有更好的方法，一起探討交流。