アルゴリズムに始まり，アルゴリズムに終わる

「アルゴリズムの勉強のしかた」http://nowokay.hatenablog.com/entry/20110922/1316676007

これを見て強烈な違和感を覚えたので，自分の意見も書いておくことにする．*1

アルゴリズムはとても重要だ．これは間違いない．プログラミングを志す者ならば，必ず学んでおかなければならない基礎知識の一つだ．DBやJavaを使ってるのに「ハッシュも平衡木もB木も知りません」なんて開発者がいるのは，日本IT業界の恥だと思ってる．

プログラマが知るべき97のこと

89. Use the Right Algorithm and Data Structure

"Programmers should not reinvent the wheel, and should use existing libraries where possible. But to be able to avoid problems like the bank's they should also be educated about algorithms and how they scale."

"Many say reuse in programming is paramount. Above all, however, programmers should know when, what, and how to reuse. To do that, they should know knowledge of the problem domain and of algorithms and data structures."

"So, read some good books - and make sure you understand them."

そしてアルゴリズムの学習には終わりが無い．それはまるで英語を学習する際の英単語に似ている．小学校や中学校で最初に英語を学ぶ時，それこそthisやbeのレベルの英単語を学ばないものはまずいない．そしてそこそこ英語が上達した人たちも，語彙を増やすための努力は必要だ．その学習には終わりが無いらしい．

今，もしプログラマ志望の若い人に相談されたら，

1. 教科書：アルゴリズムイントロダクション三部作 OR 岩波講座の「アルゴリズムとデータ構造」のどちらか*2．O'Reillyの「入門 データ構造とアルゴリズム」も要検討．
2. 参考書：オライリーのアルゴリズムクイックリファレンス

辺りを勧めるかな．*3

新しくてお勧めの本が，こんなに少ないとは思わなかった．コンピュータ書籍のコーナーにも，アルゴリズム本が数えるほどしかなかったりする．昔「アルゴリズムイントロダクション」もかなり苦戦していると聞いたことがあるし，ひょっとしたら硬派のコンピュータサイエンスの専門書って，和書だと最近はほとんど売れなくなったりするのかな？日本のIT業界も末期だなあ．

入門・基礎

英語でいうといわゆる「単語帳」な感じ．まず最初にこれを覚えなきゃ始まらない．

DUO 3.0

英単語ピーナツ銀メダル改訂新版

ジーニアス英熟語1000

普通に「アルゴリズムを勉強する」と書いた場合は，こちらの入門の方を指すと思う．プログラマならば基本的なアルゴリズムを覚えると共に，アルゴリズムの考え方，アルゴリズムを自分のアプリケーションへの適用方法や新しいアルゴリズムを創るスキルを身につける必要がある．

以下のようなアルゴリズムの入門書は最低でも一冊は目を通して，幾つかの例題について実装する練習をしておくべき．英単語帳と同じで，マトモな本ならば基本アルゴリズムについてはそれほど大差は無い．他の分野ほど陳腐化も激しくないので，10〜20年以上前の本でもまあまあ使える．*4 *5そしてまともな書籍なら2冊以上は必ずしも必要ない．（持っていても良い．）

このような本で紹介されているアルゴリズムとデータ構造はプログラミングの基本中の基本なので，

• もちろん名前は全部知っている．それがどんなアルゴリズムかも説明できる．
• うち幾つか（５〜８割くらい）については実際に実装した経験がある．
• その他についても実装する必要があれば，いつでも簡単に実装できる自信がある．
• そのアルゴリズムの特性，長所と短所，ボトルネック，実装上の注意点，効率化テクニックについて知っている．その理由についても理解している．
• 計算量やメモリ消費，ディスクアクセスのオーダーを（暗記するのではなく）見積もることができる．*6
• 必要に応じて自分でそのアルゴリズムをカスタマイズしたり，改良したりできる．またその影響や変更後の計算量を見積もることができる．*7
• そこで書かれている擬似コードやサンプルを，自分が必要とする言語に移植し，必要に応じて型安全性や例外処理等を追加できる．*8 特にこれは次に示すサンプルコード集の方で重要性が増す．
• ビッグO記法，多項式オーダー，疑似乱数，丸め誤差，貪欲(greedy)アルゴリズム，怠け者(lazy)な処理，アトミック(atomic)な処理，NP完全，巡回セールスマン問題，等々のキーワードも，一通り理解しておくこと．（そんなに多くない．むしろ名前が付いてない部分に対する理解も重要．）

