获取对象的深度

一个对象，其实就是一棵树，对于一棵树而言，很多时候，我们可能想知道它到底有多深，因此，这里需要实现一个算法getDeeps，去获取一个对象的深度

分析

对于一个对象而言，其实就是大对象套用小对象，其实基本思路应该很简单，就是利用递归，计算出每一个子节点的深度，然后再加上1就OK了。比如对于数字、字符串、数组等，可能就没有深度，那么他们的深度可以理解为1，而对于实际的对象，那么可以再通过递推去计算。

存在问题

这么一看似乎没问题了，但是，如果处理不好，那就会存在一个致命的问题，那就是循环引用，如果一个子节点可能还会引用自己，那么如果通过简单的遍历就会进入死循环。所以需要去考虑循环引用。

代码实现

/**
 * 获取一个对象的深度
 * parents 为 true 说明需要考虑循环引用 否则不需要
 * @param {*} obj 
 */
function getDeeps(obj,parents) {
    if(parents == true) {
        parents = [];
    }
    if (obj && obj instanceof Object && !(obj instanceof Array) && (!parents || parents.indexOf(obj) < 0)) {
        let max = null;
        let flag = false;
        for (let key in obj) {
            let dep = getDeeps(obj[key],!parents ? parents : parents.concat(obj)) + 1;
            if (!flag) {
                flag = true;
                max = dep
            } else {
                max = max < dep ? dep : max;
            }
        }
        return max;
    } else {
        return 0;
    }
};
module.exports = getDeps;

这里引入了parents选项。当parents为true时表示需要考虑循环引用，否则代表不需要考虑循环引用。
这里面parents其实就是一个数组，记录了某个深度节点之前的所有的父节点。如此一来，便可以通过遍历parents来获知是否有循环引用。

是否要改进Array

问题似乎解决了，但是又似乎总有点不尽人意，因为每个节点都有一个与众不同的parents去维护自己的父节点。而parents是一个数组，indexOf相当于每次都需要经历一个平均是n/2的时间复杂度的遍历。那么是不是可以有办法改进呢?
似乎可以使用es6的map或者set，对于set而言，在插入时可能存在一定的性能问题，但是获取元素时会很快，具体可以参考这篇文章

这篇文章对set、Array的插入、获取性能做了对比，基本结果如下:

Array

image.png
Set
image.png
三行分别表示的是:

1. 插入 10000 * 1000 条数据消耗的时间。
2. 新插入一条数据消耗的时间
3. 获取某条数据消耗的时间

可以看到，Set的插入性能比Array低很多，但是读取性能却比Array快很多，几乎是瞬间的。
那么，对于Map呢，于是，做了一个同样的比较:

let s = new  Map();
let begin = new Date().getTime();
for(let i = 0; i < 10000 * 1000;i++) {
    s.set(i,true);
};
let end = new Date().getTime();
console.log(`消耗${end-begin}ms`);
begin = new Date().getTime();
s.set(10000 * 10000 - 1,true);
end = new Date().getTime();
console.log(`添加消耗${end-begin}ms`);
begin = new Date().getTime();
s.get(10000 * 10000 - 1);
end = new Date().getTime();
console.log(`判断消耗${end-begin}ms`);

结果如下:

image.png
可以看到，消耗的时间远远的多于Array和Set。

综合以上，其实使用Array或者Set是最合适的，对于需要大量查找的是Set更合适，但是，查找深度的时候，每一个子节点都需要相当于新建一个分支，生成一个新的Set,从Set的插入性能来看，是不合适的。因此，用Array是最合适的，不需要改进。