ズボラのすすめ

大分前のことだが，ロボット工学の森政弘さんが，「非真面目のすすめ」を唱えたことがある．「自由な発想を」という趣旨だったかと記憶する．真面目一方で既存の枠組みの中でしかものを考えられないのは，制度などの安定・維持には結構なことかも知れないが，その枠組みを越えるような問題には無力である．また，幾何問題の解法に登場する補助線のように，その枠組みの中の問題であっても，一旦，枠を外してみると，見通しがクッキリと良くなることもあろう．「不真面目」ではなく「非真面目」といのは，このような発想の柔軟性を言ったものと思われる．

＊

少し前に「超整理法」が，流行った．読んだことがないのだが，少なくともその一部は，本などの整理について「敢えて，タイトル順などに整理しない方が良い，」といった趣旨であったと仄聞する．蔵書が多数ある場合，図書館のように整理して保管せずに，使った本は手近に残した方が，役に立つことが多い．ある本を調べたとすると，続けて二度三度と同じ本を見る傾向があるからだ．これを「アクセスの局所性」という．

パソコンを使っている人なら一度位は気付いたことがあると思うが，パソコンの仕様一覧に「キャッシュ・メモリ 512KB」などと書かれている．キャッシュは，メイン・メモリよりも高速にアクセスできる高価な素子を使い，プログラムの局所性を利用して，実効的に巨大だが低速なメイン・メモリを高速化する手法である．プログラムも，データのアクセスと同様に，比較的小さな領域内で動作していることが多い．だから，その領域がたまたま高速なキャッシュ・メモリ上にあれば，メイン・メモリを高速化したのと同じ効果が得られることになる．多くのプログラムは局所性という性質を持っているから，この「たまたま」は，結構，当たる（これを「ヒットする」と言う）ことが多いのである．

もう少し卑近な例を挙げると，かな漢字変換がある．一つの文章，あるいは同じ人の文章では，同じ漢字あるいは単語が繰り返し現れる傾向がある．文章の主題や筆者の好みの反映であろう．従って，「かんじ」を「幹事」に変換したとすると次の「かんじ」も「幹事」であり，「あおい」が「蒼い」であれば次も「蒼い」である可能性が高い．だから，かな漢字変換のプログラムは，漢字の変換頻度を計算して，頻度の高いものを漢字候補の始めの方に出すようにしていることが多い．

つまり，普通の整理法が「タイトル順（主題順，作者順，など）の整理」であるのに対して，「超整理法」は「アクセス頻度順の整理」という「整理法」であって，整理法を「超えて」いる訳ではない．

取り置きっぱなしの「ズボラ整理法」にも，ちゃんと理はあるのである．

＊

整理法と言えば，コンピュータ・プログラミングの題材に必ずと言って良い程使われるアルゴリズムに，整列（ソート）法がある．整列というのは，例えば 1 〜 10 迄の数を含む表を昇順に並べ直す（整理する）ことを言う．整列法には沢山の手法があるが，最も素朴なものはバブル・ソートである．10 個の数を横に並べたとすると，バブル・ソートの手順の概要は，以下のようである．

＊

整列法の効率を測るときは，普通，要素数 n への依存性を問題にする．バブル・ソートの場合は，上に示したように，n² である．バブル・ソートのような古典的な整列法では n² 程度であり，クイック・ソートなどの新しい整列法では n*log(n) となることが多い．

さて，「ズボラ」を奨める身としては，バブル・ソートのような「整然とした」手順は，どうも気に入らない．そう思ってバブル・ソートを眺めれば，この整列法は，

という「発想」であることが分かる．ならば，「適当に」ペアを取って逆順なら入れ替えると言う操作を気儘に繰り返せば，いつかは整列できるだろう．この手順を，ここでは，ランダム・ソートと呼ぶことにする．

明らかに，ランダム・ソートは，いつ終わるとも知れないが，「確率終了する，」つまり「終了しない確率は 0」であることも明白である．整然とした手順のバブル・ソートより「効率」が悪いのは当然だが，桁違いに遅くなるのだろうか．

そこでシミュレーションをしてみると，意外に速く終了し，バブル・ソートの高々 3 〜 4 倍程度であり，しかも n² の依存性を持っているらしいことが分かった．整列法の効率の議論では定数倍は問題にしないから，ランダム・ソートはバブル・ソートと同等の効率と言えそうである（このシミュレーションでは，調べたケースが少なく，乱数の検定もしていないので，「予想」に過ぎないが）．

「ズボラ」ソートも真面目なバブル・ソートも大差なさそう，というのが，このシミュレーションの結論である．

＊

やっぱり，ズボラにも一理あるんだナ，ウン．