/blog/Max for Live でのソートアルゴリズム可視化・ sonification プラグイン
Tech Blog2022 - 2 - 20

Max for Live でのソートアルゴリズム可視化・ sonification プラグイン

Max/MSPMax for LiveAbleton LiveJavaScriptSorting Algorithm

ソートアルゴリズムの動作を MIDI シーケンスとして音にする Max for Live デバイス Soni.f(y, sorts) を作った話。

ソートアルゴリズムの動作を可視化・音化して Ableton Live の MIDI インストゥルメントとして使えるようにする Max for Live デバイス Soni.f(y, sorts) を作りました。

https://github.com/atsukoba/sonify-sorts

ソートアルゴリズムの可視化・音化

ソートアルゴリズムの動作を視覚・聴覚的に表現した動画・デモは、プログラミング教育の文脈でも人気があり、世界中の開発者が様々なアプローチで実践しています。

15 Sorting Algorithms in 6 Minutes (Timo Bingmann, 2013)

Each comparison and swap is mapped to a pitch, creating a distinctive sonic fingerprint for each algorithm. Tens of millions of views.

AlgoRhythmics (Sapientia University)

Sorting algorithms performed as folk dances — a wonderfully embodied take on algorithmic structure. (https://www.youtube.com/user/AlgoRhythmics)

sorting.at (Carlo Zapponi)

An interactive browser-based visualization of many sorting algorithms.

https://sorting.at/

VisuAlgo (National University of Singapore)

Step-by-step animated explanations of sorting and other algorithms.
https://visualgo.net/en/sorting

https://visualgo.net/en/sorting

これらは「可視化 + 音付き動画」として完成しているものですが、あくまでオフラインのデモや動画として閲覧・鑑賞するものです。
今回はこれをリアルタイムに演奏可能な MIDI インストゥルメントとして利用できる Max for Live デバイスとして実装してみました。

Max/MSP と Max for Live

Max/MSP

Max/MSP（以下 Max）は Cycling '74 が開発するビジュアルプログラミング環境で、音楽・映像・インタラクティブメディアの制作に広く使われています。パッチ（.maxpat）と呼ばれるファイルにオブジェクトをつなぎ合わせてプログラムを組む、データフロー型の言語です。

Max の強みのひとつは、JavaScript を [js] オブジェクトとして組み込み、複雑なロジックを記述できることです。

Max for Live (M4L)

Max for Live（M4L）は Max と Ableton Live を統合した環境で、Live 上で動く独自デバイスを Max で制作できます。MIDI エフェクト・オーディオエフェクト・インストゥルメントの 3 種類のデバイスを作成でき、.amxd ファイルとして配布できます。

Cycling '74 は 2017 年に Ableton に買収されており、Max for Live は現在 Ableton Live Suite / 単体ライセンスで提供されています。(Cycling '74 Joins Ableton, 2017)

Soni.f(y, sorts)

Soni.f(y, sorts) スクリーンショット

今回作った Soni.f(y, sorts) は、ソートアルゴリズムの各ステップ（比較・交換・挿入）を MIDI ノートに変換し、Ableton Live のインストゥルメントに渡す Max for Live デバイスです。

対応アルゴリズム

  • バブルソート (Bubble Sort)
  • 選択ソート (Selection Sort)
  • 挿入ソート (Insertion Sort)
  • クイックソート (Quick Sort)
  • マージソート (Merge Sort)

仕組みの概要

1[入力シーケンス (MIDI ノート列)]
2        ↓
3[sort.js — Max [js] オブジェクト]
4  ・アルゴリズムを実行し、各ステップの操作をヒストリとして記録
5        ↓
6[bang ごとに 1 ステップ再生]
7  outlet0 : 現在のシーケンス状態
8  outlet1 : アクセスされた音符（隣接値含む）→ MIDI out
9  outlet2 : アクセスされたインデックスのポインタ
10        ↓
11[Ableton Live の MIDI インストゥルメントへ]

Max パッチ内で [js sort.js] オブジェクトを読み込み、bang をトリガーとして 1 ステップずつソート操作を再生します。ソートが完了すると outlet6 から bang が出力され、アニメーションの終了を通知します。

JavaScript 実装 (sort.js)

Max の [js] オブジェクトは ECMAScript 5 相当の JavaScript を実行できます（Max JS Object Reference）。

sort.js の主要な構造は以下のとおりです。

1inlets = 2;
2outlets = 7;
3
4var availableAlgorithms = [
5  "bubble",
6  "selection",
7  "insertion",
8  "quick",
9  "merge",
10];
11var selectedAlgorithm = "bubble";
12var stepHistory = Array(); // 各ステップの操作履歴
13
14// swap: 2 要素の入れ替え (type 0)
15function swap(array, i, j, saveHistory) {
16  var tmp = array[i];
17  array[i] = array[j];
18  array[j] = tmp;
19  if (saveHistory) stepHistory.push([0, i, j]);
20}
21
22// insert: 要素のコピー (type 1)
23function insert(array, i, j, saveHistory) {
24  array[i] = array[j];
25  if (saveHistory) stepHistory.push([1, i, j]);
26}
27
28// insertValue: 特定値の書き込み (type 2)
29function insertValue(array, i, value, saveHistory) {
30  array[i] = value;
31  if (saveHistory) stepHistory.push([2, i, value]);
32}

各ソート関数（bubbleSort, selection_sort, insertionSort, quickSort, mergeSort）は、実行中にすべての操作を stepHistory 配列に蓄積します。sort() メッセージを受け取ると事前にソート全体を計算して履歴を記録し、その後 bang を受け取るたびに stepHistory を 1 ステップずつ再生します。

bang による再生

1function bang() {
2  if (bangCount === 0) playSequence = inputArray.slice(); // 初期化
3
4  if (bangCount === stepHistory.length) {
5    outlet(6, "bang"); // ソート完了通知
6    bangCount = 0;
7    return;
8  }
9
10  var op = stepHistory[bangCount];
11  // swap / insert / insertValue を再適用
12  // ...
13
14  // アクセスされたノートとその隣接ノートを MIDI として出力
15  outlet(1, [
16    playSequence[Math.max(0, idx - 1)],
17    playSequence[idx],
18    playSequence[Math.min(playSequence.length - 1, idx + 1)],
19  ]);
20  outlet(0, playSequence);
21  bangCount++;
22}

この設計により、ソートの実行と再生を分離しているため、任意のテンポで（Ableton Live の [metro] などを使って）ステップを進めることができます。

使い方

  1. sonify-sorts.amxd を Ableton Live の MIDI トラックにドロップします。
  2. デバイス上の数列（入力シーケンス）を MIDI ノート番号として設定します。
  3. アルゴリズムを選択し、sort ボタンを押してソートの履歴を計算させます。
  4. play ボタン（またはテンポ同期させた bang）でステップを進めると、ソートの各ステップが MIDI ノートとして出力されます。
  5. 出力先のインストゥルメント（シンセ・サンプラーなど）でリアルタイムに音を鳴らすことができます。

使用例のスクリーンショット（プレースホルダ）

まとめ

ソートアルゴリズムの可視化は定番のプログラミング教育コンテンツですが、これを Ableton Live の MIDI インストゥルメントとして使えるようにすることで、ソートの動作を「音楽」として体験・演奏できるようにしました。

Max の [js] オブジェクトを用いることで、複雑なアルゴリズムをビジュアルパッチで組む必要なく、使い慣れた JavaScript で記述できるのが大きな利点です。

ソートの種類によってリズムパターンや音の密度が大きく変わるため、音楽的な観点でのアルゴリズム比較としても面白い体験ができます。

リンク