アルゴリズムの視覚化: 理解しにくいコードをゴッホの星空に描く

厳選記事 | 呉嘉楽

翻訳 | 黄年

校正 | フェン・チェン、ヤオ・ジアリン

マイク・ボストック

出典 | bost.ocks.org

この論文ではアルゴリズムに焦点を当てています。ただし、ここで説明する手法は、数式、動的システム、プロセスなど、より広範囲の問題領域に適用できます。基本的に、コードの理解が必要な場所ならどこでも。

では、なぜアルゴリズムを視覚化する必要があるのでしょうか? そもそもなぜ視覚化する必要があるのでしょうか? この記事では、視覚的に考える方法を説明します。

アルゴリズムは視覚化の魅力的な使用例です。アルゴリズムを視覚化するには、データをグラフに当てはめるだけでは不十分で、主要なデータセットも必要ありません。代わりに、動作を記述する論理的なルールが存在します。アルゴリズムの視覚化が珍しいのは、デザイナーがこの斬新な形式を試して、より効果的なコミュニケーションを図ることができるからかもしれません。これは彼らを研究する十分な理由です。

しかし、このアルゴリズムは、視覚化が単なるデータ内のパターンを見つけるツール以上のものであることを思い出させてくれます。視覚化は人間の視覚システムを活用して人間の知能を高めます。このようにして、重要な抽象的なプロセスやその他のことをよりよく理解するためにこれを使用することができます。

サンプリング

最初のアルゴリズムを説明する前に、まずそれが解決する問題を説明する必要があります。

ゴッホの「星月夜」

このスクリーンから放射される光（電磁放射）は空気中を伝わり、レンズによって焦点が合わされ、連続信号として網膜に投影されます。光信号を感知するには、空間内のさまざまなポイントで光の強度と周波数分布を測定して、光信号を個別のパルスに減らす必要があります。

この削減プロセスはサンプリングと呼ばれ、視覚にとって不可欠です。これは、画家が個別の筆使いを使ってさまざまな色を塗り、画像を形成するようなものと考えることができます (特に点描画法)。サンプリングは、実際にはコンピュータ グラフィックスの中心的な関心事です。たとえば、レイ トレーシングを使用して 3D シーンをラスタライズするには、光線をどこに照射するかを決定する必要があります。画像のサイズを変更する場合でもサンプリングが必要です。

相反する要因によりサンプリングが困難になる場合があります。一方では、サンプリング ポイントが隙間なく均等に分散されていることを確認する必要があり、他方では、繰り返しのサンプリングや定期的なサンプリングは避ける必要があります (そうしないと、エイリアシングが発生します)。写真を撮るときにピンストライプのシャツを着るべきでないのはこのためです。ストライプがカメラのセンサーのピクセルグリッドと共鳴し、モアレパターンが発生します。

画像出典: retinalmicroscopy.com

これは人間の網膜周辺の顕微鏡写真です。大きな錐体細胞は色を感知し、小さな桿体細胞は暗い場所での視力を向上させます。

人間の網膜には、光受容細胞の位置をサンプリングするための優れたソリューションが備わっています。細胞は網膜を密に均一に覆っていますが（視神経上の盲点を除く）、細胞の相対的な位置は不規則です。これは、細胞間の距離を最小に保ち、光受容体を無駄にする閉塞を回避するため、ポアソンディスク分布と呼ばれます。

しかし、ポアソンディスク分布を構築するのは難しいため、ミッチェルと呼ばれる単純な近似アルゴリズムが最適な候補となります。

これらの点からわかるように、最適な候補をサンプリングすると、満足のいくランダム分布が生成されます。これには欠点がないわけではありません。一部の領域ではサンプルが多すぎる (オーバーサンプリング) し、他の領域ではサンプルが足りない (アンダーサンプリング) ことがあります。しかし、これはかなり優れており、同様に重要なことに、実装が簡単です。

仕組みは次のとおりです:

新しいサンプルごとに、最適候補アルゴリズムは、灰色で表された固定数の候補サンプリング ポイントを生成します (ここでは、この数は 10 です)。各候補サンプリングポイントは、サンプリング領域から均一に選択されます。

最良の候補は赤で表示され、以前のすべてのサンプル (黒で表示) から最も遠いものです。各候補サンプリング ポイントから最も近いサンプルまでの距離は、関連する線と円で表されます。灰色または赤の円の内側には他のサンプルがないことに注意してください。すべての候補サンプリング ポイントが作成され、距離が測定された後、最適な候補サンプリング ポイントが新しいサンプルになり、残りの候補サンプリング ポイントは破棄されます。

▼コードは以下の通りです。

