Optimized C++ ―最適化、高速化のためのプログラミングテクニック

89

5.4　効率的整列アルゴリズム

クにある場合など）ときに顕著となる。しかし、内挿探索は最高速の探索ではない。

•

キーをハッシュテーブルの配列の添字に変換するハッシングで平均

O(1)

時間でレコードを探

し出すことができる。ハッシングは、どんなキー・値対のリストでも機能するわけではない。

特別に構成したハッシュテーブルが必要だ。ハッシュテーブルの要素は等価性だけが比較でき

ればよい。ハッシングは最悪時

O(n)

の性能で、探索するレコードよりも多数のエントリが必

要なこともある。しかし、（

1

月から

12

月までの名前やブログラミング言語のキーワードのよ

うに）表が固定なら、そういう異常な場合を避けることができる。

5.3.2

　すべての探索は

n

が小さいなら等しい

1

つの要素だけの表における探索コストはどうだろうか。どの探索アルゴリズムを使うかで違い

があるだろうか。整列済みの表に対して、線形探索、二分探索、ハッシュテーブル探索の最良のア

ルゴリズムでの探索コストを表

5-2

に示す。問いへの解答は、「小さな表ではすべての方法が同じ

個数だけ調べる」というものだ。しかし、

10

万エントリの表では、時間コスト関数の支配項が効

いて、物事は違ってくる。■

表

5-2

 表のサイズと探索のための平均アクセス個数

表のサイズ 線形 二分 ハッシュ

1 1 1 1

2 1 2 1

4 2 3 1

8 4 4 1

16 8 5 1

26 13 6 1

32 16 6 1

5.4

　効率的整列アルゴリズム

整列アルゴリズムには ...