自己組織化リニア検索への道

我々は、さまざまな要素がアクセスされる確率が与えられないにもかかわらず、より頻繁にアクセスされる要素がリストの前の方に見つかるようにリニアリストを適応させる技術を考察する。主な結果は2つのセクションで議論される。最も興味深いのは、要素が連続してk回リクエストされて初めて前に移動される技術に関するものである。もう一つは、技術的により難しいセクションで、アクセスされるたびに要素をリストの先頭に移動させるヒューリスティックの分析を扱っている。この手法がいくつかの興味深い確率分布の下でどのように機能するかが議論される。要素をk回連続してアクセスした後に前方に移動させる技術に関する2つの基本的なアプローチが議論される。最初のアプローチは、同じk回のリクエストが行われた後に変換を実行する。第二のアプローチは、リクエストを少なくともkのバッチにまとめ、バッチの最後のkリクエストが同じ場合にのみアクションを実行する。リクエストされた要素をリストの前に移動させる変換を採用することで、第二のアプローチは、k ≥2のすべての非自明な確率分布の下でより速い平均検索時間をもたらすことが示されている。また、「周期的」アプローチ（k = 2）は、平均検索時間が最適な順序の1.21..倍を超えることはないことも示されている。より直接的なアプローチにおいては、同じ制約の下で1.36..の比率が示されている。シンプルな前側移動ヒューリスティック（k = 1）を研究する中で、特定の分布に対してこの手法が最適な順序のπ/2倍の平均プローブ数につながることが示されている。興味深い分布のクラスの中で、これは最悪の平均的な振る舞いであることが示されている。