関数サンプル() {
  varbestCandidate、 bestDistance = 0 ;
  for(var i = 0 ; i <  候補数; ++i) {
   var c = [Math.random() * 幅、Math.random() * 高さ]、
 d =距離(findClosest(サンプル、c)、c);
   d >最適距離の場合
最適距離= d ;
ベスト候補= c ;
 }
  }
 bestCandidate を返します。
 }

上でアルゴリズムを説明したので、コードを目立たせておきます。 (また、この投稿の目的は、視覚化を通じてコードを学習してもらうことです)。しかし、いくつかの詳細を明らかにしておきます:

ここで、numCandidates は一度に生成される候補サンプリング ポイントの数を表します。このパラメータを使用すると、品質と速度をトレードオフできます。 numCandidates が小さいほど、アルゴリズムの実行速度が速くなります。逆に、numCandidates が大きいほど、アルゴリズムの実行速度は遅くなりますが、サンプリング品質は高くなります。

▼距離関数は単純な幾何学です:

関数距離(a, b) {
 vardx = a[0] - b[0],
 dy = a [1] - b [1];
 Math.sqrt(dx * dx + dy * dy) を返します。
 }

必要に応じて、ここでは平方根 (sqrt) を無視できます。これは単調な関数であり、最適な候補サンプリング ポイントの結果は変更されません。

findClosest 関数は、現在の候補サンプリング ポイントに最も近いサンプリング ポイントを返します。これは、既存のすべてのサンプル ポイントを反復するブルート フォース検索を使用して実行できます。あるいは、四分木検索アルゴリズムなどを使用して検索を高速化することもできます。ブルートフォース検索は実装が簡単ですが、非常に遅くなります (時間の複雑さが高すぎます)。加速方式ははるかに高速ですが、実装にはより多くの作業が必要です。

トレードオフについて言えば、アルゴリズムを使用するかどうかを決定するときは、それを単独で評価するのではなく、他のアプローチと比較します。実際のところ、実装の複雑さ、つまり実装にかかる時間と保守の難しさを考慮することは、パフォーマンスと品質を測定するのに役立ちます。

最も簡単な代替方法は均一ランダムサンプリングです。

関数サンプル() {
 [random() * 幅、random() * 高さ] を返します。
 }

次のようになります:

一様ランダムはかなり悪いです。深刻なアンダーサンプリングとオーバーサンプリングが発生しています。多くのサンプル ポイントが密集したり、重なり合ったりして、大きな空の領域が発生します (サンプリングあたりの候補サンプリング ポイントの数が 1 に設定されている場合、均一ランダム サンプリングは、最適な候補アルゴリズムの品質の下限も表します)。

サンプリング ポイントの分布によってサンプリング品質を識別することに加えて、最も近いサンプルの色に従って画像を着色することにより、さまざまなサンプリング戦略の下での視覚をシミュレートすることもできます。これは実際にはサンプル ポイントのボロノイ図であり、各セルは関連するサンプルによって色分けされています。

6667 個の均一ランダムサンプルを抽出した後の「星月夜」はどのように見えるでしょうか?

この方法の欠点も明らかです。サンプリング ポイントの不均一な分布により、サンプリング ポイントの不均一な分布から予想されるように、各ユニットのサイズが大きく異なります。詳細が著しく失われるのは、密なサンプリング ポイント (小さな単位) が十分に活用されていないためです。一方、まばらにサンプリングされたポイント (大きなセル) は、まれな色 (左下隅のピンクなど) を誇張することでノイズを発生させます。

それでは、最適な候補サンプルを見てみましょう。

ずっと良くなりました! セルはランダムに配置されていますが、サイズがより一貫しています。サンプル数 (6667) は同じままですが、均等に分散されるため、より多くの詳細が保持され、ノイズが少なくなります。目を細めて見ると、元の筆跡がほぼ判別できます。

ボロノイ図を使用すると、各セルをその面積に応じて色分けすることで、サンプル分布をより直感的に調べることができます。暗いセルは大きく、サンプリングがまばらであることを示します。明るいセルは小さく、サンプリングが密であることを示します。最良のパターンは、不規則なサンプリング位置を維持しながら、ほぼ均一な色を持ちます。 (細胞領域の分布を示すヒストグラムも便利ですが、ボロノイにはサンプリング位置も表示できるという利点があります)。

以下は、6667 個のサンプル ポイントの同じ非均一ランダム サンプリングです。

黒い点はサンプル ポイント間の大きなギャップであり、アンダーサンプリングによって生じた視覚的な局所的な欠陥である可能性があります。同じ数の最良の候補サンプルでは、​​セル領域の変動がはるかに少なく、したがって色がより一貫して表示されます。

最善の候補アルゴリズムよりも優れた結果を得ることができますか? はい! 別のアルゴリズムを使用すると、より優れたサンプル分布を生成できるだけでなく、このアルゴリズムはより高速です (線形時間)。少なくとも、最善の候補アルゴリズムと同じくらい簡単に実装できます。このアルゴリズムは任意の次元に拡張することもできます。

