プログラミング作法2 - Riverside Learning LABO(Skill/Idea/Code)

第2章　アルゴリズムとデータ構造
安定した結果を出すには一定の経験を積むしかない
不慣れな分野に取り組むときは、その分野で既に何が解明されているのかを調べないと、
優れた手法のあることに気付かずに、下手なやり方で苦労することになる。

・逐次検索(sequential search)はデータが少なければ十分実用(逐次検索は線形検索(linear search)ともいう)
・もう少し多い場合は二分検索(binary search)を使う(バイナリサーチではデータが事前にソートされている必要がある)
・汎用的なソート手法としてクイックソートがある (C.A.R Hoare/1960)(ある値を選択して以上/以下に分割し、それを再帰的に行う。
しかし値が全て同じなら n の 2 乗に比例する時間がかかるANSI C なら qsort や bsearch が用意されている、Java の例もあり)

O 記法(O-notation)による、実行時間を n の関数に見立てた計算量(complexity)の算出。
これだけではなく最悪のケースと期待される動作の把握が必要になる。以下に重要となるケースを挙げる。

記法名称例
O(1) 定数配列インデックス
O(logn) 対数二分検索 (段階ごとに半分)
O(n) 1 次文字列比較
O(nlogn) nlogn クイックソート
O(n2) 2 次単純なソート手法
O(n3) 3 次行列乗算
O(2n) 指数集合分割問題 (全ての可能性の評価)

・巡回セールスマン問題等の指数的アルゴリズムの問題は近似値で代用されることが多い
・配列は要素数が可変だったり膨大なときには別のデータ構造を検討する
・アロケートを 1 バイトずつではなくある程度まとめて行う
・memcpy よりも memmove の方が安全でおすすめ*1
・リストは頻繁に順序の変更されるときに向く
・書式文字列を引数に取るという方法
・ルートからリーフまでの個々の経路がほぼ同じ長さのツリーをバランス木(balanced tree)という
・再帰が最終的に自分自身の呼び出し結果の返すことを末端再帰(tail recursion)という
・間順走査(in-order traversal)は部分木を左から右へ行く中間で処理の行うことをいう
・降順走査(post-only traversal)は子を訪れてから現在のノードに対する処理の行うことをいう
・ハッシュをうまく使えばルックアップや挿入、削除が一定時間で可能になる
・ハッシュの配列サイズはルックアップ作業が O(1) になるような大きさにする
・ASCII 文字用のハッシュ関数の乗数には 31 と 37 が適している

アルゴリズムの使用では、まず使えそうなアルゴリズムとデータ構造の吟味し、その上でどの程度の量のデータを処理するのか考え、更にライブラリや言語の機能で使えるものがないか考える。それでも適当なものがなければ、短い実装を書くかどこかから拝借する。

あくまで高度なテクニックに頼るのは上記を行って、なおかつ性能の問題が出たときにする。ほとんど場合、配列、リスト、ツリー、ハッシュで対処できる。

*1:重複アドレスでも上書きしない