在对代码进行基准测试时，令我感到惊讶的是，递归变体比迭代方法要快。我的实现中是否存在缺陷（它们每个都将相同数量的元素迭代到相同的深度）？尽管我怀疑这些片段会影响性能，但它们在接触元素的顺序上并不完全相同。
递归深度优先方法
function iterate(current, depth) {
var children = current.childNodes;
for (var i = 0, len = children.length; i < len; i++) {
iterate(children[i], depth + 1);
}
}
iterate(parentElement, 0);
迭代广度优先前进
var stack = [{
depth: 0,
element: treeHeadNode
}];
var stackItem = 0;
var current;
var children, i, len;
var depth;
while (current = stack[stackItem++]) {
//get the arguments
depth = current.depth;
current = current.element;
children = current.childNodes;
for (i = 0, len = children.length; i < len; i++) {
stack.push({ //pass args via object or array
element: children[i],
depth: depth + 1
});
}
}
迭代广度优先后退方法
var stack = [{
depth: 0,
element: treeHeadNode
}];
var current;
var children, i, len;
var depth;
while (current = stack.pop()) {
//get the arguments
depth = current.depth;
current = current.element;
children = current.childNodes;
for (i = 0, len = children.length; i < len; i++) {
stack.push({ //pass args via object or array
element: children[i],
depth: depth + 1
});
}
}
我期望第二个代码段在JS中最快（不弹出数组），是否有机会进一步优化以提高迭代方法的性能？我认为部分缓慢是在对象中创建参数（即
{depth: depth+1,element: someElement}）。递归代码段更加直观和明确，可能会受益于ES6解释器中的尾递归。重复我自己，在JavaScript中迭代
tree数据结构是否比递归更有效？JSPerf比较代码片段
#1 楼
我会完全同意迭代应该比递归更快的想法，我已经在其他语言中多次看到这种效果的证明。但是，它很难阅读。但是，在这里，也许不是，至少基准测试似乎表明必要的对象创建超过了函数调用开销。为此，这两个基于您的示例说明了它是对象创建和数组操作会导致迭代方法的性能降低。这两个示例利用要迭代的对象来创建这些对象的链接列表。它的缺点是它修改了遍历的每个对象，因此除了说明性能差异之外，可能不是所希望的。
在误差范围内，这些方法的性能优于优化的递归算法。
宽度优先
// simulates operations for walking through tree using iteration
parentElement.depth = 0;
parentElement.next = null;
var children, i, len;
var depth;
current = parentElement;
while (current) {
depth = current.depth;
children = current.childNodes;
//removes this item from the linked list
current = current.next;
for (i = 0, len = children.length; i < len; i++) {
child = children[i];
child.depth = depth+1;
//place new item at the head of the list
child.next = current;
current = child;
}
}
深度优先
// simulates operations for walking through tree using iteration
parentElement.depth = 0;
parentElement.next = null;
var children, i, len;
var depth;
var current,last;
current = parentElement;
last = current;
while (current) {
children = current.childNodes;
for (i = 0, len = children.length; i < len; i++) {
child = children[i];
child.depth = current.depth+1;
child.next = null;
//place new item at the tail of the list
last.next = child;
last = child;
}
//removes this item from the linked list
current = current.next;
}
JSPerf比较
评论
\ $ \ begingroup \ $
jsperf中有几个全局变量（当前），这可能会影响性能。我不确定在节点顶部创建sll对用户是否公平，因为他们可能不希望树对象的下一个属性。
\ $ \ endgroup \ $
– megawac
2014年4月23日在2:44
\ $ \ begingroup \ $
全局变量与原始jsperf中的相同。我注意到对元素的修改是此方法的问题，并建议仅出于演示目的，因为我认为否则您无法击败递归方法的性能。函数堆栈远未进行优化，可以被用作堆栈的数组击败，并在上面创建新对象。
\ $ \ endgroup \ $
– AaronM
2014年4月23日在3:04
\ $ \ begingroup \ $
是的，可能是真的-我真的很惊讶您的迭代方法没有超越递归（即使在ie8中也是如此）。
\ $ \ endgroup \ $
– megawac
14-4-23在3:29
\ $ \ begingroup \ $
结果可能因实际代码而异，例如，此处的递归示例具有很少的局部变量，这减少了函数堆栈的开销。实际上正在处理每个节点的功能可能会拥有更多的开销。此开销可能足以在两个实现之间更改性能特征。此外，递归方法可能会使用更多的内存，因为递归深度会增加，并且这些局部变量无法被每次迭代重用。
\ $ \ endgroup \ $
– AaronM
2014年4月23日在3:33
#2 楼
这个问题已经有两年了，但是它出现在Google上，我没有找到满意的答案，所以就去了。递归版本很快，因为它唯一的开销就是函数呼叫。当递归比迭代慢时，通常是小的开销。但是，在这种情况下，迭代版本必须做很多额外的工作，因为数据处于递归形状。
要优化依赖于递归数据结构的任何代码的执行，您应该研究一下替换结构，或者在不可行的情况下，将数据缓存到数组中以加快迭代速度。如果不可能，那么递归可能是最好的选择。
评论
您是否尝试过使用Google Chrome浏览器的开发人员工具或类似工具对例程进行分析？那应该告诉您大部分时间都花在了哪里。v8开发人员提到的一个特别的性能难题是，通过添加/删除属性来更改对象的“形状”。他们发现，将属性设置为null会比只删除属性将其完全从对象中删除，从而改变其形状的速度要快得多。属性引用的对象可以通过两种方式进行垃圾回收，因此不会造成内存损失。
深度是什么？我看不到它有什么用，除了它在树中运行时加起来。
@JosephtheDreamer只是一个随机变量，比仅将一个状态变量传递给下一个操作使解决方案更有用。没有深入介绍操作，仅检查了内存，感谢您的建议
递归版本性能可能是由于编译器尾递归优化所致？ taylodl.wordpress.com/2013/06/07/…