くらいになっておくべきだろう．

「アルゴリズムとデータ構造」みたいなタイトルが付いているのは入門書の場合が多い．単語帳ほどではないけれど，アルゴリズム本もプログラミング関係の書籍としてはかなり多い方だ．単語集と同様に，各人それぞれに好みがあるだろうから，自分の目で確認して自己責任で入手すること．

入門書・教科書

注：その後，第三版が出版された．

数学的基礎とデータ構造 (アルゴリズムイントロダクション)

アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)

アルゴリズムイントロダクション 第3巻 精選トピックス

*9

Introduction to Algorithms (MIT Press)

*10
アルゴリズム本で定番の書籍．といっても自分が最初にプログラミングを勉強した頃には，まだこの本が存在しておらず，この本が出た頃には基本はマスターした後だったので，この本を真面目に読んだことは無い．

追記：3版の和訳も一巻が出版された．「入門書」というよりは「教科書」なので難易度は高め．基礎からミッチリ勉強したい人なら挑戦する価値はあるが，「動けば良いじゃん」ななんちゃってプログラマーだと確実に挫折する．

アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (世界標準MIT教科書)

アルゴリズムイントロダクション 第3版 第2巻: 高度な設計と解析手法・高度なデータ構造・グラフアルゴリズム (世界標準MIT教科書)

さらに追記．O'Reillyより以下の書籍も出る予定．内容は要確認だが，有力候補の一つ．

入門 データ構造とアルゴリズム

Data Structures and Algorithms Made Easy

アルゴリズムとデータ構造 (岩波講座 ソフトウェア科学 3)

これもけっこう有名な定番書籍だったけれど，今となっては古さが目立つ．記述言語はPascalだったっけ？そこがちょっと残念なところ*11
基本は悪くないので，程度の良い中古を入手するというのも十分アリ．Amazonだと千円ちょっとからあるみたいだね．

アルゴリズムC++

Bundle of Algorithms in C++, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms

http://www.amazon.com/dp/B004P8J1NA/
実物未確認だが目次とAmazon.comの書評での評判は良い．しかし原書に比べて版が古い上に，値段が値段だけに初心者にはお勧めしにくい．*12 *13

アルゴリズムC・新版―基礎・データ構造・整列・探索

和書としてはこっちの方が新しいのか．今度こそお勧めできる本だといいなあ．*14

その他．こんな感じのが多い．

アルゴリズムとデータ構造

アルゴリズムとデータ構造―基礎のツールボックス

アルゴリズムとデータ構造＜改訂 C言語版＞ (電気工学入門シリーズ)

データ構造と基本アルゴリズム

Cによるアルゴリズムとデータ構造

データ構造とアルゴリズム (新・情報 通信システム工学)

データ構造とアルゴリズム (電子情報通信学会大学シリーズ)

Data Structures and Algorithm Analysis in Java

Data Structures and Algorithms Using Python

サンプルコード集

http://www.oreilly.co.jp/books/9784873114286/
リファレンスとしてはかなり良い感じで一冊持っておいて損はなさそうだけど，初心者が「教科書」「入門書」として使うのには勧められない．初心者がいきなりこれから始めると，消化不良を起こす可能性が高いだろう．他の本をやって基本的なアルゴリズムをマスターした中級者〜上級者が，開発現場に常備しておくようなタイプの本．
なおオライリー本なので，洋書ならKindle版もあるそうだ．
http://www.amazon.com/dp/B0043D2EGI/

第二版も出版．和訳も出た．

Algorithms in a Nutshell: A Practical Guide

Algorithms in a Nutshell: A Practical Guide (English Edition)

アルゴリズムクイックリファレンス 第2版

Numerical Recipes 3rd Edition: The Art of Scientific Computing

数値演算アルゴリズムのサンプルコード集（＋解説）．日本語版は初版のままだと思う．*15日本語版が出た時にはけっこう話題になったと思う．

C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)

タイトルのこともあって知名度は高いけど，古さが気になるところ．

子供向け絵本

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

ソースがC/C++とJavaで書かれてるそうだし，目次を見た感じでは初心者によさげではある．*16内容については要確認．

追記：確認したら，なんかすごーく軽すぎ．目次だけなら立派なんだけどねえ．orz *17

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)

同じくなんかすごーく軽い．図が多くて懇切丁寧に説明していると言えば聞こえはいいが，まるで子供向けの絵本を見ている気分だよ．説明しているアルゴリズムも少ない．*18

