递归编程的性能

Question

如果数组列表太大，下面的递归代码将导致堆栈溢出。如何解决此问题并仍保留递归模式？

var list = readHugeList();
var nextListItem = function() {
var item = list.pop();
if (item) {
// process the list item...
nextListItem();
}
};

Answer 1

使用事件队列

在这种情况下，您可以轻松地将递归卸载到事件队列中。

var list = readHugeList();
var nextListItem = function() {
var item = list.pop();
if (item) {
console.log("processing", item);

// schedule the processing of the next list item
setTimeout(nextListItem);
}
};
nextListItem();

function readHugeList() {
return [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; //example
}

这是您可以做的最简单的事情 -setTimeout将安排再次调用nextListItem，但首先清除当前堆栈帧。这样，您就不会导致堆栈溢出，并且可以处理任意大的输入。

注意：这不会通过递归导致堆栈溢出，但是，它会很慢。问题是最小超时长度为 4ms，因此如果每次调用完成时间少于 4ms，则整个操作将花费更长的时间。例如，如果每个操作需要 4 毫秒，则通过setTimeout延迟将花费 4 倍的时间。即使删除了最小超时(例如在 Node.js 中或在 Node.js 中使用setImmediate)，它也会比其他替代方案更快但仍然慢 - 这仍将等待整个事件循环完成。虽然比强制的最短 4 毫秒等待更快，但它仍然是一个额外的开销。

但是，此方法确实允许在此期间发生其他事情，因此即使速度较慢，也可能是防止阻塞的合适实现。其中一个用途是创建增量更新。否则，它可能允许发生其他不相关的任务，因此它们不会延迟。因此，这是一种有用的技术，但可能不是最好的 - 如果你有一个足够大的数据集，你得到一个堆栈溢出，那么你肯定会遇到时间问题。

使用蹦床

另一种方法是使用蹦床。这基本上是尾部调用优化的手动实现。下面是一个示例实现：

function trampoline(fn) {
while (typeof fn === "function") {
fn = fn();
}
return fn;
};

这是基础知识的简单实现 - 它不考虑参数，但更好的实现可以。有蹦床的库实现，所以你不需要自己编写。

无论如何，蹦床还需要更改递归函数 - 它必须返回一个需要评估的结果，而不是返回结果。因此，这是它的工作原理：

var list = readHugeList();
var nextListItem = function() {
var item = list.pop();
if (item) {
console.log("processing", item);

// a thunk for the next list item
return () => nextListItem();
}
};
trampoline(nextListItem);

function trampoline(fn) {
while (typeof fn === "function") {
fn = fn();
}
return fn;
};
function readHugeList() {
return [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; //example
}

(注意：return () => nextListItem()也可以简单地按return nextListItem完成，但我想在这里明确说明)

蹦床将继续调用该函数，直到它停止返回更多要评估的 thunk。每个 thunk 本身都将包含对函数的递归调用。因此，您现在在通过fn()评估 thunk 时间接调用它，而不是直接调用函数自身。由于这是在循环中完成的，它仍然可以防止堆栈溢出具有非常深的嵌套递归。

第三个选项使用事件队列并作弊

好吧，这不是真正的作弊，但你可以给自己一个优势。如前所述，将递归委托给事件队列将解决堆栈溢出问题，但引入了速度问题，因为它对每个延迟操作施加了最小的延迟。为了演示这将如何影响性能，下面是一个示例：

var list = readHugeList();
var nextListItem = function() {
var item = list.pop();
if (item) {
console.log("processing", item);

// schedule the processing of the next list item
setTimeout(nextListItem);
} else {
console.log("operation took (in ms):", performance.now() - startTime)
}
};
var startTime = performance.now();
nextListItem();
function readHugeList() {
//generate an array of 100 sequential numbers
return Array.from({length: 100}, (_, i) => i);
}

递归浏览一百个项目的列表大约需要一秒钟(至少在我的机器上)。无论花费什么时间，它都太长了 - 一百个项目并不多，甚至不会首先导致调用堆栈溢出。我不会尝试使用可能导致溢出的数字，因为它可以工作，但等待它完成会非常长。

但是，您仍然可以通过微任务利用事件循环。一个非常快速的总结是，事件循环处理两种类型的任务

• 宏任务(如setTimeout设置的) - 它们的最小延迟为 4 毫秒，并且还允许发生其他事情，例如浏览器动画。
• 微任务 - 它们的优先级更高，没有任何最小延迟，只会尽快执行。

如果您卸载到微任务队列而不是宏任务队列，那么您将获得更快的处理速度。为此，您可以在浏览器中使用 Promise - 解析的承诺会将所需的任何进一步处理(使用.then添加的回调)添加到微任务队列中。

以下是其外观和行为：

var list = readHugeList();
var nextListItem = function() {
var item = list.pop();
if (item) {
console.log("processing", item);

// schedule the processing of the next list item
Promise.resolve()//resolve immediately
.then(nextListItem); //adds a microtask
} else {
console.log("operation took (in ms):", performance.now() - startTime)
}
};
var startTime = performance.now();
nextListItem();
function readHugeList() {
//generate an array of 10 000 sequential numbers
return Array.from({length: 10000}, (_, i) => i);
}

这大约需要一秒钟半(在我的机器上)。这与setTimeout相当，只是微任务版本处理的项目多两个数量级。那是 10 000 对只有 100。

Answer 2

您可以将递归调用移动到函数的末尾以进行尾部调用优化。

这将替换函数调用的返回值，并且不会增加堆栈。

var list = readHugeList();
var nextListItem = function() {
var item = list.pop();
if (!item) return;
// process the list item...
return nextListItem();
};

Answer 3

或者干脆像这样重写 ex.

var list = (function readHugeList() { return [3, 1, 4, 1, 5, 9, 2] })();
var nextListItem = function() {
do {
var item = list.pop();
if (item) {
// process the list item...
console.log("Processing item:", item);
continue;
}
} while (item);
};
nextListItem();