この驚異はブリッドソンのポアソン ディスク サンプリング アルゴリズムと呼ばれ、次のようになります。

このアルゴリズムの機能は明らかに他の 2 つとは異なり、サンプリング領域全体でランダムに新しいサンプリング ポイントを生成するのではなく、既存のサンプリング ポイントを最大限に活用して徐々に新しいサンプリング ポイントを生成します。これにより、その進行は、ペトリ皿内で細胞が分裂するのと同じような、準生物学的な様相を呈するようになります。サンプル ポイントが互いに近すぎないことに注意してください。これは、アルゴリズムによって実装されるポアソン ディスク分布を定義する最小距離制約です。

仕組みは以下のとおりです:

赤い点は「アクティブな」サンプリングポイントを示します。各反復では、すべてのアクティブなサンプリング ポイントのセットからランダム サンプルが選択されます。次に、選択されたサンプリング ポイントの周囲のリング内に、候補となるサンプリング ポイント (中空の黒い点で表される) がいくつかランダムに生成されます。リングは半径 r から 2r まで広がります。ここで、r はサンプル間の最小許容距離です。

既存のサンプリング ポイントから距離 r 以内の候補サンプリング ポイントは拒否されます。この「禁止ゾーン」は灰色で表示され、拒否される候補サンプリング ポイントと近くの既存のサンプリング ポイントが黒の線で接続されます。グリッドにより、各候補サンプリング ポイントの距離チェックが高速化されます。グリッド サイズ r/√2 により、各セルには最大 1 つのサンプリング ポイントが含まれ、チェックする必要がある隣接セルの数は固定されます。

候補のサンプリング ポイントが許容可能な場合は、新しいサンプリング ポイントとして追加され、新しいアクティブなサンプリング ポイントがランダムに選択されます。候補となるサンプリング ポイントのいずれも受け入れられない場合、選択されたアクティブなサンプリング ポイントは無効としてマークされます (色が赤から黒に変わります)。アクティブなサンプリング ポイントがなくなると、アルゴリズムは終了します。

領域が塗りつぶされたボロノイ図は、濃い青や薄い黄色のセルがなく、ポアソン ディスク サンプリング アルゴリズムが最良候補アルゴリズムよりも優れていることを示しています。

ポアソン ディスク サンプリングを使用した「Starry Night」では、詳細が最も多く保存され、ノイズが最も少なくなります。美しいローマのモザイクを思い出させます。

いくつかの例を見てきたので、アルゴリズムを視覚化する必要がある理由について簡単に考えてみましょう。

▼エンターテインメント

アルゴリズムを視覚化することは、私にとっては限りなく魅力的で、執着さえ感じます。特にランダム性が関係する場合。これは無理のある理由のように思えるかもしれませんが、楽しむことの価値を過小評価しないでください。また、これらの視覚化は、基礎となるアルゴリズムを理解していなくても魅力的ですが、アルゴリズムの重要性を把握することで、より深い理解が得られます。

▼指導

コードとアニメーションのどちらがより役立つと思いますか? 疑似コード (コンパイルされないコードの婉曲表現) はどうでしょうか? 正式な説明は明示的なドキュメントに必要ですが、視覚化によって直感的な理解が容易になります。

▼デバッグ

形式的な記述に基づいてアルゴリズムを実装したことがありますか? 難しいかもしれません! コードが何を実行しているかを確認できれば、生産性が向上します。 視覚化はテストの必要性を置き換えるものではありませんが、テストは主に障害を説明するためではなく、障害を検出するために使用されます。出力が正しく見えても、視覚化によって実装における予期しない動作が明らかになることがあります (優れた関連研究については、Bret Victor の Learnable Programming および Principles of Invention を参照してください)。

▼学習

自分自身で学びたいだけの場合でも、視覚化は深い理解を得るための優れた方法になります。教えることは最も効果的な学習方法の 1 つであり、視覚化を実装することは自分自身を教えることと同じです。小さくて忘れやすい詳細を記したコードを暗記するよりも、アルゴリズムを視覚的に見て覚える方が簡単だと思います。

シャッフル

シャッフルとは、一連の要素をランダムに並べ替えるプロセスです。たとえば、プレイする前にカードをシャッフルすることができます。優れたシャッフル アルゴリズムは偏りがなく、すべての順序が等しく発生する可能性があります。

フィッシャー・イェーツ・シャッフルは最適なシャッフル アルゴリズムです。 偏りがないだけでなく、線形時間で実行され、一定のスペースを使用し、実装も簡単です。

▼コードは以下の通りです——

関数シャッフル(配列) {
 varn =配列.length , t, i;
 一方で（n）{
 i = Math.random () * n-- | 0; // 0 ≤ i <  ん 
 t =配列[n];
   配列[n] = 配列[i];
   配列[i] = t;
  }
 配列を返します。
 }