アルゴリズムの絵本-プログラミングが好きになる9つの扉

身も蓋もねえ．．．orz

番外

アルゴリズムデザイン

この本をあげてる人もいるけれど，これまた目次を見る限り普通のアルゴリズム本ではない．特に初心者が学ぶべき基本アルゴリズムについては全く取り上げてないようなので，最低でも他に基本的なアルゴリズムを扱った本を一冊読んでマスターした後に読むべき本だろう．

応用

英語で言うと，1万語レベル超の単語帳や辞書なレベル．*19

発信型英語10000語レベル スーパーボキャブラリービルディング(CD3枚付) (CD BOOK)

英検Pass単熟語1級

ニュース英語パワーボキャビル4000語

ニュース英語パワーボキャビル3000語プラス

Oxford Dictionary of English

応用の方は各分野ごとに様々だ．タイトルに「アルゴリズムとデータ構造」のようなものが付かない「アルゴリズムとデータ構造」専門でない本も増えてくる．

Google PageRankの数理 ―最強検索エンジンのランキング手法を求めて―

http://www.amazon.com/dp/B005FMSVUO/

コンパイラの構成と最適化

最新コンパイラ構成技法

The Art of Multiprocessor Programming 並行プログラミングの原理から実践まで

http://www.amazon.com/dp/B00245A4U0/
http://www.amazon.com/dp/B008CYT5TS/ ：原書改訂版あり．Ver1.1くらいの感じ？ *20

アマトップクラスに迫る―コンピュータ将棋の進歩〈5〉

入門 自然言語処理

組合せ最適化―理論とアルゴリズム

コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用

Algorithms of the Intelligent Web

深層学習 (機械学習プロフェッショナルシリーズ)

たぶん他にも沢山あるはず．プログラムとアルゴリズムは不可分だから，新分野には多かれ少なかれ新しいアルゴリズムが存在すると思われる．

The Garbage Collection Handbook: The Art of Automatic Memory Management (Chapman & Hall/CRC Applied Algorithms and Data Structures series)

Computer Animation, Second Edition: Algorithms and Techniques (The Morgan Kaufmann Series in Computer Graphics)

Design and Analysis of Distributed Algorithms (Wiley Series on Parallel and Distributed Computing)

Algorithms in Computational Molecular Biology: Techniques, Approaches and Applications (Wiley Series in Bioinformatics)

C++ Algorithms for Digital Signal Processing (Encountering Biblical Studies)

How Debuggers Work: Algorithms, Data Structures, and Architecture

これはあくまで一例で，もちろんこんな本を全部読んでる人などいないだろう．たとえどれほどの名著でも，自分の専門分野と異なるものについては，必ずしもマスターする必要は無い．趣味でやるのは楽しいが，とてもじゃないが日本のプログラマにそんな時間も金も無いし，加えて日本企業じゃ一生そんな知識を必要としない低スキル低付加価値低利益率な会社の方が多い．*21プログラマーとしては，それが一番辛く虚しく悲しい．

なお，必ずしも全ての分野について書籍が出ているとは限らず，さらにそれ以上を学ぼうと思ったらソースコードを自分で読んだり*22，新しいアルゴリズムを自分で構築，或いは「発明」していったりする必要がある．それは自ら学ぶ姿勢のない人間には一生到達できない境地だ．

元記事に対して

まずは基礎です。

というより「（基本）アルゴリズムとデータ構造」自体がプログラミングの基礎だからねえ．．．

最初に読むのは、ソートとデータ構造が載った本で、このレベルはいろいろな本があるので、自分の使う言語での本や読みやすい本を選べばいいと思います。

なんでソートとデータ構造が最初かというと、いろいろ研究されていて話題が豊富なのと、多くのアルゴリズムがソートやデータ構造を使っていて、そこでアルゴリズムの性質が決まることが多いからです。

何を言ってるか，わけが分からないレベル．

ソートは基本アルゴリズムの一つだけど，「多くのアルゴリズムがソートを使っている」とか「そこでアルゴリズムの性質が決まる」とかは思ったことがないなあ．

ということで、平行アルゴリズムを扱った本。平行プログラミングの本ではThe Art of Multiprocessor Programming 並行プログラミングの原理から実践までも評価が高いのだけどこちらは平行プログラミングのための部品の設計の本で、問題をどのように平行に解くかというのは、この「並行コンピューティング技法」の方という印象。

