ソートアルゴリズム可視化/可聴化Max for Liveデバイス Soni.f(y, sorts)

ソートアルゴリズムの動作を可視化・音化して Ableton Live の MIDI インストゥルメントとして使えるようにする Max for Live デバイス Soni.f(y, 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)

VisuAlgo

(National

University

of

Singapore)

Step-by-step animated explanations of sorting and other algorithms.
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) は、ソートアルゴリズムの各ステップ（比較・交換・挿入）を MIDI ノートに変換し、Ableton Live のインストゥルメントに渡す Max for Live デバイスです。

対応アルゴリズム

• 選択ソート (Selection Sort)
• 挿入ソート (Insertion Sort)
• クイックソート (Quick Sort)
• マージソート (Merge Sort)
• ヒープソート (Heap Sort)

概要

[入力シーケンス (MIDI ノート列)]
        ↓
[sort.js — Max [js] オブジェクト]
  ・アルゴリズムを実行し、各ステップの操作をヒストリとして記録
        ↓
[bang ごとに 1 ステップ再生]
  outlet0 : 現在のシーケンス状態
  outlet1 : アクセスされた音符（隣接値含む）→ MIDI out
  outlet2 : アクセスされたインデックスのポインタ
        ↓
[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 の主要な構造は以下のとおりです。

inlets = 2;
outlets = 7;

var availableAlgorithms = [
  "bubble",
  "selection",
  "insertion",
  "quick",
  "merge",
];
var selectedAlgorithm = "bubble";
var stepHistory = Array(); // 各ステップの操作履歴

// swap: 2 要素の入れ替え (type 0)
function swap(array, i, j, saveHistory) {
  var tmp = array[i];
  array[i] = array[j];
  array[j] = tmp;
  if (saveHistory) stepHistory.push([0, i, j]);
}

// insert: 要素のコピー (type 1)
function insert(array, i, j, saveHistory) {
  array[i] = array[j];
  if (saveHistory) stepHistory.push([1, i, j]);
}

// insertValue: 特定値の書き込み (type 2)
function insertValue(array, i, value, saveHistory) {
  array[i] = value;
  if (saveHistory) stepHistory.push([2, i, value]);
}

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

bang

による再生

function bang() {
  if (bangCount === 0) playSequence = inputArray.slice(); // 初期化

  if (bangCount === stepHistory.length) {
    outlet(6, "bang"); // ソート完了通知
    bangCount = 0;
    return;
  }

  var op = stepHistory[bangCount];
  // swap / insert / insertValue を再適用
  // ...

  // アクセスされたノートとその隣接ノートを MIDI として出力
  outlet(1, [
    playSequence[Math.max(0, idx - 1)],
    playSequence[idx],
    playSequence[Math.min(playSequence.length - 1, idx + 1)],
  ]);
  outlet(0, playSequence);
  bangCount++;
}

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

使い方

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

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

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

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

リンク

• リポジトリ: atsukoba/sonify-sorts
• Max/MSP: https://cycling74.com/products/max
• Max for Live: https://www.ableton.com/en/max-for-live/
• Max JS Object Reference: https://docs.cycling74.com/max8/refpages/js