使用 setTimeout 避免堆栈溢出 [英] Avoiding stack overflow by using setTimeout

问题描述

我在此处发现了以下问题:

<块引用>

以下递归代码将导致堆栈溢出，如果数组列表太大.你怎么能解决这个问题并仍然保留递归模式?

答案:

<块引用>

通过修改可以避免潜在的堆栈溢出nextListItem 函数如下:

var list = readHugeList();var nextListItem = function() {var item = list.pop();如果(项目){//处理列表项...setTimeout(nextListItem, 0);}};

<块引用>

堆栈溢出被消除，因为事件循环处理递归，而不是调用堆栈.当 nextListItem 运行时，如果 item 不是null，超时函数(nextListItem)被推送到事件队列并且函数退出，从而清除调用堆栈.当...的时候事件队列运行它的超时事件，下一个项目被处理并且一个计时器设置为再次调用 nextListItem.因此，该方法是从头到尾处理，没有直接递归调用，所以无论迭代次数如何，调用堆栈都保持清晰.

谁能给我解释一下:

1. 这个用例是否实用
2. 为什么长数组会导致堆栈溢出

解决方案

这只是 蹦床，这反过来又是的替代方案总拥有成本.

当你在 Javascript 中调用一个函数时，你会在调用堆栈中添加一个框架.该框架包含有关函数范围内的变量及其调用方式的信息.

在调用函数之前，调用栈是空的.

-------

如果我们调用函数foo，那么我们会在栈顶添加一个新的帧.

<代码>|富|-------

当 foo 执行完毕后，我们再次将帧从堆栈中弹出，再次将其留空.

现在，如果 foo 依次调用另一个函数 bar，那么我们需要在堆栈中添加一个新帧，而 foo> 正在执行.

<代码>|酒吧||富|-------

希望您能看到，如果一个函数递归调用自身，它会不断向调用堆栈的顶部添加新的帧.

<代码>|... ||下一个列表项 ||下一个列表项 ||下一个列表项 ||下一个列表项 |----------------

递归函数将不断添加帧，直到它们完成处理，或者超过调用堆栈的最大长度，从而导致溢出.

因为 setTimeout 是一个异步操作，它不会阻塞你的函数，这意味着 nextListItem 将被允许完成并且它的帧可以从调用堆栈中弹出——防止它生长.递归调用将使用 事件循环 来处理.

这种模式有用吗?调用堆栈的最大大小取决于您的浏览器，但它可以低至 1130.如果您想使用递归函数处理包含数千个元素的数组，那么您可能会冒着调用堆栈的风险.

Trampolines 使用类似的技术，但不是将工作卸载到事件循环，而是返回一个调用下一​​次迭代的函数，然后可以使用 while 循环管理调用(不影响堆栈).

var nextListItem = function() {var item = list.pop();如果(项目){//处理列表项...返回下一个列表项；}};while(recur = recur()) {}

I've found the following question here:

The following recursive code will cause a stack overflow if the array list is too large. How can you fix this and still retain the recursive pattern?

And the answer:

The potential stack overflow can be avoided by modifying the nextListItem function as follows:

var list = readHugeList();

var nextListItem = function() {
    var item = list.pop();

    if (item) {
        // process the list item...
        setTimeout( nextListItem, 0);
    }
};

The stack overflow is eliminated because the event loop handles the recursion, not the call stack. When nextListItem runs, if item is not null, the timeout function (nextListItem) is pushed to the event queue and the function exits, thereby leaving the call stack clear. When the event queue runs its timed-out event, the next item is processed and a timer is set to again invoke nextListItem. Accordingly, the method is processed from start to finish without a direct recursive call, so the call stack remains clear, regardless of the number of iterations.

Can somebody please explain to me:

1. whether this use case is ever practical
2. why long array can cause stack overflow

解决方案

This is just a hacky alternative to trampolines, which in turn are just a hacky alternative to TCO.

When you call a function in Javascript, you add a frame to the call stack. That frame contains information about the variables in the scope of the function and how it was called.

Before we call a function, the call stack is empty.

-------

If we call function foo, then we add a new frame to the top of the stack.

| foo |
-------

When foo finishes executing, we pop the frame off the stack again, leaving it empty again.

Now, if foo in turn calls another function bar, then we'll need to add a new frame onto the stack, whilst foo is executing.

| bar |
| foo |
-------

Hopefully you can see that if a function calls itself recursively it keeps adding new frames to the top of the call stack.

| ...          |
| nextListItem |
| nextListItem |
| nextListItem |
| nextListItem |
----------------

Recursive functions will keep adding frames until either they finish processing, or they exceed the max length of the call stack, resulting in an overflow.

Because setTimeout is an asynchronous operation, it doesn't block your function, which means nextListItem will be allowed to finish and its frame can be popped off the call stack—preventing it from growing. The recursive call will be handled with the event loop instead.

Is this pattern ever useful? The max size for the call stack depends on your browser, but it can be as low as 1130. If you wanted to process an array with a few thousand elements using a recursive function, then you'd risk blowing the call stack.

Trampolines use a similar technique, but rather than offloading the work to the event loop, you return a function which calls the next iteration instead, then the calls can be managed with a while loop (which doesn't affect the stack).

var nextListItem = function() {
  var item = list.pop();

  if (item) {
    // process the list item...
    return nextListItem;
  }
};

while(recur = recur()) {}

这篇关于使用 setTimeout 避免堆栈溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！