プログラミング作法 第２章 アルゴリズムとデータ構造 ２．１０ まとめ

　アルゴリズムの選択にはいくつかの段階がある。まず使えそうなアルゴリズムとデータ構造を吟味すること。そしてプログラムでどの程度の量のデータを処理する見込みなのかを考える。自分の問題に使用されるデータがそれほど多くなければ、単純なテクニックを選択しよう。ただしデータが増大する可能性があるなら、膨大な入力に対処できるようにスケールアップできない設計手法は除外すること。次に、可能ならライブラリや言語の機能を利用する。それが無理なら、短く単純でわかりやすい実装を書くなり拝借するなりしてみよう。とりあえずここまでの段階で頑張ってみること。もっと高度なテクニックにグレードアップするのは、時間を計測してみてあまりに遅いことが判明するまで思いとどまったほうがいい。

　データ構造には膨大な種類があり、特殊な状況で優れた性能を得るのに欠かせないデータ構造も一部にあるが、大半のプログラムはほぼ配列とリストとツリーとハッシュテーブルを基本に作られている。

　それぞれの処理には期待される計算時間があり、たいていはそれによってこのデータ型(や実装)がある特定のケースにどの程度適しているかが決まる。配列は任意の要素に対して一定の時間でアクセスできるが、美しく伸縮できない。リストは挿入や削除にはうまく対応できるが、要素にランダムアクセスするにはＯ(n)の時間がかかる。その点ツリーとハッシュテーブルはほどよい折衷案として利用でき、バランスの基準が保たれる限り、特定の項目に対して高速にアクセスできるし簡単に伸張できる。

この章のまとめは上に引用したように、プログラム設計における問題解決のヒントになりそうなことを短くまとめてくれています。大事な箇所だ。