我接觸過的前端數據結構與算法

前面已經分享了一篇JavaScript中的數據結構和算法學習,今天來學習這篇:我接觸過的前端數據結構與算法 我們已經討論過了前端與計算機基礎的很多話題,諸如SQL、面向對象、多線程,本篇將討論數據結構與算法,以我接觸過的一些例子做為說明。

1. 遞歸

遞歸就是自己調自己,遞歸在前端里面算是一種比較常用的算法。假設現在有一堆數據要處理,要實現上一次請求完成了,才能去調下一個請求。一個是可以用Promise,就像《前端與SQL》這篇文章里面提到的。但是有時候并不想引入Promise,能簡單處理先簡單處理。這個時候就可以用遞歸,如下代碼所示:
var ids = [34112, 98325, 68125];
(function sendRequest(){
    var id = ids.shift();
    if(id){
        $.ajax({url: "/get", data: {id}}).always(function(){
            //do sth.
            console.log("finished");
            sendRequest();
        });
    } else {
        console.log("finished");
    }
})(); 
上面代碼定義了一個sendRequest的函數,在請求完成之后再調一下自己。每次調之前先取一個數據,如果數組已經為空,則說明處理完了。這樣就用簡單的方式實現了串行請求不堵塞的功能。 再來講另外一個場景:DOM樹。 由于DOM是一棵樹,而樹的定義本身就是用的遞歸定義,所以用遞歸的方法處理樹,會非常地簡單自然。例如用遞歸實現一個查DOM的功能document.getElementById。
function getElementById(node, id){
    if(!node) return null;
    if(node.id === id) return node;
    for(var i = 0; i < node.childNodes.length; i++){
        var found = getElementById(node.childNodes[i], id);
        if(found) return found;
    }
    return null;
}
getElementById(document, "d-cal");
document是DOM樹的根結點,一般從document開始往下找。在for循環里面先找document的所有子結點,對所有子結點遞歸查找他們的子結點,一層一層地往下查找。如果已經到了葉子結點了還沒有找到,則在第二行代碼的判斷里面返回null,返回之后for循環的i加1,繼續下一個子結點。如果當前結點的id符合查找條件,則一層層地返回。所以這是一個深度優先的遍歷,每次都先從根結點一直往下直到葉子結點,再從下往上返回。 最后在控制臺驗證一下,執行結果如下圖所示: 5120ddb64940520f1b2f12d0503b2ef 使用遞歸的優點是代碼簡單易懂,缺點是效率比不上非遞歸的實現。Chrome瀏覽器的查DOM是使用非遞歸實現。非遞歸要怎么實現呢? 如下代碼:
function getByElementId(node, id){
    //遍歷所有的Node
    while(node){
        if(node.id === id) return node;
        node = nextElement(node);
    }
    return null;
}
還是依次遍歷所有的DOM結點,只是這一次改成一個while循環,函數nextElement負責找到下一個結點。所以關鍵在于這個nextElement如何非遞歸實現,如下代碼所示:
function nextElement(node){
    if(node.children.length) {
        return node.children[0];
    }
    if(node.nextElementSibling){
        return node.nextElementSibling;
    }
    while(node.parentNode){
        if(node.parentNode.nextElementSibling) {
            return node.parentNode.nextElementSibling;
        }
        node = node.parentNode;
    }
    return null;
}
還是用深度遍歷,先找當前結點的子結點,如果它有子結點,則下一個元素就是它的第一個子結點,否則判斷它是否有相鄰元素,如果有則返回它的下一個相鄰元素。如果它既沒有子結點,也沒有下一個相鄰元素,則要往上返回它的父結點的下一個相鄰元素,相當于上面遞歸實現里面的for循環的i加1. 在控制臺里面運行這段代碼,同樣也可以正確地輸出結果。不管是非遞歸還是遞歸,它們都是深度優先遍歷,這個過程如下圖所示。 6529742bce74e88f183dbf8c756580f 實際上getElementById瀏覽器是用的一個哈希map存儲的,根據id直接映射到DOM結點,而getElementsByClassName就是用的這樣的非遞歸查找。 上面是單個選擇器的查找,按id,按class等,多個選擇器應該如何查找呢?

