可視化

自分で書いたプログラムが固まって、いつまで待っても返ってこない——その原因が無限ループだった、という経験はないでしょうか。やっかいなのは、次へ、次へ とデータをたどっていく類の処理が、輪にハマったときです。 たとえば、連結リストをたどるコードを書いたとします。本来は末尾（null）で終わるはずが、データが壊れて途中のノードが前のノードを指していたら、たどる処理は終点にたどり着けず、同じ環をぐるぐる回り続けます。連結リストに限らず、「ある値から次の値を計算して進む」「状態 A から次の状態へ遷移する」——こうした「次をたどる」ロジックを自分で書くとき、どこかで輪に入り込んでいないかは、コードを眺めただけでは分かりません。 この記事で扱うのは、そういう自分のコードに「隠れた輪」が無いかを、たどりながら確かめる方法です。具体的には、連結リストが壊れて循環していないかのチェック、配列の重複探し（配列を「次をたどる写像」とみなします）、あるいは自分の反復ロジックがループに落ちないかをテストで確かめたいとき——どれも同じ道具ひとつで済みます。 素朴にやるなら、「訪れた場所を全部メモ（集合）しておいて、すでに来たことのある場所に戻ったら輪あり」とすればいい。正しく動きますが、訪れた数だけメモリ（$O(n)$）が要ります。 この記事の主役は、メモを一切持たず——変数2つ、追加メモリ $O(1)$——で輪を見つける、フロイドの循環検出（カメとウサギ）です。最後に、ブラウザだけで動くビジュアライザで実際に動かし、前回の玉突き方式 の無限ループにも当てはめてみます。 まず、輪のある列は「ρ（ロー）の形」になる 「現在の場所 → 次の場所」が毎回決まっている列をたどると、形は必ずρ（ギリシャ文字のロー）のようになります。輪に入るまでの一本道（しっぽ）と、ぐるぐる回る輪です。 輪の最後のノードの「次」は、輪の入口に戻ります。だから一度入ると二度と出られず、回り続ける。やりたいのは「輪があるか」、できれば「輪の入口はどこか」を知ることです。 カメとウサギ：ポインタ2つで追いつく フロイドの方法は、拍子抜けするほど単純です。同じスタートから、速さの違う2つのポインタを走らせます。 🐢 カメ：1歩ずつ進む 🐇 ウサギ：2歩ずつ進む 第1幕。 輪が無ければ、ウサギが先に終点（行き止まり）へ着きます。輪があれば、ウサギは輪の中をぐるぐる回り、いつか必ずカメに追いつきます。なぜなら、2匹が輪に入ったあとは、ウサギはカメに毎ステップ1つずつ近づくから。差が1ずつ縮むので、飛び越してすれ違うことはなく、必ずピッタリ一致します（差が1ずつしか減らない以上、輪の長さが偶数でも奇数でも必ず 0 を通ります）。一致したら、輪がある証拠です。 第2幕。 ここがエレガントなところ。出会った地点にカメを残し、もう1つのポインタを起点（スタート）に戻して、今度は両方とも1歩ずつ進めます。すると、ちょうど輪の入口で再会します。これで輪の始まりまで分かります。 function detectCycle(start, next){ let slow = start, fast = start; // 第1幕：出会うまで（出会わずに終点へ着けば輪は無い） do { slow = next(slow); // 1歩 fast = next(fast); if(fast === null) return null; // 2歩（1歩ごとに終点を確認） fast = next(fast); if(fast === null) return null; } while(slow !== fast); // 第2幕：起点と出会った地点から1歩ずつ → 入口で再会 let p = start; while(p !== slow){ p = next(p); slow = next(slow); } return p; // 輪の入口 } 使っているのは slow と fast（と p）という変数だけ。列がどれだけ長くても、メモリは増えません。これが $O(1)$ の意味です。 なぜ第2幕で入口に揃うのか 一本道の長さを $\mu$、輪の長さを $\lambda$ とします。第1幕でカメが進んだ距離を $d$ とすると、ウサギはその倍の $2d$ 進んで同じ場所にいるので、その差 $d$ は輪の長さ $\lambda$ の倍数です。つまりカメは「$\lambda$ の倍数ぶん」だけ余計に回った場所にいる。ここから、起点と出会い地点をそれぞれ1歩ずつ進めると、ちょうど $\mu$ 歩で両者が入口に重なります。証明は1行で、紙とペンでも追えます。 ...

プログラムで「先に入れたものから順に取り出す」キュー（Queue）を作りたい場面は、よくあります。ログのバッファ、イベントの待ち行列、センサー値の直近 N 件——どれも Queue です。 JavaScript なら、配列ひとつで素直に書けます。push で末尾に足し、shift で先頭を取り出す。 class NaiveQueue { constructor(cap){ this.cap = cap; this.data = []; } enqueue(x){ if(this.data.length >= this.cap) return false; this.data.push(x); return true; } dequeue(){ return this.data.length ? this.data.shift() : undefined; } } 短くて分かりやすい。でもこのやり方には、要素数が増えると効いてくる弱点があります。 弱点：先頭を取り出すたびに、全部が前へずれる 配列の先頭（index 0）を取り出すと、残りの要素はすべて1つ前へ詰め直されます。2番目が先頭へ、3番目が2番目へ……と、全員が席を1つずつ移動する。これが shift の正体です。 要素が4個なら4個ぶん、1万個なら1万個ぶん動かす。つまり dequeue 1回のコストが、入っている要素数に比例して重くなります（$O(n)$）。enqueue は末尾に足すだけなので軽いのに、取り出す側が足を引っ張るわけです。 中身は1バイトも変わらないのに、「席をずらす」ためだけに大量のコピーが走る。動かしたいのは「どこが先頭か」という目印だけのはずです。 リングバッファ：配列を「輪」に見立てる そこで、固定長の配列を用意して、それを輪のように使います。これがリングバッファです。 考え方はシンプルで、配列を伸び縮みさせる代わりに、2つの数だけを動かします。 head … いま先頭がある位置（次に取り出す場所） count … いま入っている要素数 enqueue は、空いている次の位置 (head + count) % cap に書いて count を1増やすだけ。dequeue は、head の中身を読んで head を1つ先に進め、count を1減らすだけ。要素は1つも動きません。 右端まで埋まったら、% cap（剰余）のおかげで自動的に 0 番へ戻ります。輪をぐるぐる回りながら、書く位置と読む位置の目印だけがずれていく。配列そのものは最初から最後まで同じ大きさのままです。 class RingQueue { constructor(cap){ this.cap = cap; this.data = new Array(cap); this.head = 0; this.count = 0; } enqueue(x){ if(this.count >= this.cap) return false; // 満杯 this.data[(this.head + this.count) % this.cap] = x; this.count++; return true; } dequeue(){ if(this.count === 0) return undefined; // 空 const x = this.data[this.head]; this.data[this.head] = undefined; // 取り出した参照を残さない（GCのため） this.head = (this.head + 1) % this.cap; // 先頭の目印を進めるだけ this.count--; return x; } } shift のような全体の詰め直しがどこにもありません。dequeue がやるのは足し算と剰余だけなので、入っている要素数に関係なく一定の手数（$O(1)$）で終わります。 ...

配列を「左に k 個ぶん回したい」場面があります。 [A, B, C, D, E, F, G] を 2 つ左に回すと [C, D, E, F, G, A, B]。先頭の何個かが、そっくり後ろへ回り込むイメージです。リングバッファ 、文字列のローテーション、表示行の巻き戻し——地味ですがよく出てきます。 素直にやるなら、回したあとの並びを別の配列に書き出して、それで元を置き換えれば終わりです。ただ、それだと配列がもう1本ぶん、まるごとメモリに要ります。動かしたいのは「順番」だけなのに、です。 この記事では、別配列を一切使わず、その場（in-place）で配列を回す方法を2つ紹介します。3回ひっくり返すだけのリバーサル法と、$\gcd(n,k)$ 本の鎖で穴を歩かせるジャグリング法。最後に、両方をブラウザだけで動くビジュアライザで実際に触って確かめます。 この記事は、画像をリネームだけで並び替える「玉突き方式」 の続編にあたります。あちらで出てきた「穴を歩かせる」手口が、今回のジャグリング法でそのまま効いてきます。 まず、素朴なやり方とその代償 いちばん分かりやすいのは、結果を別配列へ書くやり方です。 function rotateLeftCopy(a, k){ const n = a.length; k = ((k % n) + n) % n; // 負の k も正の回転量に正規化 const out = new Array(n); for(let i = 0; i < n; i++){ out[i] = a[(i + k) % n]; // マス i には「元の (i+k) 番目」が来る } return out; } これは正しく動きます。ただ、out という長さ $n$ の別配列が要ります。要素が重かったり本数が多かったりすると、この「もう1本」が効いてきます。 やりたいのは並べ替えだけ。中身は1つも変わりません。だったら、追加メモリ $O(1)$（作業用の変数1個ぶん）で済ませたい。ここからが本題です。 方法1：リバーサル法（3回ひっくり返すだけ） 最初に紹介するのは、拍子抜けするほど単純な方法です。左回転 k は、次の3回の部分反転に分解できます。 前半 k 個を反転する 後半 n−k 個を反転する 全体を反転する [A, B, C, D, E, F, G] を k=2 で左に回す例で追ってみます。 ...

通し番号のついた画像の束を、別の順番に並べ替えたい場面があります。 1.png から 7.png まで並んでいて、これを「5番を先頭へ持ってきて、残りを1つずつ後ろへずらす」といった具合に組み替えたい。素直にやるなら、新しい順番でファイルを全部コピーし直せば終わりです。 ただ、枚数が多かったり1枚が重かったりすると、コピーは時間も容量も食います。中身は1バイトも変わらないのに、です。動かしたいのは「順番」だけ。だったら、ファイル名（通し番号）を付け替えるリネームだけで並べ替えたい。 この記事では、そのリネームの順番をどう決めるかを考えます。素朴なスワップ方式と、少し賢い玉突き方式（循環置換）を比べて、同じ並び替えでも手数がどれだけ変わるかを、最後にブラウザだけで動くビジュアライザで実際に触って確かめます。 まず、リネームには落とし穴がある 「1番には今の5番の画像を、2番には今の1番の画像を…」と指示があったとして、思いつくまま 5番→1番 のように上書きリネームしていくと、すぐに事故が起きます。 上書きされた先の画像は、その瞬間に消えます。並び替えのつもりが、画像の破壊になってしまう。 これを避けるには、動かす1枚をいったん別の場所（temp）に逃がしてから動かします。逃がした跡地には「穴」が空きます。実は、この穴をどう埋めていくかが戦略の分かれ道です。 ここからは説明をシンプルにするため、7枚の画像にそれぞれ A〜G の中身が入っているとして話を進めます。スロット 1 には A、2 には B…という初期状態です。 並び替えの指示は、"並び先スロット": "元スロット" という対応表で表します。 { // 5番(E)を先頭へ。1〜5を1つずつ後ろへずらし、6番(F)と7番(G)は入れ替え "1": "5", // 1番には 元5(E) を持ってくる "2": "1", "3": "2", "4": "3", "5": "4", "6": "7", "7": "6" } 値（右側）が 1〜7 を1回ずつ全部使っていれば、画像が消えも増えもしない正しい並び替えです。重複や抜けがあれば、それは「同じ画像を2か所へ」「どこにも置かれず消える画像がある」というバグなので、実行前に弾きます。 素朴なやり方：スワップ方式 いちばん分かりやすいのは、1番から順番に定位置を埋めていくやり方です。 スロット 1 を見て、「ここに来るべき画像は今どこにあるか」を調べ、そこと交換する。次に 2 を見て…と、番号順に確定させていきます。「ここに来るべき画像が今どこか」は、画像の現在地を覚えておく loc という表で追跡します。 問題は、1回の交換にリネームが3回かかることです。temp に逃がして、欲しい画像を運んで、temp の中身を空いた場所へ戻す。これで3手です。 番号順に処理するので追いやすい反面、交換のたびに必ず temp への往復が発生します。交換が増えるほど、この「3手」がそのまま積み上がっていきます。 少し賢いやり方：玉突き方式（循環置換） 玉突き方式は、並び替えを最初に鎖（サイクル）として捉え直します。 さっきの指示を「誰が誰の場所を欲しがっているか」で辿ると、1→5→4→3→2 と一本の鎖になります。「1番が欲しいのは5番の画像、5番が欲しいのは4番の画像、4番が欲しいのは3番…」と繋がって、最後は2番が1番の画像を欲しがって輪が閉じます。6 と 7 はお互いを欲しがる、長さ2の短い鎖です。 鎖さえ作れれば、あとは穴を歩かせるだけです。 鎖の先頭の1枚（A）を temp へ逃がす。そこに穴が空く。 今ある穴に「そこへ入るべき1枚」を運ぶ。運んだ跡地が次の穴になる。 これを繰り返すと、穴が鎖の上を一歩ずつ歩いていく。最後に temp の1枚を戻して、その鎖は完了。 ポイントは、穴に入った画像はそのまま最終位置だということです。一度置いたら二度と動かしません。スワップ方式のように毎回 temp へ往復しないので、temp を使うのは1つの鎖につき1回だけで済みます。 ...

日本の地震情報を、地図と時間軸で視覚的に見られる Web アプリ Quake Radar を公開しました。 Quake Radar 日本の地震情報を地図と時間軸で確認 開く このアプリでできることを先にまとめると、次の3つです。 最近の地震を、地図と時間軸でまとめて見る 東日本大震災や熊本地震の流れを、一覧ではなく分布で見直す 文字の羅列だけでは掴みにくい揺れの連続性を、視覚的に追う 「とりあえず今どこで揺れが続いているのか見たい」ときや、過去の大地震を地図ベースで見直したいときの入口 として作っています。 地震情報は普段から文字や一覧で目にすることが多いですが、実際に地図上へ並べて、時間の流れと一緒に見てみると、見え方がかなり変わります。 どこで揺れが続いているのか、どのくらいの規模の地震がどの順番で起きたのか、一覧だけでは掴みにくい流れが少し直感的に見えてきます。 もともと私は、CLI で地震情報を確認するための簡単な仕組み を手元で使っていました。 ただ、数字や地名を追うだけでは分かりにくい場面もあり、地図やタイムラインで見られた方が理解しやすいのではないかと思い、この形にしてみました。 Quake Radar でできること Quake Radar では、最近の地震を地図上にプロットして、時間軸に沿って再生できます。 色は最大震度、円の大きさはマグニチュードに対応していて、地震の規模や揺れの強さがひと目で分かるようにしています。 また、最新の地震情報だけでなく、東日本大震災や熊本地震のような過去の大きな地震も、当時の流れをたどれる形で表示できます。 現時点では、東日本大震災と熊本地震を切り替えて表示できます。 文字だけで読んでいた時には見えにくかった流れも、地図と時間軸に載せるとかなり掴みやすくなります。 同じ地域で続いている地震、少し時間を空けて起きる大きな揺れ、広い範囲での分布などが、一覧よりも掴みやすくなります。 過去の大地震を見直すと印象が変わる 特に東日本大震災のデータを見ていると、本震だけを単独で捉えるのではなく、その前に大きめの地震があり、その後に本震へつながっていく流れが視覚的に残ります。 普段のニュースやテキスト中心の情報では、どうしても「大きな地震が起きた」という一点で記憶されがちですが、時系列で並べてみると、災害の見え方が少し変わります。 熊本地震のように、比較的限られた地域で強い揺れが連続するケースも、一覧ではなく地図で見ると特徴がかなり掴みやすくなります。 同じ「大きな地震」でも、揺れの広がり方や続き方に違いが見えてきます。 もちろん、過去のデータを見たからといって将来を予測できるわけではありません。 ただ、災害を単なる過去の出来事として忘れてしまわず、改めて備えを考えるきっかけにはなるのではないかと思っています。 このアプリを公開した理由 最初は、手元の地震情報を少し見やすくしたいという延長で作り始めたものでした。 ただ、実際に形になってくると、単なる自分用のツールとして閉じておくより、公開しておいた方が少しでも役に立つかもしれないと思うようになりました。 災害は、意識していないと日常の中ですぐ遠のいてしまいます。 大きな地震の記憶も、時間が経つとどうしても薄れていきます。 Quake Radar が、日々の地震活動を見たり、過去の大きな災害を見直したりする小さなきっかけになればと思っています。 データについて Quake Radar は、気象庁などの公開データをもとに再表示しているアプリです。 最近の地震は API 経由で取得し、過去の大きな地震については表示用に整理したデータを使っています。 公式発表そのものではないため、実際の避難判断や安全確保の判断は、必ず気象庁などの公式情報を優先してください。 関連記事 CLI で地震情報を確認するための簡単な仕組み おわりに 災害への備えは、何か大きな出来事があった直後だけ意識して、しばらくすると薄れてしまいがちです。 Quake Radar は、そんな時に少し立ち止まって地震の流れを見直し、災害を忘れないためのきっかけになればと思って公開しました。 もしよければ、実際に触ってみてください。 https://quake.apppppp.com/