ジェネレータと React を利用したアルゴリズム可視化フレームワーク

概要

アルゴリズム を動かしたり止めたり 実行制御 しながら、リアルタイムに 可視化 できる 仕組み を、以前から作りたいと思っていた。JavaScript の ジェネレータ関数（ワーカースレッドで動作） によるアルゴリズムの記述方式と、表示内容が宣言的に記述できる React を組み合せる事で、アルゴリズム可視化フレームワーク を実現した。今回はシンプルかつ有名な ユークリッドの互除法 を例に、そのフレームワークの全体像を解説する。

デモ：ユークリッドの互除法 で、実際にフレームワークを試すことが出来ます。サンプルの初期値がセットされているので、何も考えずに スタートボタン を押せば動きます。もし何か不具合を発見した方は、ご報告を頂けると幸いです！！宜しくおねがいします。

目指すこと

機能

  • プラグインとか不要で、ブラウザだけ で手軽に実行できる
  • アルゴリズムを 中断・再開・ステップ実行 など、自由自在に動かせる
  • ヒストリー機能
    • 過去の実行結果を保持して、前後の結果に移動できる
  • 実行結果が 視覚的 に表示できる

設計

  • フレームワークとアルゴリズムが独立 している
    • → アルゴリズムの修正・変更したときの 影響が小さい
  • モダンな技術を利用
  • メインスレッド（ユーザインターフェイス）とは 別のスレッド で動作

技術的ポイント

アルゴリズムをジェネレータ関数で記述

アルゴリズムを JavaScript の ジェネレータ関数 として記述することで、アルゴリズムを 中断・再開など自在に制御 しつつ、途中の結果 が取得できるようになる。

下は ユークリッドの互除法 をジェネレータ関数を記述した例で、yield キーワードに到達すると、そこで途中の結果を返して、処理を一旦停止する。ジェネレータ関数から生成されるジェネレータでは、next() メソッドで次の yield まで、処理を一歩ずつ 進めることができる。

function* euclidean(m, n) {
  while (n !== 0) {
    yield { m, n }
    const r = m % n
    m = n
    n = r
  }

  yield { m, n }
}

const algo = euclidean(21, 13)
console.log(algo.next().value)
// → { m: 21, n: 13 }
console.log(algo.next().value)
// → { m: 13, n: 8 }

一方で、例えば for...of 文を使うと、途中結果の出力を繰り返しながら、アルゴリズムが 終了するまで一気 に実行できる。

for (const result of algo) {
  console.log(result)
}
$ node euclidean.js
{ m: 21, n: 13 }
{ m: 13, n: 8 }
{ m: 8, n: 5 }
{ m: 5, n: 3 }
{ m: 3, n: 2 }
{ m: 2, n: 1 }
{ m: 1, n: 0 }

ユーザインターフェイスを React で作成

React の大きな特徴は、表示内容が 宣言的に 記述できる事と言える。つまり 状態変数 に対して、「見た目はこのように出力する…」と表示内容を定義しておくと、React が 状態変数の変化を自動的に認識 して、画面出力の更新を全て面倒見てくれる。

