自己組織化リスト

自己組織化リストは、平均アクセス時間を改善するために、何らかの自己組織化ヒューリスティックに基づいて要素を並べ替えるリストです。自己組織化リストの目的は、より頻繁にアクセスされる項目をリストの先頭に移動することで、線形検索の効率を改善することです。自己組織化リストは、最良の場合、要素アクセスにほぼ一定の時間を実現します。自己組織化リストは、実行時にさまざまなクエリ分布に適応するために、再編成アルゴリズムを使用します。

自己組織化リストの概念は、ディスクやテープ上に保存されたファイル内のレコードのアクティビティ組織化というアイデアに由来しています。^[1]自己組織化ファイルとリストに関して頻繁に引用される議論の 1 つは、Knuth のものです。^[2] John McCabe は、アクセスされた項目をリストの先頭に移動する Move-to-Front (MTF) 戦略のアルゴリズムの複雑さの分析を初めて行いました。^[3]彼は、ランダムに順序付けられたリストが最適な順序になるのに必要な平均時間を分析しました。リストの最適な順序とは、最もアクセスされる項目が最初になるように、項目がリスト内で必要になる確率によって順序付けられる順序です。最適な順序は事前にわからない場合があり、時間の経過とともに変化することもあります。

McCabe は、アクセスされた項目をリスト内のその前の項目と交換する転置戦略を導入した。彼は、平均的なケースでは、転置は、極限でレコードの最適な順序に近づく上で、MTF と少なくとも同程度に機能するという推測を立てた。この推測は、後に Rivest によって証明された。^[4] McCabe はまた、転置または MTF ヒューリスティックのどちらを使用しても、ヒューリスティックが N 回目のアクセスごとにのみ適用された場合でも、レコードの最適な順序に近づくこと、およびレコードを再配置する相対的なコストと、最適な順序にすばやく近づく価値を反映する N の値を選択できることにも注目した。さらに改良が加えられ、Rivest、Tenenbaum と Nemes、Knuth、Bentley と McGeoch などの研究者によってアルゴリズムが提案された (例: 自己組織化順次検索ヒューリスティックの最悪ケース分析)。

自己組織化リストは、データ構造の使用に応じて リンク リストなどのデータ構造を変更するアルゴリズムである自己組織化ヒューリスティックを使用します。

自己組織化ヒューリスティックの例には次のものがあります。

• 最前面へ移動(または「先頭へ移動」) - 頻繁に使用される情報や最近使用された情報が最上部に表示されるため、リスト全体を移動しなくてもすぐに見つけることができます。
• 自己学習頻度リスト(または「アクセス頻度による順序」) - GUI メニューのオプション リストを再配置し、ユーザーが最も頻繁に選択するオプションが上位に表示されるようにします。
• ランダムな位置に再挿入
• 後ろに移動 - ミラーサーバーのリストを整理するために使用されます。これにより、ダウンロードに使用されたサーバーはキューの後ろに移動され、ユーザーが再度選択しないようにします。

• 自己組織化(PDF)、2004年、オリジナル(PDF)から2012年4月14日にアーカイブ、2011年12月13日に取得
• NIST DADSエントリ
• A Drozdek、Java のデータ構造とアルゴリズム 第 3 版
• Amer, Abdelrehman; B. John Oommen (2006)、「Lists on Lists: A Framework for Self-organizing Lists in Environments with Locality of Reference」、Lecture Notes in Computer Science、vol. 4007、doi :10.1007/11764298、ISBN 978-3-540-34597-8