抽象データ型

抽象データ型にはインターフェースの大きいものと小さいものがある。例えば、stackとqueueはlistよりも小さい。listとsetはmapよりも小さい。もちろん、配列が一つあればどんなデータ構造も表現できる(fortran!)けれど、面倒な手続きを介さなければならないのでは困ったものだ。
同じ抽象データ型でも最適なデータ構造は用途によって異なる。ArrayListとLinkedListでは特性が全く違っているが、大抵は中庸のDequeを使えば上手く行く。HashMapとTreeMapに対するTrieMapというのもあり得るかもしれない。
基本的にロジックは抽象データ型に対するものでデータ構造に対するものではない。抽象データ型に向けて実装しておけば後からデータ構造を交換できる。メモリ効率は事前に計算できるが、速度効率を事前に計算するのはちょっと難しい。キャッシュやパイプラインの効率まで気にしたら「もう無理」という感じだが、その辺りが強烈に効くこともしばしば。
そして近未来にはマルチコアの競合効率が支配的になるだろう。きっと排他アルゴリズムも差し替えられると便利になる。単一代入を除いた常識の範囲内ではRubyのブロック渡しsynchronizeのような形が有望かな。