const App = () => {
  // 状態変数: アルゴリズムの実行結果を保持する配列
  const [result, setResult] = useState([]);

  // アルゴリズムの処理
  // 実行結果を状態変数 result へ追記する

  // 宣言的記述
  // 状態変数の値（実行結果）を React Element（仮想 DOM）に変換
  const resultView = result.map((v, i) => (
    <p key={i}>
      m: {v.m}, n: {v.n}
    </p>
  ));

この特徴は非常に強力で、アルゴリズムの処理 と 出力結果の表示処理 が、きれいに分離して記述 できるようになる。例えばアルゴリズムの実装では、アルゴリズムの本質的部分だけに集中できるし、アルゴリズムを変更・修正する場合は、アルゴリズム以外では、表示出力の宣言的記述の部分だけ を変更すれば良い。

アーキテクチャ

アルゴリズム実行フレームワークは、下図左側のメインスレッドで動くユーザインターフェイス側と、右側の Worker スレッドで動くアルゴリズム側に分かれる。

Architecture of Algorithm Execution Framework

大まかにデータの流れを見ていくと、ユーザインターフェイス側の RunControl コンポーネント がアルゴリズム実行機能に対する ユーザ操作 を受け取り、メインの App コンポーネント が Worker スレッドに 実行リクエストを送信 する （矢印 1）。Worker スレッド でアルゴリズム実行制御を司る worker.js は、ジェネレータ関数 euclidean.js からジェネレータを生成して、実行リクエスト通りにジェネレータを動かす （矢印 2）。ジェネレータで yield に到達する度に、worker.js は実行結果を、ユーザインターフェイス側に 実行結果メッセージを送信 する （矢印 3）。App コンポーネント は実行結果メッセージを受信する度に、開始時点からの全実行結果を保持する内部の 状態変数（配列） に新たな実行結果を追加する （矢印 4）。そして React は状態変数が更新される度に、表示内容が宣言的に書かれた ResultViewItem コンポーネント を参照して、ユーザインターフェイスの表示内容を自動的に更新して、最終的にアルゴリズムの実行結果が画面に逐次表示される。

アルゴリズムの適用方法

フレームワーク上で各種アルゴリズムを実行するには、フレームワークに適合した形式 でアルゴリズム（ジェネレータ関数）と実行結果の表示形式（React コンポーネント）を記述する必要がある。引き続きユークリッドの互除法を例に、それらの方法を解説する。

アルゴリズム（ジェネレータ関数）

  • アルゴリズムのジェネレータ関数
    • export default しておく
    • 引数
      • input <object>: アルゴリズムの初期値
    • 戻り値 (yield) <object>: アルゴリズムの途中結果
      • input フィールド: 入力値
      • output フィールド: 出力値
  • worker.js（アルゴリズム実行制御）
    • アルゴリズムのジェネレータ関数を algo の名前でインポート

実行フレームワークはアルゴリズムのジェネレータを生成する際に、アルゴリズムの初期値 をジェネレータ関数の input 引数に 一つのオブジェクト として渡す。input オブジェクトの形式は自由だが、例えばユークリッドの互除法で m=21,n=13m = 21, n = 13 の場合は { m: 21, n: 13 } のようにできる。

更にフレームワークはアルゴリズムの実行結果を、ステップ毎 に 入力値と出力値と組み合わせ て保存する。そこでアルゴリズム側では、入力値を input フィールド、出力値を output フィールドに入れて、所望のタイミングで yield すればよい。例えば m=21,n=13m = 21, n = 13 で初期化された場合は、最初に yield される戻り値は、{ input: { m: 21, n: 13 }, output: { m: 13, n: 8 } } となる。

export default function* euclidean(input) {
  while (input.n !== 0) {
    // アルゴリズムメイン (Immutable)
    let output = { m: input.n, n: input.m % input.n }
    // 入力値と出力値（次のステップで入力値となる）をイールド
    yield { input, output }
    // 次のステップにむけて準備
    input = output
  }
  // 最終結果をイールド
  yield { input, result: input.m }
}

実行結果の表示形式（React コンポーネント）

実行結果の表示形式は ResultViewItem コンポーネント で記述される。上で説明したアルゴリズムの実行結果は、React によって ResultViewItem コンポーネントの result プロパティにそのまま渡される。input フィールドや output フィールドの値が参照できるので、あとは各自希望の可視化が可能。

例えばオブジェクトの中身をそのままダンプする場合は、

export default function ResultViewItem(props) {
  return <p>{JSON.stringify(props.result, null, 1)}</p>
}

Output of ResultViewItem Component - Object Dump

KaTeX\KaTeX で数式表示することもできる。

outputLine = (
  <>
    <TeX math={`m \\equiv ${r} \\mod n`} block />
    <TeX
      math={`m_{\\text{next}} \\coloneqq n, \\, n_{\\text{next}} \\coloneqq ${r}`}
      block
    />
  </>
)

Output of ResultViewItem Component - KaTeX

他にも、D3.js でグラフや図形で表示するなど、あとはご自由に！！

フレームワークの開発の流れ

Phase0: 準備（アルゴリズムの実装）

  • 準備 1: ユークリッド互除法のアルゴリズムを実装
  • 準備 2: React コンポーネントでアルゴリズムを実行
  • 開始ボタン
  • 初期値入力フォーム

ユークリッドの互除法をジェネレータ関数で実装して、React コンポーネントから呼び出して、結果が正しく表示される事を確認する。この時点では 同期的 に全ての処理を書いている。

Phase1: 実行機能

  • 一時停止、再開
  • ステップ実行（手動で一コマずつ）
  • クリア（出力結果を）
  • 時間間隔 (Interval)

中断・再開など、アルゴリズム実行の機能を作っていく。ユーザインターフェイスとの兼ね合いで、非同期処理 に切り替える必要が出る。また 状態管理 も必要になってくる。

  • idle 状態（初期状態）: アルゴリズムの実行前／完了
  • runninng 状態: アルゴリズムが実行中
  • pause: アルゴリズムの実行が中断

Phase2: ヒストリー機能

  • 中断／完了状態で、最初・途中・最新（最後）の時点へ移動
    • 全表示モードではハイライト表示
    • 個別表示モードでは、表示される結果が入れ替わる
  • 最新（最後）以外の時点 からの再実行

過去の実行結果を保持 して、前後の結果に移動できる機能を追加する。前回までは、中断中の最新（最後）の実行結果からの再開に限っていたが、今回は更に 最新（最後）以外の時点 からアルゴリズムを再実行する機能を追加する。

１つ目の機能では、フォーカスするインデックスを focusedIndex という状態変数で管理するのだが、React では 非同期処理で最新の値の取得が一筋縄では行かず、別途 useRef を使うという一工夫が必要になる。

また、再実行したい時点の出力で ジェネレータ関数を再生成 すれば、２つ目の機能が実現できる。しかし、再実行を開始するフォーカスが従来の最新（最後）か、それ以外かで処理が異なってくるので、状態が複雑化 して大変になってくる。

Phase3: Web Worker（バックグラウンドのスレッド）

Web Worker を利用して、アルゴリズムをメインスレッド（ユーザインターフェイス）とは 別のスレッド で動作するようにする。メインスレッド（ユーザインターフェイス）とワーカースレッド（アルゴリズム）のそれぞれで、二重の状態管理 が必要。更にメインスレッドでは、ワーカースレッドのレスポンスを待つ waiting 状態 が加わる。つまり 状態管理がますます複雑化 する。そこで State パターンでリファクタリング する。

まとめ

今回は手始めにユークリッドの互除法を例に、実行フレームワークに焦点をあてて説明した。今後は アルゴリズムを主軸に、視覚的にも楽しめる ソートアルゴリズム から始めて、色々なデモを作っていきたい。将来的には WebAssembly で高速化 など、夢はますます広がる！！