前端数据结构与算法

1.递归

递归就是自己调自己，递归在前端里面算是一种比较常用的算法。假设现在有一堆数据要处理，要实现上一次请求完成了，才能去调下一个请求。一个是可以用Promise，就像《前端与SQL》这篇文章里面提到的。但是有时候并不想引入Promise，能简单处理先简单处理。这个时候就可以用递归，如下代码所示：

var ids = [34112, 98325, 68125];
(function sendRequest(){
    var id = ids.shift();
    if(id){
		console.log(id);
		sendRequest();
    } else {
        console.log("finished");
    }
})(); 

//34112
//98325
//68125
//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符合查找条件，则一层层地返回。所以这是一个深度优先的遍历，每次都先从根结点一直往下直到叶子结点，再从下往上返回。
最后在控制台验证一下，执行结果如下图所示：

使用递归的优点是代码简单易懂，缺点是效率比不上非递归的实现。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.

在控制台里面运行这段代码，同样也可以正确地输出结果。不管是非递归还是递归，它们都是深度优先遍历，这个过程如下图所示。

实际上getElementById浏览器是用的一个哈希map存储的，根据id直接映射到DOM结点，而getElementsByClassName就是用的这样的非递归查找。

上面是单个选择器的查找，按id，按class等，多个选择器应该如何查找呢？

2. 复杂选择器的查DOM

如实现一个document.querySelector：

1	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，如下代码所示：

最外层的while循环和简单选择器一样，都是要遍历所有DOM结点。对于每个结点，先判断第一个选择器是否match，如果不match的话，则继续下一个结点，如果不是标签选择器，对于绝大多数结点将会在这里判断不通过。如果第一个选择器match了，则根据第一个选择器的relation，找到下一个target，判断下一个targe是否match下一个selector，只要有一个target匹配上了，则退出里层的while循环，继续下一个选择器，如果所有的selector都能匹配上说明匹配成功。如果有一个selecotr的所有target都没有match，则说明匹配失败，退出selector的for循环，直接从头开始对下一个DOM结点进行匹配。

这样就实现了一个复杂选择器的查DOM。写这个的目的并不是要你自己写一个查DOM的函数拿去用，而是要明白查DOM的过程是怎么样的，可以怎么实现，浏览器又是怎么实现的。还有可以怎么遍历DOM树，当明白这个过程的时候，遇到类似的问题，就可以举一反三。

最后在浏览器上运行一下，如下图所示：

重复值处理

现在有个问题，如下图所示：

当地图往下拖的时候要更新地图上的房源标签数据，上图绿框表示不变的标签，而黄框表示新加的房源。

后端每次都会把当前地图可见区域的房源返回给我，当用户拖动的时候需要知道哪些是原先已经有的房源，哪些是新加的。把新加的房源画上，而把超出区域的房源删掉，已有的房源保持不动。因此需要对比当前房源和新的结果哪些是重复的。因为如果不这样做的话，改成每次都是全部删掉再重新画，已有的房源标签就会闪一下。因此为了避免闪动做一个增量更新。

把这个问题抽象一下就变成：给两个数组，需要找出第一个数组里面的重复值和非重复值。即有一个数组保存上一次状态的房源，而另一个数组是当前状态的新房源数据。找到的重复值是需要保留，找到非重复值是要删掉的。

最直观的方法是使用双重循环。

（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
    };  
}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的时候也是需要时间的：

1
2
3

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};
}

掘金

掘金