おや？
アルゴリズムとデータ構造とは「プログラミングのための部品」そのものではないですか．

「The Art of Multiprocessor Programming」に出てくるような「部品」を組み合わせて，或いは改良して自分のプログラムに適応していくのが，プログラマに求められる能力の一つです．そういう意味ではアルゴリズムは「部品」というよりは「材料」で，アルゴリズムを扱うスキルには「材料をいかに加工するか？」というものも含まれると言えます．

他にも全般として方向性が無茶苦茶だなあ．「急がば回れ」とはいうけど回り道しすぎ．「（基本）アルゴリズムとデータ構造」だけなら，普通にそこそこの入門書を一冊読めばマスターできる．それで理解できないような人は素質がないからプログラマーの道を断念した方がかえってその人のためになる．他にお勧めされてる本にしても，悪書とまでは行かなくとも不適切な物が多いと思う．全般として初心者を惑わすだけの質の悪い記事になり下がってる．

番外

ところで，これはどこに分類すべきなんだろう．*23

The Art of Computer Programming Volume1 Fundamental Algorithms Third Edition 日本語版 (ASCII Addison Wesley Programming Series)

The Art of Computer Programming Volume 1,Fascicle 1:MMIX―A RISC Computer for the New Millennium日本語版 (Ascii Addison Wesley programming series)

The Art of Computer Programming (2) 日本語版 Seminumerical algorithms Ascii Addison Wesley programming series

The Art of Computer Programming Volume 3 Sorting and Searching Second Edition 日本語版 (Ascii Addison Wesley programming series)

The Art of Computer Programming,Volume 4, Fascicle 0 Introduction to Combinatorial Algorithms and Boolean Functions 日本語版 (ASCII Addison Wesley Programming Se)

The Art of Computer Programming Volume 4, Fascicle 1 Bitwise Tricks & Techniques; Binary Decision Diagarms 日本語版 (ASCII Addison Wesley Programming Se)

The Art of Computer Programming,Volume 4, Fascicle 2: Generating All Tuples and Permutations[日本語版] (アスキー・アジソンウェスレイシリーズ)

The Art of Computer Programming,Volume 4, Fascicle 3: Generating All Combinations and Partitions【日本語版】 (ASCII Addison Wesley Programming Se)

The Art of Computer Programming Volume 4, Fascicle 4 Generating All Trees -- History of Combinatorial Generation 日本語版 (ASCII Addison Wesley Programming Series)

Art of Computer Programming, Volumes 1-4A Boxed Set, The (Box Set)

関連

• http://d.hatena.ne.jp/JavaBlack/20070825/p1
• 「情報検索ことはじめ〜教科書編その2 (2011年決定版)」http://d.hatena.ne.jp/sleepy_yoshi/20110118/p1

プログラミング作法

ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか

余談

隣に座っているウチの会社の人に以下の本を薦めてみたんですよね。
アルゴリズムC・新版―基礎・データ構造・整列・探索
「言語に左右されない知識は積んでおいたほうがいいよ」ってことで。
そしたら

「まぁ大事なのかもしんないっすけどね。そんなのよりもJQueryとかDI使った各種フレームワーク系とかの使い方でも覚えてたほうがマシだと思うんですよ。そっちの方が俺ってすごい感があるじゃないですか。アルゴリズムの勉強なんてやるだけ時間の無駄じゃないっすかね。」

などと言われまして。

でもまぁ彼が言うことも全然間違ってない。

金を稼げる人になる、って意味ではまったく正しいことを言っていると思う。

でもまったく知らなくてもいいのか、っていうとそうでもないと信じたいんですけど。

どうなんでしょうかね。

http://d.hatena.ne.jp/KTF/20081022/1224625855

たしかに安易に日銭を稼ぐというのなら，日本企業ではそっちの方が費用対効果は高そうだ．なにしろ経営者が自ら「10年は泥のように働け」（≒「頭はいらない．十年したら過労死で死ね．」）とか言ってるくらいだもの．だからこそ日本は負けたんだけどね．

そして，たとえJQueryとかDIフレームワークとかの「使い方」があぶく銭になったとしても，そこには「俺ってスゴイ感」は全く感じないな．もし自分がその立場なら「せいぜいスゴイのはフレームワークの方であって，それに使われてるあんたじゃない．そこだけは誤解するな」と忠告だけはしておきたい．

PS．「プログラミング入門」タグ新規追加．

