3

まず第一に、横たわっているすべての「睡眠」の質問 ( sleep() の JavaScript バージョンとは?など) を調べましたが、受け入れられる解決策が見つかりませんでした。

あらゆる種類のアルゴリズムの視覚的な教育ツールを作成したいと考えています。そのために、jQuery で JavaScript を使用してデータを表示し、きれいに塗りつぶしています。それを開始するために、並べ替えのサンプルを実行したいと思います。ここでは、配列が表示され、シャッフルされ、視覚的に楽しい方法で並べ替えられます。私が実現したいのは、2 つのセルが強調表示され (簡単)、交換される可能性があり (簡単)、次のペアがテストされる前にわずかな遅延がある (難しい) ことです。

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 で動作するように再帰的に書き直すことができますが、私が考えているすべてのアルゴリズムでそうするには、かなりの時間がかかります。何か不足していますか？実装をそのままにして、自由にスリープを配置する「簡単な」方法はありますか?

編集:私は2つの解決策を見つけました.きれいなものと互換性のあるものです. 残念ながら、きれいなものは 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"> を使用する必要があることに注意してください。しかし、これは完璧です。また、無限のアルゴリズムに対しても機能し、必要に応じてそれらが無駄に苦労していることを示していた可能性があります.

以下の回答に基づいて、私が見つけた2番目の解決策も同様に機能します。

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

この回答は一般的なケースを解決するものではありませんが、各命令の間隔を増やして、互いに 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);
}

したがって、最初の操作は一度に実行され、次の操作は 1 秒後に実行され、3 番目の操作は合計 2 秒後に実行されます。

このソリューションには、コードの書き換えを最小限に抑えるという利点があります。ループの内容を でラップしsetTimeout(ループ変数でクロージャー内にラップされます)、interval各ループの反復後にインクリメントする行を追加するだけです。

于 2012-05-21T20:26:39.563 に答える
1

setTimeoutクライアント側で「スリープ」に相当するものに最も近いと思います。

于 2012-05-21T18:47:59.517 に答える
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 に答える