2012年02月10日 13:00 [Edit]

博士の異常なアルゴリズム、または私は如何にして心配するのを止めて線形探索を愛するようになったか

これはちょっとプログラマーといふ生物を買いかぶりすぎてると思います。

プログラマへの誤解 | pineapple blog
プログラムを書かない人がプログラムを読んだときにする良くある間違いは,ああこんなプログラムなら自分にも書けそうだと思うことだ.プログラムは何百万とある可能性からたったひとつ(は言い過ぎにしてもわずかながら)の正しい方法を残したものであり,この捨てる能力こそがプログラマの実力だから.

少なくとも、プロ2グラマーの場合は。


その反証としてあげたいのが、線型探索(linear search)。漢字で書いたり英語で書いたりするとさぞ凝ったことをやってるように見えるけど、実は「見つかるまで頭から(あるいは尻から)順に」、つまり文字通り「片っ端から探す」だけ。プロアマ問わず、それどころかプログラムという言葉を知らない人でも、これをやったことがない人はありえない。バケットソート以上に「天然」な、誰にも教わらなくても誰でもできるアルゴリズム。

それゆえに、「ダメアルゴリズム」の代表格として扱われることが最も多いのもこれでしょう。二分探索ハッシュテーブルB-tree…確かに「片っ端から探す」より冴えたやり方を、今の我々はいくらでも知っています。

にも関わらず、線形探索は他のどの検索アルゴリズムよりも使われているのです。それも、他のアルゴリズムも方が明らかに冴えたやり方だとわかっている場面でさえ。

その代表が、ファイルシステム。FAText2も、ディレクトリーは線形探索なんですよ。

File Allocation Table - Wikipedia, the free encyclopedia
In fact, seeking for files in large subdirectories or computing the free disk space on FAT volumes is one of the most resource intensive operations, as it requires reading the directory tables or even the entire FAT linearly.

システムアドミニストレイターであれば、キャッシュを多用するプログラムのキャッシュディレクトリが一つではなく多くのサブディレクトリに分けていることをご存知だと思います。これはその頃の名残。

404 Blog Not Found:備忘録 - Firefox 4 がキャッシュ使いすぎてたので
以前はこの下にキャッシュファイルが直にあったのが、0〜Fのサブディレクトリのさらに00〜FFサブディレクトリの下にできるようになった。デフォルト設定のautomatic cache managementが有効になった状態では、ディレクトリの数だけで軽く4112(16+16*256)を超えることになる。

FATやext2が生まれた当時、すでにB-Treeを用いたファイルシステムだっていくつか存在していました。にも関わらずそういう「冴えたアルゴリズム」を用いたファイルシステムが主流になるのは、21世紀に入ってからです。いや、数だけで言えば今だってFATが用いられている以上、未だ線形探索が主流と言っても過言ではない。これってMicrosoftの中の人々がアホだからそうなってしまったのでしょうか?

そう主張する人が少なくないのは私も承知しています。私自身、酒が入ったらそう言い出しそう。でもしらふではとてもそう主張できないのは、プロ2プログラマーにはアマグラマーには課せられていない制約があることを、その端くれとして知っているからです。

それが、納期。

あまりに当たり前なので、線形探索も立派なアルゴリズムであることを忘れてしまうぐらい、プロですらこのことを見落としがちなのだけど、実際問題「何百万とある可能性からたったひとつの正しい方法を残す」時間をもらえることなんてまずないんです。

これは、プログラムに限ったことではありません。

考えないのが、いいプログラマ/ぐぐらず校正せず書くのが、よい日記 - きしだのはてな
確か、初心者が10手、中級者が20手、上級者が30手で、羽生名人は15手くらい、とかだったと思う。まあ、そのくらいの比率。

将棋だって、実はそう。試合によって持ち時間は異なるけど、有限であることには変わりはありません。プロでさえ二歩をやってしまうことがあることを鑑みれば、その制約の強さは推して知るべしでしょう。

そんな時に重要なのは、「冴えたやり方」ではなくて「とりあえず動くやり方」。そんな時に、線形探索ほど頼もしいアルゴリズムはまずありません。「一番速く動く」わけではないけれど、「一番早く書ける」。そのうえ「正しくない」、つまり前処理されていないデータに対しても正しい答えを出すことが保証されている…

もちろんそれで「後で困ったことになること」は、ユーザーもプログラマーもその時点で薄々気づいています。JavaScriptという言語は困ったところが実に多い言語ですが、なぜそうなったかは「Coders at Work」のブレンダン・アイクのインタビューを読めばとてもよくわかります。このインタビューだけでも甲斐です、失礼、買いです。私は買う前に献本いただいてしまったのですが。この場を借りて御礼。

幸い、プログラムを組んだ年数だけは長くなってきてて、もうプログラムを組んだことがない年数のほうが圧倒的に少なくなってるくらいなんで、ある程度、考えなくても正しい選択をするようになってる。

これをアイクの前で言う度胸は、私にはありません。

彼ほどの手練プログラマーでも、「とりあえず動く」を優先せざるをえなかったのですから。

そして「とりあえず動く」が、「これ以上正しく動かせない」よりずっとずっと大事なことであること、 "Done is better than perfect" であるという歴史に JavaScript は新たなページを加えました。動いているプログラムを見てはじめて、我々は考えるべきなのは何なのか、正しくするべきは何なのかを知ることが出来る生物なのです。

"Done is better than perfect"の例としてもう一つ登場するのが、Perl。本書におけるPerlの扱いはまさに"done"と"perfect"のせめぎ合い。本書でもPerlはさんざん持ち上げられかつdisられています。done は better ではありますが、そこで満足してしまうのもまたプロとして持続可能性を放棄しているとしか言えません。

それでも、 done は perfect にまさるのです。

考えるのは、やってしまった後でも間に合います。ファイルシステムにおける線形探索が徐々にB-Treeなどに置き換えられるように。

しかし、やらないことには、それが考えるに値する問題であるかも我々にはわからないのです。

少なくとも、私にはわからない。

バカにするのはバカになった後でいい。

ダメだしする前に、とりあえず本当にだめか線形探索してみましょう。

Dan the Programmer

というわけで追記


この記事へのトラックバックURL