3

首先，我查看了所有的“睡眠”问题（例如What is the JavaScript version of sleep()?），但没有找到可接受的解决方案。

我想为各种算法制作一个视觉教育工具。为了做到这一点，我使用带有 jQ​​uery 的 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，并利用了美妙的产量语义（这里有一些示例解释：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“扩展”实现了类似睡眠的语法，这显然比上面所有的都好。谢谢您的帮助！

4

6 回答 6

6

最近我做了一个子回文查找算法的可视化，它使用了 setTimeout 并且不需要以递归形式重写算法。

请参阅此示例。

一般原则是建立一堆命令，对于冒泡排序，这将是一堆突出显示和交换命令。然后你可以让一个函数每 N 毫秒运行一次，它从堆栈中获取一个命令并将其可视化。

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

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

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

如果您愿意，我可以通过电子邮件将 JS 源代码发送给您，它是匆忙编写的，但无论如何可能会有用。

于 2012-05-21T19:00:49.727 回答
2

另一个想法 - StratifiedJS。这是一个简单的jsFiddle 示例：

<script src="http://code.onilabs.com/apollo/0.13/oni-apollo.js"></script>
<script type="text/sjs">
  for (var i = 1; i < 4; i++) {
      alert(i);
      hold(1000);
  }
</script>
于 2012-05-21T20:04:06.030 回答
1

我将与 合作setTimeout，我相信这是您在客户端最接近“睡眠”等效项的方式。

于 2012-05-21T18:47:59.517 回答
1

这个答案不能解决一般情况，但也许您可以增加每条指令的间隔，以便它们彼此运行一秒钟。

function bubble_sort(arr){
    var interval = 0;  // increases with each loop
    for(var i=0;i<arr.length;i++){
        for(var j=1;j<arr.length;j++){
            (function(i, j) {
                setTimeout(function() {
                    highlight(j-1);
                    highlight(j);
                    if(arr[j-1] > arr[j]){
                        visible_swap(arr, j, j-1);
                    }
                }, interval);
            })(i, j);
            interval += 1000;
        }
    }
    exhibit_array(arr);
}

因此，第一个操作立即运行，下一个操作在一秒后运行，第三个操作在总共两秒后运行，依此类推。

此解决方案提供了代码重写最少的好处：只需将循环内容包装在 a 中setTimeout（它与循环变量一起包装在闭包中）并interval在每次循环迭代后添加一行以递增。

于 2012-05-21T20:26:39.563 回答
0

使用setTimeout()不是递归。

您可以使用闭包来跟踪状态。for但是，必须将循环更改while为才能正常工作：

function bubbleSort(arr) {
  (function(i, j) { // <- this closes over i and j
    function nextSortStep() {
      while (i < arr.length) {
        while (j < arr.length) {
          highlight(j - 1);
          highlight(j);
          if (arr[j - 1] > arr[j]) {
            visibleSwap(arr, j, j - 1);
          }
          j++;
          return setTimeout(nextSortStep, 1000);
        }
        i++;
        j = 1;
        return setTimeout(nextSortStep, 1000);
      }
      exhibitArray(arr);
    }
    nextSortStep();
  })(0, 1); // <- loop initialization
}

顺便说一句，JavaScript 不是 PHP，函数名称通常在camelCase.

于 2012-05-21T19:35:52.607 回答
0

按照 Lebedev 的想法，我将存储“数组排序的演变”，然后使用 setInterval() 显示它们。 http://jsfiddle.net/mari/EaYRZ/

于 2012-05-21T20:13:37.463 回答