4

问题描述

今天去面试,题目是对一个对象中的value属性做遍历求和, 对象结构如下:

var nodes = {
    value: 1,
    children: [
        {
            value:2,
            children:[
                {
                    value:4,
                    children:[...]
                },
                {
                    value:3,
                    children:[...]
                }, 
                ...
            ]
        },
        {
            value:5,
            children:[...]
        },
        ...
    ]
}

我当时写的答案如下

function sum(node){
     if(node.children.length===0){
          return node.value
     }
     else{
          return node.children.reduce(
            (prev, curr) => prev + sum(curr),
             node.value
          )
    }
}
sum(nodes)

面试官说在数据量很大的情况下,用递归的性能会很差,所以这题不能用递归, 我思前想后都觉得需要用到递归, 最后只能请教面试官,被他批评说现在的程序员只会拍脑袋用递归,叫我回去看看DFS和BFS算法,但我看完后依然觉得需要用到递归,很苦恼,各路大神能否帮忙解答一下?

2019-09-06 提问
5 个回答
3

首先说一下BFS 广度优先搜索算法DFS 深度优先搜索算法
此题的两种搜索算法分别实现如下:

BFS

"use strict";

const sum = (nodes, result = 0) => {
  const stack = [nodes];
  while (stack.length) {
    const { value = 0, children } = stack.pop();
    result += value;
    if (children) stack.push(...children);
  }
  return result;
};

DFS

"use strict";

const sum = ({ value = 0, children = [] }) =>
  children.reduce((result, node) => result + sum(node), value);

区别

路径

递归下去,回溯上来,这就是DFS的简单逻辑。而BFS则是层层递进的逻辑。
所以如果结果是一个集合,那么集合中项的顺序是不同的。
此例中,结果是唯一求和值,所以2种算法对结果并无影响。

性能

由于路径的不同,将导致求和顺序的不同。但是,不管哪种算法,所经历项的总数是相同的

我们常常能看到一个普遍的结论是,BFS的性能要优于DFS。为什么会有这个结论呢?
首先,需要明白的是这2种算法的第3个字母S表示的是什么意思。S代表的是Search,所以这2种算法是针对搜索而言的,而搜索是无须遍历每一项的。如果数据离散度较高,那么使用BFS更能容易命中,而实际生活种,数据总是离散的,所以往往BFS要比DFS更快。
可是,如果只是更快,未必就是更好。而且考虑到遍历所有数据样本的情况,为什么仍然会有BFS优于DFS的结论呢?
要说这个,首先看一下这2种算法的实现。DFS是递归的方法,性能开销在于函数调用栈的出入栈BFS是队列的方法,性能开销在于内存申请,队列的出入。这是两者本质的区别。在不考虑内存限制的情况下,内存的操作会略快一点,但要视不同语言而定,但两者的差距并没有想象中的那么大。而在内存限制的情况下,其实BFS要增加额外的内存管理成本,反而得不偿失。
另一点在于,BFS因为有着第三者队列的存在,所以在多进程模型下,可以将队列分片,交由不同的进程处理。而DFS由于不知其深度,无法很好地平均分配,即使分片了,也仍然存在DFS的问题。

因此,结论往往是BFS要优于DFS

然而Javascript不一样!

虽然Javascript有办法做到多进程和多线程,但是其开销比静态语言要大的多。因为VM的执行机制,只有当其翻译到fork新进程的时候才会去优化代码和执行,所以会慢很多。而在浏览器端,虽然可以利于Worker做到多进程,但是其创建和通信的成本仍然巨大。所以就目前而言,BFS的多进程优势对于Javascript并不适用。
在此题中,因为结果是需要唯一确定的值,而且必须经历所有节点,所以BFSDFS的性能差异其实就是2种算法的性能开销的博弈。在ES6+之前,每次调用函数必须为函数创建额外的执行上下文,由于执行上下文是在函数执行时动态赋予的,所以在函数申明和定义时无法优化;但是ES6的箭头函数在函数定义时指定了上下文,因此避免了额外的开销。另外,ES6还有一个特性是尾调用优化(虽然目前只有Safari支持),但是尾调用优化的本质就是VM内部自动优化,避免了DFS出入栈问题。所以,对于Javascript更快。

不过,实践是检验的唯一标准,上面的都是理论,实际结果比理论更重要。
我在自己电脑上跑了一下,此题的DFS解法比BFS解法,在Chrome下要快1倍,在Safari下要快40%(看来V8还是厉害)。你也可以自己试验一下。

不要人云亦云,实践出真知,亲身实践比任何理论都有说服力。而且技术是不断进步的,如果理论只是维持不变,或者片面,总会被淘汰的。


最后,给些类递归的新奇解法吧。

Proxy
"use strict";

