逆転ポインタ法について
@UtakoSaeki(佐伯 詩子)さんが逆転ポインタ法の記事を書かれています。
おお、懐かしい〜と思って、Javaで実装してみました。
過程を画面に表示してみた
このアルゴリズムですが、文章で読んでも、なかなか理解できません。
『これは、絶対、アニメーションのようにして見せた方が、面白いし理解も早いぞ』と思いました。
STEPボタンを押す毎に、１ステップずつ画面に表示するプログラムをJavaのSwingを使って作ってみました。
こんな画面です。
１ステップずつ画面コピーをとっていると、大変なので、省略しますが、最終的に以下のようになりました。
背景がグレーのセル(cons)が、使われていたセルです。
背景がオレンジ色のセルは、GCされた箇所を表しています。
４パターンのGC過程のアニメーションができます。
パターン１
(list (quote a) b)
パターン２
(let ((a 1) (b 2)) (list a b))
パターン３
((a . 1) (b . 2) (c . 3))
パターン４
((a 1) (c 2 3))
佐伯さんの記事によるとハノイの塔もできるそうです。
私はやった事はありませんが、以下のように書かれていましたのでできるのでしょう
有名なハノイの塔の問題はかなり簡単にスタック無し再帰を実現できる
練習問題です
詳しい画面コピーが見たい方は、こちらを参照ください。
逆転ポインター法は、メモリーが少ない時に有効な方法だそうです。
興味を持って頂けたら幸いです。