キー偏りありで効率よく線形探索したい

配列やリストの先頭から順々にキーと一致しているかを見ていって一致していたらそれを取得するというのは、探索ではよくあると思います. 実装は容易ですが、効率がかなり悪く配列やリストの末尾に対象があるときはだいぶ時間がかかってしまいます.

この時間がかかってしまうのをなるべく改善する方法があります. それは毎回探索して見つけたら先頭に移動するという方法です. そうすると次回から先頭から見ていくときに見つけるまでに時間がかからなくなります. ただし条件があって、 ・何回も同じキーで探索する というのが必要です. 上記を満たしていれば、単純だった線形探索が用意に高速化することができます. あくまでアルゴリズムは変わらないので、平均的にな探索時間が短くなるだけです.

上記のような工夫を取り込んだものを自己組織化探索とかっこよく言います. この自己組織化探索においては、先頭に要素移動して移動した分他のを後ろに移動する必要があるので、配列ではなく、リストがおすすめです.要素の入れ替えが起こるたびに配列の要素をすべてずらしていたら結局遅くなってしまいます.

先頭に移動させることで頻繁に探索されるものがすぐに見つかるようにしました. それは見つけた要素がまた探される可能性が高かったためです. 逆に見つけた要素が再度探索されることがなければ、先頭でなく末尾に持っていくことも考えられます. 実装もやることもほぼ同じで移動先を末尾に変更するのみです.