2. 復雜選擇器的查DOM

如實現一個document.querySelector:
document.querySelector(".mls-info > div .copyright-content")
首先把復雜選擇器做一個解析,序列為以下格式:
//把selector解析為
var selectors = [
{relation: "descendant",  matchType: "class", value: "copyright-content"},
{relation: "child",       matchType: "tag",   value: "div"},
{relation: "subSelector", matchType: "class", value: "mls-info"}];
從右往左,第一個selector是.copyright-content,它是一個類選擇器,所以它的matchType是class,它和第二個選擇器是祖先和子孫關系,因此它的relation是descendant;同理第二個選擇器的matchType是tag,而relation是child,表示是第三個選擇器的直接子結點;第三個選擇器也是class,但是它沒有下一個選擇器了,relation用subSelector表示。 matchType的作用就在于用來比較當前選擇器是否match,如下代碼所示:
function match(node, selector){
    if(node === document) return false;
    switch(selector.matchType){
        //如果是類選擇器
        case "class":
            return node.className.trim().split(/ +/).indexOf(selector.value) >= 0;

        //如果是標簽選擇器
        case "tag":
            return node.tagName.toLowerCase() === selector.value. toLowerCase();

        default:
            throw "unknown selector match type";
    }
}
根據不同的matchType做不同的匹配。 在匹配的時候,從右往左,依次比較每個選擇器是否match. 在比較下一個選擇器的時候,需要找到相應的DOM結點,如果當前選擇器是下一個選擇器的子孫時,則需要比較當前選擇器所有的祖先結點,一直往上直到document;而如果是直接子元素的關系,則比較它的父結點即可。所以需要有一個找到下一個目標結點的函數:
function nextTarget(node, selector){
    if(!node || node === document) return null;
    switch(selector.relation){
        case "descendant":
            return {node: node.parentNode, hasNext: true};
        case "child":
            return {node: node.parentNode, hasNext: false};
        case "sibling":
            return {node: node.previousSibling, hasNext: true};
        default:
            throw "unknown selector relation type";
          //hasNext表示當前選擇器relation是否允許繼續找下一個節點
    }
}
有了nextTarge和match這兩個函數就可以開始遍歷DOM,如下代碼所示: 2e17e8041a10554a3aa164e99640620 最外層的while循環和簡單選擇器一樣,都是要遍歷所有DOM結點。對于每個結點,先判斷第一個選擇器是否match,如果不match的話,則繼續下一個結點,如果不是標簽選擇器,對于絕大多數結點將會在這里判斷不通過。如果第一個選擇器match了,則根據第一個選擇器的relation,找到下一個target,判斷下一個targe是否match下一個selector,只要有一個target匹配上了,則退出里層的while循環,繼續下一個選擇器,如果所有的selector都能匹配上說明匹配成功。如果有一個selecotr的所有target都沒有match,則說明匹配失敗,退出selector的for循環,直接從頭開始對下一個DOM結點進行匹配。 這樣就實現了一個復雜選擇器的查DOM。寫這個的目的并不是要你自己寫一個查DOM的函數拿去用,而是要明白查DOM的過程是怎么樣的,可以怎么實現,瀏覽器又是怎么實現的。還有可以怎么遍歷DOM樹,當明白這個過程的時候,遇到類似的問題,就可以舉一反三。 最后在瀏覽器上運行一下,如下圖所示: 337c5d78734bf049015e3789f1c13ea

3. 重復值處理

現在有個問題,如下圖所示: fd1b1dacd701276302a42a5f5dcbeed 當地圖往下拖的時候要更新地圖上的房源標簽數據,上圖綠框表示不變的標簽,而黃框表示新加的房源。 ?后端每次都會把當前地圖可見區域的房源返回給我,當用戶拖動的時候需要知道哪些是原先已經有的房源,哪些是新加的。把新加的房源畫上,而把超出區域的房源刪掉,已有的房源保持不動。因此需要對比當前房源和新的結果哪些是重復的。因為如果不這樣做的話,改成每次都是全部刪掉再重新畫,已有的房源標簽就會閃一下。因此為了避免閃動做一個增量更新。 把這個問題抽象一下就變成:?給兩個數組,需要找出第一個數組里面的重復值和非重復值。即有一個數組保存上一次狀態的房源,而另一個數組是當前狀態的新房源數據。找到的重復值是需要保留,找到非重復值是要刪掉的。 最直觀的方法是使用雙重循環。

