2007年11月26日 18:15 [Edit]

プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10

ぎくっ

なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。

その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。


  1. ユークリッドの互除法(Euclidean algorithm)

    その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法」を指していたほど有名なアルゴリズム。小学校でも必ず習うこのアルゴリズムだけれども、実地でもよく使う。例えば本blogでも、「404 Blog Not Found:javascript - Math.Rational で 1/3 * 3 == 1」で使っている。

    「アルゴリズム一生もの」、いや「アルゴリズム人類史もの」であることの代表と言っていい。

  2. エラトステネスの篩(the Sieve of Eratosthenes)

    これまた古典アルゴリズムの代表。あまりに大きな数の素数判定には向かないが、32bit程度であれば今でも実用的である。

  3. 二分探索(Binary Search)

    おそらく有史以前から存在するアルゴリズムだが、コンピューターとは特に相性がいい。

    順番通り並んでいるものから目的のものを取り出すときに、まず真ん中を見て、それより前なら半分戻り、それより後なら半分進みを繰り返していけば、必ず目的のものが見つかるか、目的のものが存在しないかがわかる。

    配列の検索だけではなく、方程式を解くのにも使える。

    これだけ知られているアルゴリズムであるにも関わらず、最近まで「枯れていない」バグがあったという点でも面白い → 404 Blog Not Found:(a+a)/2 == -a /* 半世紀もののバグ */

  4. ニュートン法(Newton's method)

    二分探索でも方程式の解を求めることは可能であるが、より洗練されているのがこちらのニュートン法。Programming Pearlでは著者のベントリーをもってしてニュートンを「ハッカー」と言わしめた理由の一つが、これ。

    libmのソースを読めばいくらでも実例が出てくる。

  5. クイックソート(Quick Sort)

    このアルゴリズムを見て、アルゴリズムに「目覚めた」人も多いだろう。「分割して制服」(divide et impera)というのはローマの「やり口」だが、21世紀の現代でも有効だ。

    ただし、後述のマージソートと比べて、「手間がかかってしまう」ケースがあるのが今イチか。

  6. マージソート(Merge Sort)

    一般的なソートアルゴリズムとして、現代もっとも使われているのがこちら。クイックソートほど「あったまいー」感はないし、クイックソートの方が高速な場合も少なくないのだが、ワーストケースがない、安定ソートである、並列処理に向いているいった利点が欠点にあまりある。「メモリーがより多く必要」という欠点も、現代では一時メモリーを使わないin-place merge sortが開発されている。クイックソートが「初恋の人」なら、こちらは「本命」といえば言い過ぎか。

  7. ハッシュテーブル(Hash Table)

    メモリー効率を犠牲にしてでも(たいていのケースで)O(1)でデータにアクセスすることを可能にするこの方法は、連想配列の実装に最適で、Perlで多用されたことから今では連想配列の代名詞にすらなってしまった。

    現在のLLでは、いずれも組み込みでこれをサポートしているし、CやC++のライブラリーも充実していることもあって、自ら実装する機会はあまりないと思われるが、その特性は知っておいた方がよい。

  8. 二分木(Binary Tree)

    これはアルゴリズムというよりデータ構造であるが、両者には密接な関係があるのでここで紹介してもいいだろう。配列ソートにしろハッシュテーブルにしろ、データ構造は配列にデータを転がしているという点において「乱暴」であるが、こちらはデータの並べ方を工夫することによって、データへのアクセスを常にO(ln N)に抑えるという点が特徴だ。

    ただし、メモリー確保(具体的にはmalloc)のコストが結構あるということで、メモリー(再)確保の回数が少ない、配列を使ったデータ処理よりも実際は低速なことが多いので、メモリーだけで用が足りる場合には意外と出番が少なかったりもする。

    ところが、これがハードディスクが相手となると、とたんにこの方法の利点が生きてくる。これの変種であるB+木などは、データベースの実装などで実によく使われている。まともな計算機科学のクラスであれば、このアルゴリズムを必ず教えるのには理由があるのだ。

  9. ハフマン符号(Huffman Coding)

    データの圧縮法としてもっとも基本的な方法の一つ。一応発案者の名前が付いているが、原理自体はモールス信号にも見られる。その要諦は「よく使われるものは短く、そうでないものは長く表現する」ということになる。

    欠点は、コード表を作るためにデータを一度読んでからでないと理想的な圧縮が出来ないことであるが、データの特性があらかじめ解っている場合、あらかじめ用意しておいたコード表を用いることが出来る。JPEGなどがそうしており、またモールス信号もその変種と見なせる。

  10. メルセンヌ・ツイスタ(Mersenne twister)

    ここまでは割と直感的にそのよさがわかるアルゴリズムばかり紹介してきたが、「専門家はやっぱりすげー」というのも一つは紹介しておきたい。というわけで取り上げるのがこのメルセンヌ・ツイスター。

    現在では乱数を使う機会というのはこれまでになく増えているが、その乱数の「乱れ具合」を革命的に改善したのがこれである。

    最近では組み込みでこれに基づく疑似乱数を提供する処理系も徐々に増えて来てはいるが、まだまだ「昔」のアルゴリズムに基づくものも少なくないので、お使いの言語や環境でシリアスな乱数が必要なら、それをモジュールなどで手に入れる方法は覚えておいて損はないだろう。

♪手を横に〜あら危ない〜頭を下げればぶつかりません
♪でも誰に〜頭下げる〜もちろんその名はJASRAC

↑草稿段階でもそうなのかしらん

Dan the Algorithmical Man


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

この記事へのトラックバック
YouTube - FanworksChのチャンネル これはハマる スイスのリアルタイム鉄道マップ「Swiss Trains」|WEBマーケティングブログ キューブ 「Humping Dog」:腰を振るだけのUSBアクセサリ : Gizmodo Japan(ギズモード・ジャパン) 一発芸に役立つマジ...
なんか興味そそられたなんやかんや【heeha.ws::blog】at 2008年10月10日 03:45
今週前半、小飼弾さんの「404 Blog not found」が「プログラマーで
好きなアルゴリズム:モンテカルロ法【nobilog2】at 2007年12月01日 07:46
私 のような文系人間にはあんまり縁がないのが「アルゴリズム」という奴ですが(ユークリッドの互除法も勉強してない)、それでも覚えておいたほうがいいとの ことなのでリンク。大体上5つぐらいはwikiの記事見て仕組みはわかりました。アルゴリズムとは違うけど、数学...
・プ ログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10【のほほんダイアリー】at 2007年11月28日 00:43
誤字脱字をあげつらうのは面白いものではない。そんなことより、PCと日本語変換が小飼氏の思考に追従しきれないことに驚くべきだ。
小飼弾的勢い【日々雑感II】at 2007年11月26日 22:43
この記事へのコメント
俣 韲鱶袱 WAP!
http://go4wap.net
Posted by go4wap.net at 2008年10月04日 09:05
俣 韲鱶袱 WAP!
http://go4wap.net
Posted by go4wap.net at 2008年10月03日 02:05
体操ww
ブラックですね!
Posted by hg at 2007年12月06日 19:34
RSAも欲しいっす
Posted by   at 2007年12月01日 10:18
スライド辞書。これとハフマン符号を組み合わせたのがLHA。
Posted by shamcat at 2007年11月28日 10:23
情報科学的なアルゴリズムではないかもしれませんが。

信号処理応用発展の礎となったと思う、FFTなんてどうですか?
あれのおかげで70年代に入ってからいろんな信号処理応用製品が出てきたと思うんですよ・・・

その昔は、普通のフーリエ変換を計算するために、そろばん塾にいって、たすきがけの計算やってたそうです。(私の指導教官談)

んで私も修論で音声屋になり、素のフーリエ変換とFFTとで処理速度の差に唖然とした口です・・・
Posted by 昔の情報工学科 at 2007年11月27日 18:43
>in-place merge sort
これなんですか?
探してみても見つからない、
それらしきものでも英語なので分からんチンです。
ざっくりでもいいので教えていただけませんか?
それか日本語情報があれば
よろしく。
Posted by doubleclick at 2007年11月27日 16:03
あ〜勉強になりました。
Posted by blog49 at 2007年11月27日 08:24
再帰下降解析。だってこれで言語がつくれるんだもん。
Posted by FA at 2007年11月26日 23:30
アルゴリズムというよりも「取り扱い手法」といった方が良いでしょうが「計算幾何学」にも、ごく軽い言及だけでもお願いします。そういう分野があるということすら知らないプログラマが多すぎるような気がしていますので。

たとえば、杉原厚吉著「計算幾何工学」の最初の方に書かれていることは、プログラマの常識にしたいことです。
Posted by 携帯から at 2007年11月26日 22:26
偏ってるね.少なくとも再帰とグラフは入れておかないとダメだよ.
Posted by hoge at 2007年11月26日 21:02
ダイカストラ法も大好きです
Posted by back at 2007年11月26日 20:59
4.までは高校で習いますね。
これからの時代6.まで教えてもいい気がします。
Posted by bob at 2007年11月26日 20:34
s/制服/征服
Posted by at 2007年11月26日 19:21
分割統治法(Divide and Conquer)は?
Posted by ん? at 2007年11月26日 18:57