logo标签列表

JavaScript中的Sleep函数 - 不使用递归

javascriptjqueryrecursionsleep
3
首先，我查看了所有与“睡眠”有关的问题（例如JavaScript版本的sleep()是什么？），但我没有找到可接受的解决方案。
我想制作一个适用于各种算法的视觉教育工具。为此，我使用JavaScript和jQuery来显示数据并美化它。为了启动它，我想做一个排序示例，其中显示一个数组，然后以视觉上令人愉悦的方式进行洗牌和排序。所以我想发生的是两个单元格被突出显示（容易），可能交换（容易），然后在测试下一对之前有一个小延迟（困难）。
我知道JavaScript中没有显式的“sleep”方法。但是，将代码重构为使用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“扩展”实现了类似于sleep的语法，显然比以上所有方法都要好。 感谢您的帮助！

为什么你不能只是使用 https://dev59.com/jnNA5IYBdhLWcg3wdtpd 中的方法？为什么这是不可接受的？ - JoshNaro
1
@JoshNaro 好吧，对于那个问题的答案都是关于重写所有内容以使用setTimeout()，但这里的OP不愿意（尽管注定要）这样做。 - Pointy
"但在我心中的所有算法上这样做需要花费大量时间"。检测到反模式。在重复代码之前，应三思而行...现在你将把相同的代码添加到每个代码片段中，如果未来需要更新，你将需要修改每一个。如果我是你，我会首先重写整个代码。" - ajax333221
@ajax333221 您误解了我的意思。我有许多不同的算法，我都想要展示出来。这些并没有重复的代码，它们是完全不同的算法，我需要递归地重写它们。 - Gilthans
@Gilthans，当你完成这个工具后，能否在这里发布一个链接？我们很想看看它。 - Alexey Lebedev
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源代码，虽然匆忙编写，但可能还是有用的。
1
那看起来很漂亮 - 但我希望避免使用不同的编程语言。 这确实给了我一个想法。如果排序函数并没有立即显示结果，而是仅记录所需的操作以供稍后调用呢？这可能会奏效。我会尝试并报告结果。 - Gilthans
@Gilthans，你可以增强你现有的排序算法，使其能够将排序过程中所做的“移动”作为单独的列表输出。然后，在执行排序后，再“回放”这些移动。 - Pointy
@Gilthans，是的，那正是我的意思。Python只是一个例子，说明有时你可以避免完全修改算法。如果你在JavaScript中定义自己的数组类，并提供交换和比较方法，然后在内部记录它们，例如arr.gt(j-1, j)而不是arr[j-1]> arr[j]，你几乎可以做到同样的效果。 - Alexey Lebedev
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>
这太完美了！我不需要兼容性或其他任何东西，所以这非常适合。我遇到的更糟糕的问题是eclipse不再识别我的javascript，但我会找到解决方法的。 :) - Gilthans
这与https://dev59.com/jnNA5IYBdhLWcg3wdtpd中给出的代码有何不同？function pausecomp（millis） { var date = new Date（）; var curDate = null; do {curDate = new Date（）; } while（curDate-date <millis）; } - JoshNaro
1
@JoshNaro 它不会阻塞用户界面，也不会导致高 CPU 利用率。StratifiedJS 会自动将您的代码重写为 continuation-passing 风格。hold() 调用会转换为 setTimeout()。 - Alexey Lebedev
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);
}

因此，第一次操作立即运行，下一次在一秒钟后运行，第三次在总共两秒钟后运行，以此类推。
这种解决方案的好处是最小化代码重写：只需将循环内容包装在setTimeout中（它被包含在闭包中，其中包含您的循环变量），并在每个循环迭代后添加一行以增加interval。
1

我会使用setTimeout，我相信这是在客户端实现类似“sleep”功能的最接近方法。

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）。
这正是使用递归实现冒泡排序。只需将setTimeout替换为bubbleSort(i, j)即可。显然，这可以是一种解决方案（递归是图灵完备的），但并不总是一个好的解决方案。 - Gilthans
@Gilthans 这不是递归。setTimeout()注册一个回调函数，该函数被放置在队列中，并在计时器触发时执行。函数堆栈不会随时间增长而增加。这相当于在循环中调用函数。 - Tomalak
从程序员的角度来看，在循环中调用函数就是递归。我的问题从来不是性能，而是将所有算法重写为递归范式所需的额外工作。 - Gilthans
@Gilthans 在循环中调用函数并不是递归。这只是在循环中调用函数。就像在十行代码上调用函数十次一样，我相信你不会称之为“递归”。从函数内部调用自身才是递归，而我上面的代码并没有这样做。 - Tomalak
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接