(1)雙重循環

如下代碼所示:
var lastHouses = [];
filterHouse: function(houses){
    if(lastHouses === null){
        lastHouses = houses;
        return {
            remainsHouses: [], 
            newHouses: houses
        };  
    }   
    var remainsHouses = [], 
        newHouses = []; 

    for(var i = 0; i < houses.length; i++){
        var isNewHouse = true;
        for(var j = 0; j < lastHouses.length; j++){
            if(houses[i].id === lastHouses[j].id){
                isNewHouse = false;
                remainsHouses.push(lastHouses[j]);
                break;
            }   
        }   
        if(isNewHouse){
            newHouses.push(houses[i]);
        }   
    }   
    lastHouses = remainsHouses.concat(newHouses);
    return {
        remainsHouses: remainsHouses,
        newHouses: newHouses
    };  
}
上面代碼有一個雙重for循環,對新數據的每個元素,判斷老數據里面是否已經有了,如果有的話則說明是重復值,如果老數據循環了一遍都沒找到,則說明是新數據。由于用到了雙重循環,所以這個算法的時間復雜度為O(N2),對于百級的數據還好,對于千級的數據可能會有壓力,因為最壞情況下要比較1000000次。

?(2)使用Set

如下代碼所示:
var lastHouses = new Set();
function filterHouse(houses){
    var remainsHouses = [],
        newHouses = [];
    for(var i = houses.length - 1; i >= 0; i--){
        if(lastHouses.has(houses[i].id)){
            remainsHouses.push(houses[i]);
        } else {
            newHouses.push(houses[i]);
        }
    }
    for(var i = 0; i < newHouses.length; i++){
        lastHouses.add(newHouses[i].id);
    }
    return {remainsHouses: remainsHouses, 
            newHouses: newHouses};
}
老數據的存儲lastHouses從數組改成set,但如果一開始就是數組呢,就像問題抽象里面說的給兩個數組?那就用這個數組的數據初始化一個Set. 使用Set和使用Array的區別在于可以減少一重循環,調用Set.prototype.has的函數。Set一般是使用紅黑樹實現的,紅黑樹是一種平衡查找二叉樹,它的查找時間復雜度為O(logN)。所以時間上進行了改進,從O(N)變成O(logN),而總體時間從O(N2)變成O(NlogN)。實際上,Chrome V8的Set是用哈希實現的,它是一個哈希Set,查找時間復雜度為O(1),所以總體的時間復雜度是O(N). 不管是O(NlogN)還是O(N),表面上看它們的時間要比O(N2)的少。但實際上需要注意的是它們前面還有一個系數。使用Set在后面更新lastHouses的時候也是需要時間的:
for(var i = 0; i < newHouses.length; i++){
    lastHouses.add(newHouses[i].id);
}
如果Set是用樹的實現,這段代碼是時間復雜度為O(NlogN),所以總的時間為O(2NlogN),但是由于大O是不考慮系數的,O(2NlogN) 還是等于O(NlogN),當數據量比較小的時侯,這個系數會起到很大的作用,而數據量比較大的時候,指數級增長的O(N2)將會遠遠超過這個系數,哈希的實現也是同樣道理。所以當數據量比較小時,如只有一兩百可直接使用雙重循環處理即可。 上面的代碼有點冗長,我們可以用ES6的新特性改寫一下,變得更加的簡潔:
function filterHouse(houses){
    var remainsHouses = [],
        newHouses = []; 
    houses.map(house => lastHouses.has(house.id) ? remainsHouses.push(house) 
                        : newHouses.push(house));
    newHouses.map(house => lastHouses.add(house.id));
    return {remainsHouses, newHouses};
}
代碼從16行變成了8行,減少了一半。

(3)使用Map