上記はコードであり、以下は視覚的な説明です。

各線は数字を表し、小さい数字は左に傾き、大きい数字は右に傾きます。 (数字だけでなく、あらゆるセットをシャッフルできますが、この視覚的なエンコードは要素の順序を示すのに適しています。これは、Robert Sedgwick の Algorithms Implemented in C のソート視覚化からヒントを得ました。

アルゴリズムは配列を 2 つの部分に分割し、右半分はシャッフルされた領域 (黒で表示)、左半分はシャッフルされる領域 (灰色で表示) になります。各ステップで、左側の領域からランダムに要素が 1 つ選択され、シャッフルされて右側に移動され、シャッフルされた領域の要素数が 1 ずつ増加します。シャッフルされた領域に新しい要素のためのスペースを確保するために、左半分の元の順序を維持する必要はなく、アルゴリズムは要素を所定の位置に単純に入れ替えることができます。最終的にすべての要素がシャッフルされ、アルゴリズムは終了します。

フィッシャー・イェーツ法が優れたアルゴリズムだとしたら、悪いアルゴリズムとはどのようなものでしょうか?

▼これは——

 //そんなことはしないでください!
関数シャッフル(配列) {
 配列を返す。ソート(関数(a, b) {
    Math.random() - .5 を返します。// ಠ_ಠ
  });
 }

このメソッドは、ランダム比較関数を指定してソートを利用してカードをシャッフルします。比較器は要素の順序を定義します。引数 a と b (比較する配列内の 2 つの要素) を受け取り、a が b より小さい場合は 0 未満の値を返し、a が b より大きい場合は 0 より大きい値を返し、a と b が等しい場合は 0 を返します。ソート中にコンパレータが繰り返し呼び出されます。

array.sort に比較演算子を指定しない場合、要素は辞書順にソートされます。

ここで、コンパレータは -0.5 から +0.5 の間の乱数を返します。これがランダムな順序を定義していると仮定すると、ソートは要素をランダムにシャッフルし、適切なシャッフルを実行します。

残念ながら、この仮定は間違っています。ランダムなペアワイズ順序 (任意の 2 つの要素) では、要素セットのランダムな順序は確立されません。比較子は推移性に従う必要があります。つまり、a > b かつ b > c の場合、a > c となります。しかし、ランダム コンパレータはランダムな値を返すため、推移性が破られ、array.sort の動作が未定義になります。運が良ければうまくいくかもしれませんし、そうでないかもしれません。

なぜ悪いのでしょうか? 出力を視覚化することで、この質問に答えることができます。

このアルゴリズムが良くないもう一つの理由は、ソートに O(n lg n) の時間がかかり、O(n) しかかからない Fisher-Yates アルゴリズムよりも大幅に遅くなることです。しかし、速度の欠陥は偏差の欠陥よりも小さいです。

これはランダムに見えるかもしれないので、ランダムな比較器のシャッフルで十分だと結論付け、偏りに注意を払わなくなるかもしれません。しかし、見た目は誤解を招く可能性があります。人間の目にはランダムに見えても、実際にはランダムではないものがたくさんあります。

この欺瞞は、視覚化が魔法の杖ではないことを示しています。アルゴリズムを 1 回実行しただけでは、そのランダム性の品質を評価するのに効果的ではないことがわかっています。アルゴリズムの偏りとは何かという具体的な質問に対応する視覚化を慎重に作成する必要があります。

偏見を示すためには、まずそれを定義する必要があります。 1 つの定義は、シャッフル後のインデックス i にある配列要素が、シャッフル後にインデックス j にある確率に基づいています。アルゴリズムに偏りがない場合、シャッフルが終了した後、各要素が各インデックスに出現する確率は等しくなります。したがって、すべての i と j の確率は同じになります: 1/n (n は要素の数)。

これらの確率を解析的に計算するのは、使用されるソートアルゴリズムを正確に知る必要があるため困難です。しかし、経験的に計算するのは簡単です。デッキを何千回もシャッフルし、インデックス j の要素 i の出現回数を数えるだけです。この確率行列を効果的に表示するには行列プロットを使用します。

行列の列 (水平位置) はシャッフル前の要素のインデックスを表し、行 (垂直位置) はシャッフル後の要素のインデックスを表します。確率は色分けされています。緑のセルは正の偏差を表し、要素は偏りのないアルゴリズムから予想されるよりも頻繁に発生します。同様に、赤のセルは負の偏差を表し、要素は予想されるよりも頻繁に発生しません。

上記のように、Chrome のランダム コンパレータ シャッフルの結果は驚くほど平凡です。配列の一部は弱いバイアスしかかかっていません。ただし、対角線の下には強い正のバイアスが見られ、これは要素をインデックス i から i+1 または i+2 にプッシュする傾向があることを示しています。最初、真ん中、最後の行も奇妙な動作をしますが、これはおそらく Chrome が「3 つの中央値」クイック ソートを使用していることが原因です。

不偏フィッシャー・イェーツアルゴリズムは次のようになります。

経験的測定による少量のノイズを除けば、このマトリックスには目に見える規則性はありません。 （必要に応じて、追加の測定を行うことでノイズを低減できます。）

ランダムコンパレータシャッフルの動作はブラウザによって大きく異なります。ブラウザによって使用するソート アルゴリズムは異なり、ソート アルゴリズムによって (壊れた) ランダム コンパレータの動作が大きく異なります。 Firefox でのランダム コンパレータ シャッフルの結果は次のとおりです。

これは非常に偏りがありません。このマトリックスの強い緑の対角線で示されているように、結果の配列はほとんどシャッフルされていないことがよくあります。これは、Chrome のソートが Firefox のソートよりも「優れている」という意味ではなく、ランダム コンパレータ シャッフルを使用すべきではないという意味です。ランダムコンパレータは根本的に壊れています。

ソート

ソートはシャッフルの逆で、無秩序から秩序を作り出し、その逆も行います。これにより、ソートはより困難な問題となり、さまざまなトレードオフと制約に対するさまざまなソリューションを設計する必要があります。

最もよく知られているソートアルゴリズムの 1 つはクイックソートです。

クイックソートは、まずピボットを選択して配列を 2 つの部分に分割します。 左半分にはピボットより小さいすべての要素が含まれ、右半分にはピボットより大きいすべての要素が含まれます。配列が分割された後、クイックソートは左側と右側の部分で再帰的に実行されます。各セクションに要素が 1 つだけ含まれる場合、再帰は停止します。

パーティション分割操作により、配列のアクティブな部分に対してのみ単一の操作を実行できます。フィッシャー・イェーツ法が要素を入れ替えることでシャッフルされた領域を段階的に構築するのと同様に、パーティション操作はサブ配列の小さい部分 (左) と大きい部分 (右) を段階的に構築します。各要素にアクセスすると、その要素がピボットよりも小さい場合は小さい部分にスワップされ、ピボットよりも大きい場合は、パーティション操作は次の要素に移動します。

▼コードは以下の通りです——

関数クイックソート(配列, 左, 右) {
  if(左<  右- 1) {
   var pivot = left + right >> 1 ;
 pivot =パーティション(配列、左、右、ピボット);
   クイックソート(配列、左、ピボット);
   クイックソート(配列、ピボット + 1、右);
  }
 } 
  
関数パーティション(配列、左、右、ピボット) {
 varpivotValue =配列[ピボット];
 swap(配列、ピボット、--右);
  for(var i =左; i <  右; ++i) {
   if (配列[i] <  ピボット値) {
     swap(配列、i、左++);
    }
  }
 swap(配列、左、右);
 左に戻る;
 }

クイックソートには多くのバージョンがあります。上に示したものは最も単純ですが、最も遅いものでもあります。このバリエーションは教育目的には便利ですが、実際にはパフォーマンスを向上させるために、より複雑な実装が使用されます。

一般的な改善点は、「3 つの中央値」ピボット選択です。この選択では、最初、中央、最後の要素の中央値がピボットとして使用されます。これにより、実際の中央値に近いベンチマークが選択される傾向があり、左半分と右半分のサイズが似通って、再帰層が少なくなります。もう 1 つの最適化は、配列の小さな部分に対してクイック ソートから挿入ソートに切り替えることです。これにより、関数呼び出しのオーバーヘッドが軽減され、高速化される可能性があります。

特に巧妙なバリエーションの 1 つは、配列を 2 つの部分ではなく 3 つの部分に分割する Yaroslavskiy の 2 ベース クイックソートです。これは、Java および Dart のデフォルトのソート アルゴリズムです。

上記のソートおよびシャッフルのアニメーションには、イベントが時間にマッピングされるという優れた特性があり、アルゴリズムがどのように進行するかを簡単に観察できます。しかし、アニメーションは直感的である一方で、特に時折起こる奇妙なアルゴリズムの動作に焦点を当てたい場合には、見るのがイライラすることもあります。アニメーションは、行動パターンを観察するために私たちの記憶に大きく依存しています。アニメーションは、一時停止したり、時間をスクラブするコントロールによって改善されますが、すべてを一度に表示する静的な表示はさらに効果的です。目でスキャンする方が手動でスキャンするよりも高速です。

アニメーションを静的表示に変換する簡単な方法は、アニメーションからキーフレームを選択し、漫画のように順番に表示することです。キーフレーム間の冗長な情報を削除すると、スペースをより効率的に使用できます。表示が高密度になると、理解するためにより多くの研究が必要になる場合がありますが、目の動きが少なくなるため、より速くスキャンできます。

以下では、各行は再帰前の配列の状態を示しています。最初の行は配列の初期状態、2 行目は最初のパーティション操作後の配列、3 行目は最初のパーティションの左側と右側の部分が再度パーティション分割された後の配列、というように続きます。実際には、これは幅優先のクイックソートであり、左側と右側のパーティション操作が並行して実行されます。

前と同様に、各パーティション操作のベースラインは赤で強調表示されます。再帰の次のレベルでは、ピボットが灰色に変わることに注意してください。パーティション操作が完了すると、関連付けられたピボットは最終的なソート位置にあります。表示される合計深度は再帰の最大深度であり、クイックソートがどれだけ効率的に実行されるかを示します。入力とベンチマークの選択によって大きく異なります。

クイックソートのもう 1 つの静的表示は、密度は低いですが、おそらく読みやすく、各要素を色付きの線で表し、各連続スワップを表示します。 (この形式は、Aldo Cortesi のソート視覚化からヒントを得ました。) 値が小さいほど明るくなり、値が大きいほど暗くなります。

これまで、同じアルゴリズムの 3 つの異なる視覚的表現 (アニメーション、密な静的表現、疎な静的表現) を見てきました。それぞれの形式には、独自の長所と短所があります。アニメーションは見ていて楽しいですが、静的な視覚化により、急がずに詳細に検査することができます。まばらなプレゼンテーションの方が理解しやすいかもしれませんが、密なプレゼンテーションでは、詳細に加えてアルゴリズムの動作の「全体像」が示されます。

先に進む前に、クイック ソートと、もう 1 つのよく知られたソート アルゴリズムであるマージ ソートを比較してみましょう。

▼以下はマージソートのコードです——

関数 mergesort(配列) {
 varn = array.length 、 a0 =配列、 a1 =新しい配列(n);
  for(var m = 1 ; m <   n ; m < < = 1) {
   (var i = 0 ; i <   n ; i += m < <   1 ）{
     var左= i ,
右= Math.min (i + m, n)、
終了= Math .min(i + (m < <   1 ）、n);
     マージ(a0, a1, 左, 右, 終了);
    }
 i = a0 、 a0 = a1 、 a1 = i ;
  }
  if(配列=== a1) {
   (var i = 0 ; i <   n ;++i){
     配列[i] = a0[i];
    }
  }
 }
関数 merge(a0, a1, 左, 右, 終了) {
  for(var i0 =左、 i1 =右; 左<  終了; ++左) {
   もし(i0 <  右&& (i1 > = 終了 || a0[i0] < = a0[i1])) {
     a1[左] = a0[i0++];
    }それ以外 {
     a1[左] = a0[i1++];
    }
  }
 }

関連するアニメーションは次のとおりです。

コードやアニメーションから推測できるように、マージ ソートはクイック ソートとはまったく異なるソート手法を採用します。インプレースでスワップを実行して動作するクイックソートとは異なり、マージソートでは配列の追加コピーが必要です。この余分なスペースは、順序を維持しながらサブ配列の要素の各ペアを結合し、サブ配列をマージソートするために使用されます。マージソートはスワップではなくコピーを実行するため、それに応じてアニメーションを変更する必要があります (そうしないと、読者を誤解させるリスクがあります)。

マージソートは下から上に実行されます。最初は、サイズ 1 のサブ配列がソートされているので、それらをマージします。隣接する各サブ配列: 最初は要素のペアだけであり、追加の配列を使用してサイズ 2 のソートされたサブ配列にマージされます。次に、サイズ 2 の隣接するソート済みサブ配列がそれぞれ、サイズ 4 のソート済みサブ配列に結合されます。配列を通過するたびに、マージソートはソートされたサブ配列のサイズを 8、16 のように 2 倍にします。最終的に、この倍増により配列全体が組み込まれ、アルゴリズムは終了します。

マージ ソートは、クイック ソートのように再帰的にではなく、配列に対して繰り返しパスを実行し、各パスで入力に関係なくソートされるサブ配列のサイズが 2 倍になるため、静的なプレゼンテーションの設計が容易になります。各マージ後に配列の状態を表示するだけです。

私たちが見ているものについて少し考えてみましょう。ここでの目標は、特定のデータセットではなく、アルゴリズムの動作を研究することです。しかし、データはアルゴリズムの実行から得られるため、必然的にまだデータが存在します。つまり、派生データのタイプを使用してアルゴリズムの視覚化を分類できるということです。

▼レベル0/ブラックボックス

最も単純なクラスで、出力を表示するだけです。アルゴリズムの動作は説明されていませんが、正確性は検証できます。アルゴリズムをブラックボックスとして扱うことで、異なるアルゴリズムの出力を比較しやすくなります。ブラック ボックスの視覚化は、上に示したランダム オフセット マトリックス プロットなど、出力のより詳細な分析と組み合わせることもできます。

▼レベル1/グレーボックス

多くのアルゴリズム（すべてではありませんが）は、出力を段階的に構築します。プロセスが進むにつれて、プロセスの途中で出力を視覚化することで、アルゴリズムがどのように機能するかを理解し始めます。中間プロセスと最終出力は同じ構造を共有するため、新しい抽象化を導入することなく、より多くのことを説明できます。ただし、このタイプの視覚化では、アルゴリズムがなぜその動作を行うのかが説明されないため、答えよりも多くの疑問が生じます。

▼レベル2/ホワイトボックス

「なぜ？」という質問に答えるために、ホワイトボックスの視覚化では、アルゴリズムの内部状態と中間プロセスの出力を公開します。このタイプは解釈の可能性が最も高くなりますが、内部状態の意味と目的を明確に記述する必要があるため、読者に最も大きな負担がかかります。余分な複雑さによって読者が圧倒されるリスクがありますが、情報を階層化することでグラフィックをよりわかりやすくすることができます。最後に、内部状態は特定のアルゴリズムに大きく依存するため、このタイプの視覚化は通常、アルゴリズムの比較には適していません。

アルゴリズムを視覚化するという実際的な問題もあります。通常、コードをそのまま実行することはできません。コードをキャプチャして視覚化する方法が必要です (例については、この記事のソース コードを参照してください)。実行と視覚化をインターリーブする必要がある場合もありますが、これは再帰アルゴリズムのスタック状態をキャプチャする場合に特に困難です。 Esprima などの言語パーサーは、実行コードと視覚化コードを完全に分離し、コード検出を通じてアルゴリズムの視覚化を簡単に実現できます。

迷路生成

最後に取り上げる問題は迷路生成です。このセクションのすべてのアルゴリズムは、2D 長方形グリッドのスパニング ツリーを生成します。つまり、サイクルはなく、左下隅のルートから迷路内の他のすべてのセルへの唯一のパスがあります。

このような深いテーマで申し訳ありません。これらのアルゴリズムが、電気ネットワークに関する単純なゲーム以外ではなぜ役立つのか、私にはわかりません。しかし、そうであっても、視覚化の観点からは、非常に制約の多い同じ問題を非常に異なる方法で解決しているため、興味深いものです。

見ていてとても楽しいです。

ランダム ウォーク アルゴリズムは、迷路の最初のセルを左下隅に初期化します。次に、アルゴリズムは迷路を拡張できる可能性のあるすべての方法を追跡します (赤で表示)。各ステップで、これらの可能な拡張の 1 つがランダムに選択され、これが迷路の別の部分に再接続されない限り、迷路は拡張されます。

Bridon のポアソン ディスク サンプリング アルゴリズムと同様に、ランダム トラバーサルはリーディング エッジを維持し、フロンティアからランダムに選択して拡張します。したがって、両方のアルゴリズムは菌類のように有機的に成長するように見えます。

ランダム化された深さ優先トラバーサルは、非常に異なるパターンに従います。

毎回新しいランダム パスを選択する代わりに、アルゴリズムは常にランダムな方向に最も深いパス (ルートに最も長く戻るパス) を拡張します。したがって、ランダム化された深さ優先探索は、現在のパスが行き止まりの場合にのみ、迷路の前の分岐に分岐します。続行するには、新しいブランチを開始できるまでバックトラックします。この蛇のような探索により、分岐が大幅に少なくなり、曲がりくねった通路が長くなった迷路が完成します。

プリムのアルゴリズムは、最小全域木、つまり重み付きエッジを持つグラフの全域木のうち、合計の重みが最も低いものを構築します。 このアルゴリズムは、エッジの重みをランダムに初期化することでランダム スパニング ツリーを構築するために使用できます。

各ステップで、Prim のアルゴリズムは、既存の迷路に接続された最も重みの低いエッジ (潜在的な方向) を使用して迷路を拡張します。エッジがサイクルを形成する場合、そのエッジは破棄され、次に重みの低いエッジが考慮されます。

プリムのアルゴリズムは、要素に優先順位を付ける効率的なデータ構造であるヒープを使用して実装されることが多いです。 迷路に新しいセルが追加されると、接続エッジ (赤で表示) が山に追加されます。エッジは任意の順序で追加できますが、ヒープを使用すると、重みが最も低いエッジをすばやく削除できます。

最後に、非常に珍しい例を挙げます。

ウィルソンのアルゴリズムは、サイクル消去ランダムウォークを使用して、すべての可能な全域木の偏りのないサンプルである均一全域木を生成します。私たちが見た他の迷路生成アルゴリズムは、この美しい数学的特性を欠いています。

アルゴリズムは、任意の開始セルで迷路を初期化します。次に、新しいセルが迷路に追加され、ランダムウォークが開始されます（赤で表示）。既存の迷路に再接続するまで、ランダムウォークを続けます（白で概説されています）。ただし、ランダムウォークがそれ自体を交差させると、ランダムウォークが続く前に結果のサイクルが消去されます。

当初、初期のランダムウォークが小さな既存の迷路と再接続できない可能性があるため、アルゴリズムはイライラするほど遅いように思えるかもしれません。迷路が成長するにつれて、ランダムウォークは迷路と衝突する可能性が高くなり、アルゴリズムは大幅に高速化されます。

これらの4つの迷路生成アルゴリズムは、非常に異なる方法で機能します。ただし、アニメーションが終了すると、結果として生じる迷路は互いに区別できません。アニメーションは、アルゴリズムがどのように機能するかを示すのに役立ちますが、結果のツリー構造を表示することはできません。

プロセスではなく構造を示す1つの方法は、迷路を色で満たすことです。

カラーコードツリー深度 - 左下隅のルートに戻るパスの長さ。カラースケールは、ツリーの奥深くに移動するとサイクルがあります。 （これは伝統的な虹色のカラースケールではなく、名目上有害と見なされますが、キューブの虹は知覚されたパフォーマンスを改善する能力を持っています。）

迷路の構造をさらに強調し、壁を差し引くことで視覚ノイズを減らすことができます。下の画像では、各ピクセルは迷路を通るパスを表しています。上記のように、パスは深さで色付けされ、色は時間の経過とともに潮のように迷路の奥深くに流れ込みます。

結びついたシャツのような色の同心円は、ランダムトラバーサルが多くの分岐経路を生成することを明らかにしています。ただし、各パスの形状は、直線でルートに戻る傾向があるため、特に興味深いものではありません。ランダムトラバーサルは、境界線からランダムにサンプリングすることで迷路を拡張するため、パスは蛇行する自由を与えられることはありません。最終的には、サイクルの制限のために成長する境界と衝突し、終了します。

一方、ランダム化された深さの最初のトラバーサルは、蛇行についてすべてです。

このアニメーションは、前のアニメーションの50倍で実行されます。迷路のランダムな深さfirstの横断は、分岐が制限されているため、ランダムトラバーサル迷路よりもはるかに深くなる可能性があるため、このスピードアップが必要です。ご覧のとおり、特定の深さには通常、アクティブな枝が1つだけで、めったに複数ありません。

以下では、Primのアルゴリズムがランダムグラフを使用して実証されています。

これははるかに興味深いものです。同時に拡張されている小花の色は、ランダムなトラバーサルが示唆するよりも複雑なグローバル構造があります。

ウィルソンのアルゴリズムは、非常に異なって動作しますが、非常によく似た結果を生み出しているようです。

彼らが同じように見えるからといって、彼らが同じであるという意味ではありません。同じように見えますが、Primのアルゴリズムは、ランダムに重み付けされたグラフに均一なスパンニングツリーを生成しません（私が知る限り、これは私の専門分野の外にあることを証明します）。視覚化は、人為的誤りのために誤解を招くことがあります。 Primの色の洪水の初期バージョンは、色のスケールが本来の2倍の速さで回転していることを示唆しています。

これらの迷路は木に及ぶため、特殊な木を使用して構造を視覚化することもできます。迷路と木の二重性を説明するために、ここではウィルソンのアルゴリズム（白で表示）によって生成された迷路の通路が徐々にきちんとした木のレイアウトに変換されます。他のアニメーションと同様に、それは深さから始まり、ルートから葉までさらに始まります。

比較のために、長い通路と小さな枝を持つ、ランダムな深さfirstのトラバーサルによって生成されたツリーを見てみましょう。

どちらの木にも同じ数のノード（3239）があり、同じ領域（960×500ピクセル）に合うようにスケーリングされています。これは重要な違いを隠しています。このサイズでは、ランダム化された深さfirstのトラバーサルは通常、ウィルソンのアルゴリズムよりも2〜5倍深い木を生成します。上の木の深さは、それぞれ315と1338です。色の洪水に使用されるはるかに大きな480,000ノードの迷路では、ランダム化された深さfirターストトラバーサル生成された木が10〜20倍深くなりました！

視覚的に考えてください

このペーパーでは、アルゴリズムに焦点を当てています。ただし、ここで説明する手法は、数学的式、動的システム、プロセスなど、より広い範囲の問題スペースに適用できます。基本的に、コードを理解する必要がある場所。

それで、

- なぜ何かを視覚化するのですか？

- 人間の視覚システムを使用すると、理解を深めることができます。または、より簡単に言えば、視覚的に考えてください。

出典：https：//bost.ocks.org/mike/algorithms/

[この記事は51CTOコラムBig Data Digest、WeChatパブリックアカウント「Big Data Digest（id: BigDataDigest）」のオリジナル翻訳です]