*1:あそこで紹介されてる勉強法は，すごくおかしい．異常すぎる．初心者があの方法を真似して，またも変な宗教に洗脳されないか心配になる．まるで第二の憂鬱本のようだ．

*2: アルゴリズムC・新版―基礎・データ構造・整列・探索も良さそうだけど，アルゴリズムイントロダクションと同様に難易度は高め．

*3:それと同じくらい，初心者にはプログラマが知るべき97のことは目を通しておくことをお勧めする．

*4:真面目に勉強する気のある初心者ならば「アルゴリズムイントロダクション」のような名著を旧版の中古で揃えるのもアリだろう．

*5:サンプルコード集の方は，古くても使えなくはないが，可能ならなるべく新しい物を探すべき．英語が苦手でもソースコードが分かればなんとかなるので，洋書に挑戦してみるのもお勧め．

*6:これができないと，プログラムに改良を加えた場合に，それが改良なのか改悪なのか，その影響がどのくらい大きいのか小さいのか，リスクやメリットなどが自分では判断できなくなる．

*7:改変のレベルにもよるけれど，こういうことはザラ．

*8:その書籍で使われている言語が，たまたま自分の使う言語と同じであるとは限らない．特に先端分野になればなるほど参考になる書籍の数も減り，そういう移植の必要性が高まる．

*9:「第３巻部分の発売について、近代科学社様に問い合わせをしたのですが、予定は無しだそうです」 http://d.hatena.ne.jp/mukaken/20081215/1229304150

*10:日本語訳は2版だが，洋書は3版．

*11:ちなみに自分が主に使っている以外の言語でも，アルゴリズム本のサンプルコードくらいは読めるようになっておいた方がいいよ．Pascalはさすがにどうかと思うけどね．

*12:ちなみにJava版もあるらしい．

Bundle of Algorithms in Java, Third Edition, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms

Algorithms

*13:http://d.hatena.ne.jp/kabus/20060603/1149299869

*14:斜め読みした感じではかなりよさげ．ただし難易度と値段は高めなのでそのつもりで．

*15:FFTとか懐かしい．

ニューメリカルレシピ・イン・シー 日本語版―C言語による数値計算のレシピ

これはC言語版．昔はFORTRAN版もあったんだよ．

Numerical Recipes in Fortran 90: Volume 2, Volume 2 of Fortran Numerical Recipes: The Art of Parallel Scientific Computing (Fortran Numerical Recipes , Vol 2)

*16:初版のページ http://www.sbcr.jp/books/img/takarabako/
目次を見る限りでは，とても素直な入門書のように見える．本当に見えるだけ．orz
なお，この目次を見ただけで，扱われてる内容がだいたい予測できるくらいにはなっておくべき．

*17:今の若い者には，このくらい軽くて中身の薄い本じゃないと売れないのかもしれない．ライトな娯楽小説ならまだ分かるけど，ライトな専門書って一体なんなんだよ．ライトな専門家を目指すためのライト解説書？それって要するに素人だよね？ http://d.hatena.ne.jp/JavaBlack/20091031/p1

*18:「Amazonで「アルゴリズム」と検索して、こんなのが上位に来る日本のプログラミング界は、大丈夫なのだろうか？相当クオリティの低い本だ。まるで名著の外殻だけtraverseしたかのような駄本。」http://d.hatena.ne.jp/nao-ichiro/20110430/1304141263
最初見た時は「そこまで言うか？」と思ったけど，今見るとだいたい同意だなあ．大丈夫じゃないよ，ホントに．orz

*19:本当に上級の人向けの単語集などというのは存在せず，そのレベルの人は多読多聴によって覚えたりするんだそうな．私は上級じゃ無いから分かりません．

*20:

The Art of Multiprocessor Programming, Revised Reprint

*21:「ITを専攻している学生達からは、「就職時にITスキルが問われないのだとしたら、大学でやっていることには何の意味があるのか」という質問が出ていたのだけど、明確な回答はなかったと思う。その人たちは、ちょっとショックを受けていたような気がする。」 http://d.hatena.ne.jp/itoyosuke/20071101/1193932945

*22:いずれも古い本だけど，これなんかもそれに近い世界だ．

詳解TCP/IP〈Vol.2〉実装

Lions’ Commentary on UNIX (Ascii books)

*23:どちらかというと，単語帳というよりは，あのOEDみたいな感じかな．．．

The Oxford English Dictionary, Second Edition (20 Volume Set<5 Boxes>)