使用Map也是類似的,代碼如下所示:
var lastHouses = new Map();
function filterHouse(houses){
    var remainsHouses = [],
        newHouses = [];
    houses.map(house => lastHouses.has(house.id) ? remainsHouses.push(house)
			: newHouses.push(house));
    newHouses.map(house => lastHouses.set(house.id, house));
    return {remainsHouses, newHouses};
}
哈希的查找復雜度為O(1),因此總的時間復雜度為O(N),Set/Map都是這樣,代價是哈希的存儲空間通常為數據大小的兩倍

(4)時間比較

最后做下時間比較,為此得先造點數據,比較數據量分別為N = 100, 1000, 10000的時間,有N/2的id是重復的,另外一半的id是不一樣的。用以下代碼生成:
var N = 1000;
var lastHouses = new Array(N);
var newHouses = new Array(N);
var data = new Array(N);
for(var i = 0; i < N / 2; i++){
    var sameNumId = i;
    lastHouses[i] = newHouses[i] = {id: sameNumId};
}
for(; i < N; i++){
    lastHouses[i] = {id: N + i};
    newHouses[i] = {id: 2 * N + i};
}
然后需要?將重復的數據隨機分布,可用以下函數把一個數組的元素隨機分布:
//打散
function randomIndex(arr){
    for(var i = 0; i < arr.length; i++){
        var swapIndex = parseInt(Math.random() * (arr.length - i)) + i;
        var tmp = arr[i];
        arr[i] = arr[swapIndex];
        arr[swapIndex] = tmp;
    }
}
randomIndex(lastHouses);
randomIndex(newHouses);
Set/Map的數據:
var lastHousesSet = new Set();
for(var i = 0; i < N; i++){
    lastHousesSet.add(lastHouses[i].id);
}

var lastHousesMap = new Map();
for(var i = 0; i < N; i++){
    lastHousesMap.set(lastHouses[i].id, lastHouses[i]);
}
分別重復100次,比較時間:
console.time("for time");
for(var i = 0; i < 100; i++){
    filterHouse(newHouses);
}
console.timeEnd("for time");

console.time("Set time");
for(var i = 0; i < 100; i++){
    filterHouseSet(newHouses);
}
console.timeEnd("Set time");

console.time("Map time");
for(var i = 0; i < 100; i++){
    filterHouseMap(newHouses);
}
console.timeEnd("Map time");
使用Chrome 59,當N = 100時,時間為: for < Set < Map,如下圖所示,執行三次: 618e960d8969ed369e9870a2a352f6f 當N = 1000時,時間為:Set = Map < for,如下圖所示: e1d14a9c0278023012e01dd7429ab29 當N = 10000時,時間為Set = Map << for,如下圖所示: 11da72a746b57798e19905e709083be 可以看出,Set和Map的時間基本一致,當數據量小時,for時間更少,但數據量多時Set和Map更有優勢,因為指數級增長還是挺恐怖的。這樣我們會有一個問題,究竟Set/Map是怎么實現的。

4. Set和Map的V8哈希實現

