javascript中的睡眠功能 - 不使用递归

Question

首先,我已经看过所有"睡眠"问题(例如什么是睡眠的JavaScript版本？)？但我找不到可接受的解决方案.

我想为各种算法制作视觉教育工具.为了做到这一点,我正在使用带有jQuery的javascript来显示数据并很好地绘制它.为了启动它,我想做一个排序示例,其中一个数组被显示,洗牌,然后以一种视觉上令人愉悦的方式排序.所以我想要发生的是两个单元格突出显示(简单),可能交换(简单),然后在测试下一对(硬)之前有一个小延迟.

我知道javascript中没有明确的"睡眠"方法.但是,将代码重组为使用setTimeout意味着递归地重写我的所有算法,这是一个巨大的阻碍(尽管显然不是不可能).

作为示例问题,请查看冒泡排序示例:

function bubble_sort(arr){
    for(var i=0;i<arr.length;i++){
        for(var j=1;j<arr.length;j++){
            highlight(j-1);
            highlight(j);
            if(arr[j-1] > arr[j]){
                visible_swap(arr, j, j-1);
            }
            sleep(1000);
        }
    }
    exhibit_array(arr);
}

这显然可以递归地重写以使用setTimeout,但是在我考虑的所有算法上这样做会花费大量时间.我错过了什么吗？是否存在一种"简单"的方式来实现实现并随意安排睡眠？

编辑:我找到了两个解决方案:一个漂亮的解决方案和一个兼容的解决方案.漂亮的只适用于firefox,我担心,并且使用了精彩的yield语义(这里有一些示例解释:https://developer.mozilla.org/en/New_in_JavaScript_1.7).这实际上完美地解决了我的问题,因此:

function bubble_sort(arr){
    for(var i=0;i<arr.length;i++){
        for(var j=1;j<arr.length;j++){
            highlight(j-1);
            highlight(j);
            if(arr[j-1] > arr[j]){
                visible_swap(arr, j, j-1);
            }
            yield true;
        }
    }
    yield false;
}
var bubble = bubble_sort(arr)
function gen(){
    if(bubble.next()){
        setTimeout(gen, 500);
    }
    else{
        alert("Done!");
    }
}

这对我来说非常有用,但确实依赖于目前仅在firefox上支持的yield功能.请注意,要使其完全正常工作,您需要使用<script type ="text/javascript; version = 1.7">.然而,这是完美的.它本来可以用于无限的算法,如果需要的话,显示它们徒劳无功.

根据以下答案,我发现的第二个解决方案也有效:

function bubble_sort(arr){
    var q = new Array();
    for(var i=0;i<arr.length;i++){
        for(var j=1;j<arr.length;j++){
            q[q.length] = [ [highlight, j-1 ], [highlight, j] ];
            if(arr[j-1] > arr[j]){
                swap(arr, j, j-1);
                q[q.length] = [ [visible_swap, j, j-1] ];
            }
        }
    }
    return q;
}
function play(q, step){
    if(q.length == 0)
        return;
    clear_highlights();
    cmds = q.shift();

    for(ind in cmds){
        cmd = cmds[ind];
        f = cmd.shift();
        f.apply(null, cmd);
    }
    setTimeout(function(){ play(q, step); }, step);
}

这也有效.这在语法上非常麻烦,但绝对适用于所有浏览器.

在所有这些之后,似乎有javascript'扩展'实现类似睡眠的语法,这显然比上述所有更好.谢谢您的帮助!

Answer 1

最近我对sub-palindrome finder算法进行了可视化,它使用了setTimeout,并且不需要以递归形式重写算法.

看这个例子.

一般原则是建立一堆命令,用于冒泡排序,这是一组高亮和交换命令.然后你可以让一个函数每N毫秒运行一次,它从堆栈中获取一个命令并将其可视化.

commands = [
    ['highlight', 1, 5]
    ['swap', 1, 5]
    ['highlight', 3, 7]
    ...
];

setInterval(function() {
    var cmd = commands.shift();
    visualize(cmd);
}, 1300);

在我的问题中,finder算法是用Python编写的,由用户提供,我无法修改它.幸运的是,Python允许重载访问和比较运算符并记录算法所采取的每个操作.RecString类.在JavaScript中你不能这样做,但在你的情况下这不是问题,因为你可以修改原始算法.

如果你愿意,我可以给你发送JS源代码,它是用急速编写的,但无论如何都可能有用.