前端進階: 總結幾個常用的JS搜索算法和性能對比
前言
今天讓我們來繼續聊一聊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次穩定后的結果如圖：
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來優化算法，讓其在后臺并行執行。
好啦，這篇文章雖然比較簡單，但十分重要，希望大家對搜索算法有更加直觀的認識，也希望大家有更好的方法，一起探討交流。