我們來研究一下Chrome V8對Set/Map的實現,源碼是在chrome/src/v8/src/js/collection.js這個文件里面,由于Chrome一直在更新迭代,所以有可能以后Set/Map的實現會發生改變,我們來看一下現在是怎么實現的。 如下代碼初始化一個Set:
var set = new Set();
//數據為20個數
var data = [3, 62, 38, 42, 14, 4, 14, 33, 56, 20, 21, 63, 49, 41, 10, 14, 24, 59, 49, 29];
for(var i = 0; i < data.length; i++){
    set.add(data[i]);
}
這個Set的數據結構到底是怎么樣的呢,是怎么進行哈希的呢? 哈希的一個關鍵的地方是哈希算法,即對一堆數或者字符串做哈希運算得到它們的隨機值,V8的數字哈希算法是這樣的:
function ComputeIntegerHash(key, seed) {
  var hash = key;
  hash = hash ^ seed;  //seed = 505553720
  hash = ~hash + (hash << 15);  // hash = (hash << 15) - hash - 1;
  hash = hash ^ (hash >>> 12);
  hash = hash + (hash << 2);
  hash = hash ^ (hash >>> 4);
  hash = (hash * 2057) | 0;  // hash = (hash + (hash << 3)) + (hash << 11);
  hash = hash ^ (hash >>> 16);
  return hash & 0x3fffffff;
}
把數字進行各種位運算,得到一個比較隨機的數,然后對這個數對行散射,如下所示:
var capacity = 64;
var indexes = [];
for(var i = 0; i < data.length; i++){
    indexes.push(ComputeIntegerHash(data[i], seed) 
                      & (capacity - 1)); //去掉高位
}
console.log(indexes)
散射的目的是得到這個數放在數組的哪個index。 由于有20個數,容量capacity從16開始增長,每次擴大一倍,到64的時候,可以保證capacity > size * 2,因為只有容量是實際存儲大小的兩倍時,散射結果重復值才能比較低。 計算結果如下: 7aa726d1f765c949a0e587e822e2f2d 可以看到散射的結果還是比較均勻的,但是仍然會有重復值,如14重復了3次。 然后進行查找,例如現在要查找key = 56是否存在這個Set里面,先把56進行哈希,然后散射,按照存放的時候同樣的過程:
function SetHas(key){
    var index = ComputeIntegerHash(56, seed) & this.capacity;
    //可能會有重復值,所以需要驗證命中的index所存放的key是相等的
    return setArray[index] !== null 
              && setArray[index] === key;
}
上面是哈希存儲結構的一個典型實現,但是Chrome的V8的Set/Map并不是這樣實現的,略有不同。 哈希算法是一樣的,但是散射的時候用來去掉高位的并不是用capacity,而是用capacity的一半,叫做buckets的數量,用以下面的data做說明:
var data = [9, 33, 68, 57];
由于初始化的buckets = 2,計算的結果如下: e361bf14aa82919505f857b0cc61e63 由于buckets很小,所以散射值有很多重復的,4個數里面1重復了3次。 現在一個個的插入數據,觀察Set數據結構的變化。

(1)插入過程

a) 插入9

如下圖所示,Set的存儲結構分成三部分,第一部分有3個元素,分別表示有效元素個數、被刪除的個數、buckets的數量,前兩個數相加就表示總的元素個數,插入9之后,元素個數加1變成1,初始化的buckets數量為2. 第二部分對應buckets,buckets[0]表示第1個bucket所存放的原始數據的index,源碼里面叫做entry,9在data這個數組里面的index為0,所以它在bucket的存放值為0,并且bucket的散射值為0,所以bucket[0] = 0. 第三部分是記錄key值的空間,9的entry為0,所以它放在了3 + buckets.length + entry * 2 = 5的位置,每個key值都有兩個元素空間,第一個存放key值,第二個是keyChain,它的作用下面將提到。 652c6840a98a7614d618f3fd1c6c0a5

b) 插入33

現在要插入33,由于33的bucket = 1,entry = 1,所以插入后變成這樣: e9cd1efc4f90cdab71e2bb0c0f05312

c) 插入68

68的bucket值也為1,和33重復了,因為entry = buckets[1] = 1,不為空,說明之前已經存過了,entry為1指向的數組的位置為3 + buckets.length + entry * 2 = 7,也就是說之前的那個數是放在數組7的位置,所以68的相鄰元素存放值keyChain為7,同時bucket[1]變成68的entry為2,如下圖所示: 4c216373be6343b70c8215141b96a4b

d) 插入57

插入57也是同樣的道理,57的bucket值為1,而bucket[1] = 2,因此57的相鄰元素存放3 + 2 + 2 * 2 = 9,指向9的位置,如下圖所示: a9818662015500a5f7684792fb1baf3

(2)查找

現在要查找33這個數,通過同樣的哈希散射,得到33的bucket = 1,bucket[1] = 3,3指向的index位置為11,但是11放的是57,不是要找的33,于是查看相鄰的元素為9,非空,可繼續查找,位置9存放的是68,同樣不等于33,而相鄰的index = 10指向位置7,而7存放的就是33了,通過比較key值相等,所以這個Set里面有33這個數。76ecfeaa75153c9973dff2ba2df4728 這里的數據總共是4個數,但是需要比較的次數比較多,key值就比較了3次,key值的相鄰keyChain值比較了2次,總共是5次,比直接來個for循環還要多。所以數據量比較小時,使用哈希存儲速度反而更慢,但是當數據量偏大時優勢會比較明顯。

