リスト更新の問題

リスト更新問題またはリスト アクセス問題は、オンライン アルゴリズムの競合分析の研究で使用される単純なモデルです。リスト内のアイテム セット (アイテムへのアクセス コストがリストの先頭からの距離に比例する) (リンク リストなど) とアクセスの要求シーケンスが与えられた場合、問題は、アクセスの総コストが最小になるようにリストを並べ替える戦略を見つけることです。並べ替えはいつでも実行できますが、コストが発生します。標準モデルには、2 つの並べ替えアクションが含まれます。

• アクセスされている項目を現在の位置より前の任意の場所に自由に転置します。
• リスト内の隣接する2つのアイテムを交換するための単位コストの有料転置。アルゴリズムのパフォーマンスは、さまざまな敵対者モデルの下での敵対者によるリクエストシーケンスの構築に依存します。

この問題のオンライン アルゴリズムでは、以前に要求された項目に関する知識のみに基づいて要素を並べ替え、要求を処理する必要があります。そのため、最初の要求を処理する前に要求シーケンス全体を確認し、完全な戦略を考案するオフライン アルゴリズムと比較して、その戦略のコストが最適にならない可能性があります。

この問題は、本来の用途に加え、バロウズ・ウィーラー変換に従ってグローバル コンテキストと圧縮性を改善する問題と非常に類似していることが示唆されています。この変換に従うと、ファイルは局所的に高い頻度を持つ大きな領域を持つ傾向があり、頻繁に出現する文字をゼロ、つまり「リスト」の先頭に移動する傾向がある手法によって圧縮効率が大幅に向上します。このため、Move-to-Front および頻度カウントのメソッドとバリアントは、圧縮性を改善するために BWT アルゴリズムに従うことがよくあります。

敵対者とは、アルゴリズムALGのリクエストシーケンスを選択できるエンティティです。ALGの戦略に基づいて変更できるかどうかに応じて、敵対者にさまざまな権限が与えられ、これらの敵対者に対するALGのパフォーマンスが測定されます。 ${\displaystyle \sigma}$${\displaystyle \sigma}$

無意識の敵対者は、 ALGを実行する前にリクエストシーケンス全体を構築し、最適なオフライン価格を支払う必要がある。これは、${\displaystyle \sigma}$${\displaystyle OPT(\sigma )}$${\displaystyle ALG(\sigma )}$

適応型オンライン攻撃者は、オンラインアルゴリズムの以前の結果に基づいて次のリクエストを作成しますが、そのリクエストに対して最適かつオンラインで支払います。

適応型オフライン攻撃者は、オンラインアルゴリズムの以前の結果に基づいて次のリクエストを実行しますが、最適なオフライン コストを支払います。

多くのリスト更新問題に対する競合分析は、最適オフラインアルゴリズム (OPT) の正確な性質に関する具体的な知識なしに実行されました。O( n 2 ^l ( l -1)!) 時間と O( l !) スペースで実行されるアルゴリズムが存在します。ここで、nはリクエストシーケンスの長さ、lはリストの長さです。^[1] リクエストシーケンスの長さに依存する最もよく知られている最適オフラインアルゴリズムは、O(l^2(l−1)!n) 時間で実行され、2014 年に Srikrishnan Divakaran 博士によって発表されました。^[2]

有料の転置は、一般に、最適なアルゴリズムに必要です。リスト ( a、b、c ) を考えてみましょう。ここで、a はリストの先頭にあり、リクエスト シーケンスはc、b、c、bです。無料の交換のみを使用する最適なオフライン アルゴリズムのコストは 9 (3+3+2+1) ですが、有料の交換のみを使用する最適なオフライン アルゴリズムのコストは 8 です。したがって、無料の転置のみを使用して最適なオフライン アルゴリズムを実現することはできません。

最適リスト更新問題は、(Ambühl 2000) によって NP 困難であることが証明されました。

