2007年11月26日 18:15 [Edit]
プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
ぎくっ
なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。
その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。
- ユークリッドの互除法(Euclidean algorithm)
その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法」を指していたほど有名なアルゴリズム。小学校でも必ず習うこのアルゴリズムだけれども、実地でもよく使う。例えば本blogでも、「404 Blog Not Found:javascript - Math.Rational で 1/3 * 3 == 1」で使っている。
「アルゴリズム一生もの」、いや「アルゴリズム人類史もの」であることの代表と言っていい。
- エラトステネスの篩(the Sieve of Eratosthenes)
これまた古典アルゴリズムの代表。あまりに大きな数の素数判定には向かないが、32bit程度であれば今でも実用的である。
- 二分探索(Binary Search)
おそらく有史以前から存在するアルゴリズムだが、コンピューターとは特に相性がいい。
順番通り並んでいるものから目的のものを取り出すときに、まず真ん中を見て、それより前なら半分戻り、それより後なら半分進みを繰り返していけば、必ず目的のものが見つかるか、目的のものが存在しないかがわかる。
配列の検索だけではなく、方程式を解くのにも使える。
これだけ知られているアルゴリズムであるにも関わらず、最近まで「枯れていない」バグがあったという点でも面白い → 404 Blog Not Found:(a+a)/2 == -a /* 半世紀もののバグ */
- ニュートン法(Newton's method)
二分探索でも方程式の解を求めることは可能であるが、より洗練されているのがこちらのニュートン法。Programming Pearlでは著者のベントリーをもってしてニュートンを「ハッカー」と言わしめた理由の一つが、これ。
libmのソースを読めばいくらでも実例が出てくる。
- クイックソート(Quick Sort)
このアルゴリズムを見て、アルゴリズムに「目覚めた」人も多いだろう。「分割して制服」(divide et impera)というのはローマの「やり口」だが、21世紀の現代でも有効だ。
ただし、後述のマージソートと比べて、「手間がかかってしまう」ケースがあるのが今イチか。
- マージソート(Merge Sort)
一般的なソートアルゴリズムとして、現代もっとも使われているのがこちら。クイックソートほど「あったまいー」感はないし、クイックソートの方が高速な場合も少なくないのだが、ワーストケースがない、安定ソートである、並列処理に向いているいった利点が欠点にあまりある。「メモリーがより多く必要」という欠点も、現代では一時メモリーを使わないin-place merge sortが開発されている。クイックソートが「初恋の人」なら、こちらは「本命」といえば言い過ぎか。
- ハッシュテーブル(Hash Table)
メモリー効率を犠牲にしてでも(たいていのケースで)O(1)でデータにアクセスすることを可能にするこの方法は、連想配列の実装に最適で、Perlで多用されたことから今では連想配列の代名詞にすらなってしまった。
現在のLLでは、いずれも組み込みでこれをサポートしているし、CやC++のライブラリーも充実していることもあって、自ら実装する機会はあまりないと思われるが、その特性は知っておいた方がよい。
- 二分木(Binary Tree)
これはアルゴリズムというよりデータ構造であるが、両者には密接な関係があるのでここで紹介してもいいだろう。配列ソートにしろハッシュテーブルにしろ、データ構造は配列にデータを転がしているという点において「乱暴」であるが、こちらはデータの並べ方を工夫することによって、データへのアクセスを常にO(ln N)に抑えるという点が特徴だ。
ただし、メモリー確保(具体的には
malloc)のコストが結構あるということで、メモリー(再)確保の回数が少ない、配列を使ったデータ処理よりも実際は低速なことが多いので、メモリーだけで用が足りる場合には意外と出番が少なかったりもする。ところが、これがハードディスクが相手となると、とたんにこの方法の利点が生きてくる。これの変種であるB+木などは、データベースの実装などで実によく使われている。まともな計算機科学のクラスであれば、このアルゴリズムを必ず教えるのには理由があるのだ。
- ハフマン符号(Huffman Coding)
データの圧縮法としてもっとも基本的な方法の一つ。一応発案者の名前が付いているが、原理自体はモールス信号にも見られる。その要諦は「よく使われるものは短く、そうでないものは長く表現する」ということになる。
欠点は、コード表を作るためにデータを一度読んでからでないと理想的な圧縮が出来ないことであるが、データの特性があらかじめ解っている場合、あらかじめ用意しておいたコード表を用いることが出来る。JPEGなどがそうしており、またモールス信号もその変種と見なせる。
- メルセンヌ・ツイスタ(Mersenne twister)
ここまでは割と直感的にそのよさがわかるアルゴリズムばかり紹介してきたが、「専門家はやっぱりすげー」というのも一つは紹介しておきたい。というわけで取り上げるのがこのメルセンヌ・ツイスター。
現在では乱数を使う機会というのはこれまでになく増えているが、その乱数の「乱れ具合」を革命的に改善したのがこれである。
最近では組み込みでこれに基づく疑似乱数を提供する処理系も徐々に増えて来てはいるが、まだまだ「昔」のアルゴリズムに基づくものも少なくないので、お使いの言語や環境でシリアスな乱数が必要なら、それをモジュールなどで手に入れる方法は覚えておいて損はないだろう。
♪手を横に〜あら危ない〜頭を下げればぶつかりません ♪でも誰に〜頭下げる〜もちろんその名はJASRAC
↑草稿段階でもそうなのかしらん
Dan the Algorithmical Man
この記事へのトラックバックURL
これからの時代6.まで教えてもいい気がします。
たとえば、杉原厚吉著「計算幾何工学」の最初の方に書かれていることは、プログラマの常識にしたいことです。
これなんですか?
探してみても見つからない、
それらしきものでも英語なので分からんチンです。
ざっくりでもいいので教えていただけませんか?
それか日本語情報があれば
よろしく。
信号処理応用発展の礎となったと思う、FFTなんてどうですか？
あれのおかげで７０年代に入ってからいろんな信号処理応用製品が出てきたと思うんですよ・・・
その昔は、普通のフーリエ変換を計算するために、そろばん塾にいって、たすきがけの計算やってたそうです。（私の指導教官談）
んで私も修論で音声屋になり、素のフーリエ変換とFFTとで処理速度の差に唖然とした口です・・・
ブラックですね！
http://go4wap.net
http://go4wap.net