(3)擴容

?再繼續插入第5個數的時候,發現容量不夠了,需要繼續擴容,會把容量提升為2倍,bucket數量變成4,再把所有元素再重新進行散射。 ?Set的散射容量即bucket的值是實際元素的一半,會有大量的散射沖突,但是它的存儲空間會比較小。假設元素個數為N,需要用來存儲的數組空間為:3 + N / 2 + 2 * N,所以占用的空間還是挺大的,它用空間換時間。

(4)Map的實現

?和Set基本一致,不同的地方是,map多了存儲value的地方,如下代碼:
var map = new Map();
map.set(9, "hello");
生成的數據結構為: 1ba2ae1f730821a05433ffd088d5d2c 當然它不是直接存的字符串“hello”,而是存放hello的指針地址,指向實際存放hello的內存位置。

(5)和JS Object的比較

?JSObject主要也是采用哈希存儲,具體我在《從Chrome源碼看JS Object的實現》這篇文件章里面已經討論過。 和JS Map不一樣的地方是,JSObject的容量是元素個數的兩倍,就是上面說的哈希的典型實現。存儲結構也不一樣,有一個專門存放key和一個存放value的數組,如果能找到key,則拿到這個key的index去另外一個數組取出value值。當發生散列值沖突時,根據當前的index,直接計算下一個查找位置:
inline static uint32_t FirstProbe(uint32_t hash, uint32_t size) { 
  return hash & (size - 1);
}

inline static uint32_t NextProbe(
    uint32_t last, uint32_t number, uint32_t size) { 
  return (last + number) & (size - 1);
}
同樣地,查找的時候在下一個位置也是需要比較key值是否相等。 上面討論的都是數字的哈希,實符串如何做哈希計算呢?

(6)字符串的哈希計算

如下所示,依次對字符串的每個字符的unicode編碼做處理:
uint32_t AddCharacterCore(uint32_t running_hash, uint16_t c) {
  running_hash += c;
  running_hash += (running_hash << 10);
  running_hash ^= (running_hash >> 6);
  return running_hash;
}

uint32_t running_hash = seed;
char *key = "hello";
for(int i = 0; i < strlen(key); i++){
    running_hash = AddCharacterCore(running_hash, key[i]);
}
接著討論一個經典話題

5. 數組去重

如下,給一個數組,去掉里面的重復值:
var a = [3, 62, 3, 38, 20, 42, 14, 5, 38, 29, 42];

輸出
[3, 62, 38, 20, 42, 14, 5, 29];

方法1:使用Set + Array

如下代碼所示:
function uniqueArray(arr){
    return Array.from(new Set(arr));
}
在控制臺上運行: 2d45092515242370548d62b3f01ca3b 優點:代碼簡潔,速度快,時間復雜度為O(N) 缺點:需要一個額外的Set和Array的存儲空間,空間復雜度為O(N)

方法2:使用splice

如下代碼所示:
function uniqueArray(arr){
    for(var i = 0; i < arr.length - 1; i++){
        for(var j = i + 1; j < arr.length; j++){
            if(arr[j] === arr[i]){
                arr.splice(j--, 1);
            }
        }
    }
    return arr;
}
優點:不需要使用額外的存儲空間,空間復雜度為O(1) 缺點:需要頻繁的內存移動,雙重循環,時間復雜度為O(N2) 注意splice刪除元素的過程是這樣的,這個我在《從Chrome源碼看JS Array的實現》已做過詳細討論: e16839849dbed99003e9e7ae82c583b 它是用的內存移動,并不是寫個for循環一個個復制。內存移動的速度還是很快的,最快1s可以達到30GB,如下圖所示: 3015f3cd9df0a4f93a00fe7fb7eba90

方法3:只用Array

