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

概要

配列やリストから"探索するキーとなるもの"と一致するものを見つけるしらみ潰し探索(線形)において、探索するキーによく探索されるキーが偏っている場合に適用できる工夫です.
Facebookシェア Twitterツイート LINEで送る このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
0
条件
  • よく探索されるキーに偏りがある
  • または一度探索されたキーで再度探索されることがない
効果
  • 探索に平均的にかかる時間が早くなる
  • 線形探索よりは平均的に早くなる
ポイント
  • 配列で管理されているより連結リストの方が効率的

解 説

配列やリストの先頭から順々にキーと一致しているかを見ていって一致していたらそれを取得するというのは、探索ではよくあると思います. 実装は容易ですが、効率がかなり悪く配列やリストの末尾に対象があるときはだいぶ時間がかかってしまいます.
キー偏りありで効率よく線形探索したい
この時間がかかってしまうのをなるべく改善する方法があります. それは毎回探索して見つけたら先頭に移動するという方法です. そうすると次回から先頭から見ていくときに見つけるまでに時間がかからなくなります. ただし条件があって、 ・何回も同じキーで探索する というのが必要です. 上記を満たしていれば、単純だった線形探索が用意に高速化することができます. あくまでアルゴリズムは変わらないので、平均的にな探索時間が短くなるだけです.
線形探索に工夫を入れる
上記のような工夫を取り込んだものを自己組織化探索とかっこよく言います. この自己組織化探索においては、先頭に要素移動して移動した分他のを後ろに移動する必要があるので、配列ではなく、リストがおすすめです.要素の入れ替えが起こるたびに配列の要素をすべてずらしていたら結局遅くなってしまいます.
自己組織化探索の実装時
自己組織化探索の図解
先頭に移動させることで頻繁に探索されるものがすぐに見つかるようにしました. それは見つけた要素がまた探される可能性が高かったためです. 逆に見つけた要素が再度探索されることがなければ、先頭でなく末尾に持っていくことも考えられます. 実装もやることもほぼ同じで移動先を末尾に変更するのみです.
先頭でなく末尾におく
この章を学んで新たに学べる
Comments

Reasons
>>隠す