const proxy = (() => {
  const store = new WeakMap();

  return node => {
    if (store.has(node)) return store.get(node);

    const proxied = new Proxy(node, {
      get(target, key, receiver) {
        switch (key) {
          case Symbol.toPrimitive:
            return () =>
              receiver.children.reduce(
                (result, node) => result + node,
                target.value || 0
              );
          case "children": {
            const children = target[key];
            return Array.isArray(children) ? children.map(proxy) : [];
          }
          default:
            return target[key];
        }
      }
    });
    store.set(node, proxied);
    return proxied;
  };
})();

console.log(+proxy(nodes));

类似的,可以用ES5的getter实现。

JSON
"use strict";

const sum = eval(JSON.stringify(nodes).replace(/\D+/g, "+") + "0");
console.log(sum);

解决问题是唯一目标

我在面试时,往往会遇到一些令人哭笑不得但又确实很有效的解答。但只要解决问题就好啦,最实用的才是最好的。

就此题而言,可以看出,其value不管是在多深的层级,其实都是连续递增的。所以单就此题而言,完全可以变成求从1最大的value值的和。所以,只要找到最大的value值,就可以计算了,而不必遍历所有节点。

2

典型的层级遍历。与按层输出二叉树的节点思路相同。

var nodes = {
    value: 1,
    children: [
        {
            value:2,
            children:[
                {
                    value:4,
                },
                {
                    value:3,
                }, 
            ]
        },
        {
            value:5,
        },
    ]
}

function sum(nodes) {
    let s = 0;
    let level = [nodes];
    let nextLevel = [];
    while (level.length > 0) {
        for (let i = 0; i < level.length; i++) {
            s += level[i].value;
            if ("children" in level[i]) {
                nextLevel = nextLevel.concat(level[i].children);
            }
        }

        level = nextLevel;
        nextLevel = [];
    }

    return s;
}

console.log(sum(nodes));
1

首先说一下所有用递归可以解决的问题都可以用循环替代。

  • BFS:广度优先搜索
  • DFS:深度优先搜索

BFS 的重点在于队列,而 DFS 的重点在于递归。

namespace A {
  export interface Node {
    value: number,
    children: Array<Node>,
  };
}

const nodes: Array<A.Node> = [
  {
    value: 1,
    children: [
      {
        value: 2,
        children: [
          {
            value: 3,
            children: [],
          },
          {
            value: 4,
            children: [],
          },
        ],
      },
      {
        value: 5,
        children: [],
      },
      {
        value: 6,
        children: [
          {
            value: 7,
            children: [],
          },
        ],
      },
    ],
  },
  {
    value: 8,
    children: [
      {
        value: 9,
        children: [],
      },
      {
        value: 10,
        children: [],
      },
    ],
  },
];

function bfs(nodes: Array<A.Node>) {
  const queue = new Array(...nodes);
  const result = new Array();
  while(queue.length) {
    const node = queue.shift();
    result.push(node.value);
    queue.push(...node.children);
  }
  return result;
}

function dfs(nodes: Array<A.Node>) {
  const result = new Array();
  nodes.forEach(node => {
    result.push(node.value);
    result.push(...dfs(node.children));
  });
  return result;
}

console.log(`bfs:`, bfs(nodes));
console.log(`dfs:`, dfs(nodes));

运行结果:

bfs: [ 1, 8, 2, 5, 6, 9, 10, 3, 4, 7 ]
dfs: [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

从遍历顺序中可以看出来差别。

0

采用广度优先遍历。

function breadthFirstTraverse(nodes = {}) {
    let total = 0
    let curNode = null
    const queue = [nodes]
    while (queue.length) {
        curNode = queue.pop()
        total += curNode.value || 0
        if (curNode.children) {
            queue.push(...curNode.children)
        }
    }
    return total
}
0
  var nodes = {
    value: 1,
    children: [
      {
        value: 2,
        children: [
          {
            value: 3,
            children: [],
          },
          {
            value: 4,
            children: [],
          },
        ],
      },
      {
        value: 5,
        children: [],
      },
      {
        value: 6,
        children: [
          {
            value: 7,
            children: [],
          },
        ],
      },
    ],
  };

  function dfs(node) {
    var queue = [];
    queue.push({
      node: node,
      index: -1,
    });
    queue.last = function() {
      return this[this.length - 1];
    };
    let sum = 0;

    while (queue.length) {
      let last = queue.last();

      if (last.index === -1) {
        sum += last.node.value;
      }

      let children = last.node.children;
      
      if (children && children.length) {
        if (last.index >= children.length - 1) {
          queue.pop();
          continue;
        }
        queue.push({
          node: children[++last.index],
          index: -1,
        });
      } else {
        queue.pop();
      }
    }
  }

撰写答案

推广链接