如下代碼所示:
function uniqueArray(arr){
    var retArray = [];
    for(var i = 0; i < arr.length; i++){
        if(retArray.indexOf(arr[i]) < 0){
            retArray.push(arr[i]);
        }
    }
    return retArray;
}
時間復雜度為O(N2),空間復雜度為O(N)

方法4:使用Object + Array

下面代碼是goog.array的去重實現: bafc0c1a61ce738366821c81fde3d91 和方法三的區別在于,它不再是使用Array.indexOf判斷是否已存在,而是使用Object[key]進行哈希查找,所以它的時間復雜度為O(N),空間復雜為O(N). 最后做一個執行時間比較,對N = 100/1000/10000,分別重復1000次,得到下面的表格: 21a67505c71548f76d65b9f837bc178 Object + Array最省時間,splice的方式最耗時(它比較省空間),Set + Array的簡潔方式在數據量大的時候時間將明顯少于需要O(N2)的Array,同樣是O(N2)的splice和Array,Array的時間要小于經常內存移動操作的splice。 ? 實際編碼過程中1、2、4都是可以可取的? ?方法1 一行代碼就可以搞定 ?方法2 可以用來添加一個Array.prototype.unique的函數 ?方法4 適用于數據量偏大的情況 上面已經討論了哈希的數據結構,再來討論下棧和堆

6. 棧和堆

(1)數據結構的棧

棧的特點是先進后出,只有push和pop兩個函數可以操作棧,分別進行壓棧和彈棧,還有top函數查看棧頂元素。棧的一個典型應用是做開閉符號的處理,如構建DOM。有以下html:
<html>
<head></head>
<body>
    <div>hello, world</div>
    <p>goodbye, world</p>
</body>
</html>
將會構建這么一個DOM: 264af5f8a20a85a7a20b55d5d30163c 上圖省略了document結點,并且這里我們只關心DOM父子結點關系,省略掉兄弟節點關系。 首先把html序列化成一個個的標簽,如下所示: 1 html ( 2 head ( 3 head ) 4 body ( 5 div ( 6 text 7 div ) 8 p ( 9 text 10 p ) 11 body ) 12 html) 其中左括號表示開標簽,右括號表示閉標簽。 如下圖所示,處理html和head標簽時,它們都是開標簽,所以把它們都壓到棧里面去,并實例一個HTMLHtmlElement和HTMLHeadElement對象。處理head標簽時,由于棧頂元素是html,所以head的父元素就是html。 ea359134baca34f74563ce919b58f6c 處理剩余其它元素如下圖所示: 485c412d3e9b61bfa11e865c8a080a8 遇到第三個標簽是head的閉標簽,于是進行彈棧,把head標簽彈出來,棧頂元素變成了html,所以在遇到第一個標簽body的時候,html元素就是body標簽的父結點。其它節點類似處理。 上面的過程,我在《從Chrome源碼看瀏覽器如何構建DOM樹》已經做過討論,這里用圖表示意,可能會更加直觀。

(2)內存棧

函數執行的時候會把局部變量壓到一個棧里面,如下函數:
function foo(){
    var a = 5,
        b = 6,
        c = a + b;
}
foo();
a, b, c三個變量在內存棧的結構如下圖所示: d8f53d38d18d45ea848a293126648e9 先遇到a把a壓到棧里面,然后是b和c,對函數里面的局部變量不斷地壓棧,內存向低位增長。??臻g大小8MB(可使用ulimit –a查看),假設一個變量用了8B,一個函數里面定義了10個變量,最多遞歸8MB / (8B * 10) = 80萬次就會發生棧溢出stackoverflow 這個在《WebAssembly與程序編譯》這篇文章里面做過討論。

(3)堆

?數據結構里的堆通常是指用數組表示的二叉樹,如大堆排序和小堆排序。內存里的堆是指存放new出來動態創建變量的地方,和棧相對,如下圖所示: ed30f5a89cdb55421f8ea09596383ad 討論完了棧和堆,再分析一個比較實用的技巧。

6. 節流