オンライン アルゴリズムALG は、任意の入力に対して OPT のc倍以上悪いパフォーマンスを示す場合、競合率c を持ちます。つまり、すべての有限長の要求シーケンスに対して、となるような が存在する場合です。オンライン アルゴリズムは決定論的またはランダム化のいずれかであり、この場合のランダム化は、気づかない敵に対して本当に役立つことがわかります。 ${\displaystyle \alpha \geq 0}$${\displaystyle \sigma}$${\displaystyle ALG(\sigma )-c.OPT(\sigma )\leq \alpha }$

ほとんどの決定論的アルゴリズムは、次の 3 つのアルゴリズムのバリエーションです。

MTF（最前線へ移動）

アイテムにアクセスした後、他のアイテムの順序を変更せずにリストの先頭に移動します

TRANS（転置）

項目にアクセスした後、その項目を直前の項目と入れ替えます。

FC (頻度カウント)

各項目について、その項目へのアクセス回数の頻度カウントを維持します。要素がアクセスされると、その頻度カウントが増加し、頻度の降順でリストが並べ替えられます。

これらすべてが自由転置のみを使用していることに注意してください。TRANS と FC はどちらも競合的ではないことがわかります。ポテンシャル法分析 (Sleator & Tarjan 1985) を使用した古典的な結果では、MTF が 2 競合的であることが証明されました。証明には OPT の明示的な知識は必要ありませんが、代わりに反転の数、つまり MTF と OPT のリストで逆の順序で発生する要素の数をカウントします。

決定論的アルゴリズムには長さlのリストに対しての下限があり、MTF は実際には最適な決定論的リスト更新アルゴリズムです。決定論的アルゴリズムの場合、攻撃者の種類は関係ありません。攻撃者は決定論的アルゴリズムのコピーを独自に実行して、最も破滅的なシーケンスを事前に計算できるためです。 ${\displaystyle 2-{\frac {2}{l+1}}}$

次の単純なランダム化アルゴリズムを考えてみましょう。

少し

リスト内のすべての項目について、ビットを維持します。すべてのビットを均一かつランダムに 0 または 1 に初期化します。項目がアクセスされると、ビットを反転し、1 の場合は先頭に移動します。それ以外の場合は移動しません。

このアルゴリズムはランダムとは言い難い。実行中ではなく、最初にすべてのランダムな選択を行う。BIT は決定論的限界を破ることが判明した。つまり、無知な敵に対しては MTF よりも優れている。7/4 の競争力がある。COMB など、BIT よりも優れたパフォーマンスを発揮するランダム化アルゴリズムは他にもある。Boris Teia は、ランダム化リスト更新アルゴリズムの下限が 1.5 であることを証明した。^[3]

要素の挿入と削除が可能なリスト更新問題は、リスト要素へのアクセスのみが許可される静的リスト更新問題とは対照的に、動的リスト更新問題と呼ばれます。 の上限は動的モデルにも当てはまります。 ${\displaystyle 2-{\frac {2}{l+1}}}$

さまざまなコスト モデルもあります。通常のフル コスト モデルでは、位置 i にある要素へのアクセスにはi のコストがかかりますが、最後の比較はどのアルゴリズムでも避けられません。つまり、iの前にi-1 個の要素が存在します。部分コスト モデルでは、リクエスト シーケンス内の要素の数に合計されるこれらの最終比較コストは無視されます。ユニティ以外の有料転置のコストについては、P ^dモデルが使用されます。

• オンラインアルゴリズム
• 競合分析
• キャッシュアルゴリズム

• Sleator, D. ; Tarjan, R. (1985)、「リスト更新とページングルールの償却効率」、Communications of the ACM、28 (2): 202–208、CiteSeerX  10.1.1.367.6317、doi :10.1145/2786.2793、S2CID  2494305。
• ボロディン、A. ; エルヤニフ、R. (1998)。オンライン計算と競合分析。ケンブリッジ大学出版局。ISBN 978-0-521-56392-5。

• Ambühl, C. (2000)、「オフラインリスト更新はNP困難」、Springer、pp. 42–51