V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
yulanggong
V2EX  ›  JavaScript

Javascript 如何给一个深度递归(使用了setTimeout)设置完成后回调?

  •  
  •   yulanggong · 2012-09-28 15:15:07 +08:00 · 4141 次点击
    这是一个创建于 4450 天前的主题,其中的信息可能已经有所发展或是发生改变。
    因为递归太深而使用了异步的 setTimeout 清空调用栈,整个递归变成了异步的行为,怎么设置完成后的回调?

    简单的代码示例:

    var stackSize = 0;

    function foo(a){
    stackSize ++;

    bar();

    if (!a.length) return;

    if (stackSize > 1000) {
    stackSize = 0;
    setTimeout(function(){
    a.forEach(foo);
    },0);
    } else {
    a.forEach(foo);
    }
    }

    foo(hugeArray); //hugeArray 是一个多层嵌套的数组, 像这样 [[[...],[...]],[...]]
    14 条回复    1970-01-01 08:00:00 +08:00
    yulanggong
        1
    yulanggong  
    OP
       2012-09-28 15:26:22 +08:00
    怎么不能编辑了?

    这是上面的代码
    <script src="https://gist.github.com/3798444.js"> </script>
    yulanggong
        2
    yulanggong  
    OP
       2012-09-28 15:27:36 +08:00
    yulanggong
        3
    yulanggong  
    OP
       2012-09-28 15:30:39 +08:00
    haohaolee
        4
    haohaolee  
       2012-09-28 15:36:17 +08:00
    一个疑问,stackSize 真的能反映当前递归的深度吗?出函数的时候是不是要 stackSize-- 一下啊?
    另外,为什么要选择这么难以理解的解决方式呢,如果不是非要使用递归的话,可以用一个数据结构模拟栈或者别的神马嘛,比如树的遍历
    skyleft
        5
    skyleft  
       2012-09-28 15:39:31 +08:00
    使用全局变量
    yulanggong
        6
    yulanggong  
    OP
       2012-09-28 15:46:49 +08:00
    @haohaolee
    stackSize 的确是错的,因为 forEach 那会进入不同的分支。可以改为 stackSize 作为参数传给递归的函数用来分别统计。
    你能说说用数据结构模拟栈的思路吗?我没什么编程基础。
    chone
        7
    chone  
       2012-09-28 15:54:37 +08:00
    callback是不是要在所有遍历完成后调用,那样需要能逐级向上反馈完成的信号吧,这样在子级遍及没有完成前,父级需要被阻塞以等待信号。阻塞的实现好像也要用settimeout,父级和子级之间的通讯可以使用forEach的bind参数。

    不过这样的处理又复杂,效率又差。@haohaolee 说的比较靠谱。
    yulanggong
        8
    yulanggong  
    OP
       2012-09-28 17:02:57 +08:00
    @chone
    我搜了下非递归遍历,发现这可能是 @haohaolee 说得方式,我在琢磨怎么写代码。

    逐级汇报是一个思路,不过我还想不出怎么实现。

    我原来有个思路是在递归的函数里累加一个全局变量,然后定时轮询这个变量,变量在一段时间内没有变化时就是递归完成了,只是这样回调不太及时。
    haohaolee
        9
    haohaolee  
       2012-09-28 17:20:17 +08:00
    @yulanggong 我觉得你可以参考树遍历的方式,应该有很多资料。
    提供一个思路,设想有一个队列 q (javascript原生是否支持队列我不知道)
    1. 把a数组放进队列 2 若队列不为空循环处理队列: 取出队列头的元素,遍历该数组,若元素仍为数组则加入队列尾,若为非数组则直接处理
    skyleft
        10
    skyleft  
       2012-09-28 17:32:38 +08:00
    使用栈实现递归,类似树的非递归遍历,但是树的节点之间有指针链接,这里用两个栈。

    初始化两个栈S1,S2(js无,自己实现),s1存下标,s2存数组
    s1.push(0)
    s2.push(arr)
    while(s not empty){
    i=s1.pop();arri=s2.pop();
    循环arri,如果是元素,就访问它,如果还是数组,就将其在父数组中的下标压入栈S1,将父数组压入栈S2
    }
    shawiz
        11
    shawiz  
       2012-09-28 17:41:35 +08:00
    non-blocking 的 callback 可以用 jquery 的 deferred 来解决。
    比如:

    <script src="https://gist.github.com/3798898.js"> </script>
    shawiz
        12
    shawiz  
       2012-09-28 17:42:13 +08:00   ❤️ 1
    haohaolee
        13
    haohaolee  
       2012-09-28 18:51:41 +08:00
    @shawiz 没看懂这个例子,这个例子能做到所有的foo都结束的时候回调吗
    shawiz
        14
    shawiz  
       2012-09-29 14:43:23 +08:00   ❤️ 1
    @haohaolee 豆瓣上别人推荐了一篇关于 Javascript 异步的文章,值得一读,也许能解决你的疑问。我介绍的是 promise 方法。

    http://jimliu.net/?p=12
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3597 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 04:26 · PVG 12:26 · LAX 20:26 · JFK 23:26
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.