節流是前端經常會遇到的一個問題,就是不想讓resize/mousemove/scroll等事件觸發得太快,例如說最快每100ms執行一次回調就可以了。如下代碼不進行節流,直接兼聽resize事件:
$(window).on("resize", adjustSlider);
由于adjustSlider是一個非常耗時的操作,我并不想讓它執行得那么快,最多500ms執行一次就好了。那應該怎么做呢?如下圖所示,借助setTimout和一個tId的標志位: d9d50c7d19ee3263dbacd084d23c60d 最后再討論下圖像和圖形處理相關的。

7. 圖像處理

假設要在前端做一個濾鏡,如用戶選擇了本地的圖片之后,點擊某個按鈕就可以把圖片置成灰色的: 3273b60a588288988665da393f8c2ee 效果如下: 7eed2ba53635d7f069f1661a6add353 一個方法是使用CSS的filter屬性,它支持把圖片置成灰圖的:
img{
    filter: grayscale(100%);
}
由于需要把真實的圖片數據傳給后端,因此需要對圖片數據做處理。我們可以用canvas獲取圖片的數據,如下代碼所示:
<canvas id="my-canvas"></canvas>
JS處理如下:
var img = new Image();
img.src = “/test.jpg”; //通過FileReader等
img.onload = function(){
    //畫到canvas上,位置為x = 10, y = 10
    ctx.drawImage(this, 10, 10);
}

function blackWhite() {
    var imgData = ctx.getImageData(10, 10, 31, 30);
    ctx.putImageData(imgData, 50, 10);
    console.log(imgData, imgData.data);
}
這個的效果是把某張圖片原封不動地再畫一個,如下圖所示: 190b291be280529a4416b8712a1b4b3 現在對imgData做一個灰化處理,這個imgData是什么東西呢?它是一個一維數組,存放了從左到右,從上到下每個像素點的rgba值,如下圖所示: 819e38d0590297a8f96f09712ba05d4 這張圖片尺寸為31 * 30,所以數組的大小為31 * 30 * 4 = 3720,并且由于這張圖片沒有透明通道,所以a的值都為255。 常用的灰化算法有以下兩種: ?(1)平均值 Gray = (Red + Green + Blue) / 3 ?(2)按人眼對三原色的感知度:綠 > 紅 > 藍 Gray = (Red * 0.3 + Green * 0.59 + Blue * 0.11) 第二種方法更符合客觀實際,我們采用第二種方法,如下代碼所示:
function blackWhite() {
    var imgData = ctx.getImageData(10, 10, 31, 30);
    var data = imgData.data;
    var length = data.length;
    for(var i = 0; i < length; i += 4){
        var grey = 0.3 * data[i] + 0.59 * data[i + 1] + 0.11 * data[i + 2];
        data[i] = data[i + 1] = data[i + 2] = grey;
    }
    ctx.putImageData(imgData, 50, 10);
}
執行的效果如下圖所示: a7c1c02a1e8fc154eb7adf60632346a 其它的濾鏡效果,如模糊、銳化、去斑等,讀者有興趣可繼續查找資料。 還有一種是圖形算法

8. 圖形算法

如下需要計算兩個多邊形的交點: e1c5bed22acb7df42bd30cceb2ebf64 這個就涉及到圖形算法,可以認為圖形算法是對矢量圖形的處理,和圖像處理是對全部的rgba值處理相對。這個算法也多種多樣,其中一個可參考《A new algorithm for computing Boolean operations on polygons》 綜合以上,本篇討論了幾個話題:
  1. ? 遞歸和查DOM
  2. ? Set/Map的實現
  3. ? 數組去重的幾種方法比較
  4. ? 棧和堆
  5. ? 節流
  6. ? 圖像處理
本篇從前端的角度對一些算法做一些分析和總結,只列了一些我認為比較重要,其它的還有很多沒有提及。算法和數據結構是一個永恒的話題,它的目的是用最小的時間和最小的空間解決問題。但是有時候不用太拘泥于一定要最優的答案,能夠合適地解決問題就是好方法,而且對于不同的應用場景可能要采取不同的策略。反之,如果你的代碼里面動不動就是三四重循環,還有嵌套了很多if-else,你可能要考慮下采用合適的數據結構和算法去優化你的代碼。