2

アプリケーションの加重アルゴリズムを考え出そうとしています。アプリケーションでは、さまざまな要素に使用できるスペースが限られています。すべてのスペースが占有されると、アルゴリズムは、新しい要素用のスペースを作成するために、削除するのに最適な要素を選択する必要があります。

この決定に影響を与えるはずのさまざまな属性があります。例えば：

  • T：最後にアクセスしてからの時間。（しばらくアクセスされていないものを交換することをお勧めします。）
  • N：アクセスされた回数。（何度もアクセスされていないものを交換することをお勧めします。）
  • R：新しい要素のためのスペースを作るために削除する必要がある要素の数。（最小限の要素を置き換えるのが最善です。理想的には、これは、置き換えられる各要素のT属性とN属性も考慮に入れる必要があります。）

私には2つの問題があります：

  1. これらの各属性に与える重みを計算します。
  2. 要素の重量を計算する方法を理解する。

（1）このような重みを考え出すのは非常に主観的だと思いますが、各属性にどの程度の重みを与えるかを決めるのに役立つ標準的な方法などがあることを期待していました。たとえば、2つのサンプル要素のセットを考え出し、手動で2つを比較して、どちらを最終的に選択するかを決定する方法があるのではないかと考えていました。次に例を示します。

要素A：N = 5、T=2時間前。
要素B：N = 4、T=10分前。

この例では、Aを、もう一度アクセスされたものの、Bと比較して長い時間アクセスされていないため、置き換えられる要素として選択する必要があります。この方法は、時間がかかるようです。多くの時間、そして多くの難しい、主観的な決定をすることを含みます。さらに、最後に結果の重みを考え出すのは簡単ではないかもしれません。

私が思いついたもう1つの方法は、さまざまな属性の重みを任意に選択してから、しばらくの間アプリケーションを使用することでした。アルゴリズムに明らかに問題があることに気付いた場合は、入って重みを少し変更することができます。これは基本的に「推測とチェック」の方法です。

これらの方法はどちらもそれほど素晴らしいとは思えないので、もっと良い解決策があることを願っています。

（2）体重を計算した後、どちらの方法で体重を計算するのが最適かわかりません。すべてを追加するだけでいいですか？replacementWeight（これらの例では、最も高い要素が置き換えられる要素であると想定しています。）

replacementWeight = .4*T - .1*N - 2*R

またはすべてを掛けますか？

replacementWeight = (T) * (.5*N) * (.1*R)

重みに定数を使用しないのはどうですか？たとえば、「時間」（T）は重要かもしれませんが、特定の時間が経過すると、それほど大きな違いはありません。基本的に、私はそれをすべて「多くの時間が経過した」ビンにまとめます。（たとえば、8時間と7時間の間に時間差がありますが、この2つははるかに新しいため、この差は1分と5分の差ほど重要ではない可能性があります。）（または別の例：（R ）1つまたは2つの要素で問題ありませんが、5つまたは6つを置き換える必要が生じた場合は、大幅に重み付けする必要があります...したがって、線形であってはなりません。）

replacementWeight = 1/T + sqrt(N) - R*R

明らかに（1）と（2）は密接に関連しているので、この種のアルゴリズムを考え出すためのより良い方法があることを望んでいます。

4

2 に答える 2

2

あなたが説明しているのは、キャッシュ置換ポリシーを選択するという古典的な問題です。どのポリシーが最適かはデータによって異なりますが、通常は次のように機能します。

まず、常に新しいオブジェクトをキャッシュに保存し、R最悪のオブジェクトを削除します。オブジェクトを保存する必要があるかどうかを事前に知る方法はありません。オブジェクトが役に立たない場合は、すぐに再びキャッシュから削除されます。

人気のあるsquidキャッシュは、次のキャッシュ置換アルゴリズムを実装しています。

  • 最近使用されていない（LRU）：
    • replacementKey = -T
  • ダイナミックエイジング（LFUDA）での使用頻度が最も低い：
    • replacementKey = N + C
  • 貪欲-デュアルサイズ-頻度（GDSF）：
    • replacementKey = (N/R) + C

Cここでは、キャッシュの経過時間係数を指します。C基本的にreplacementKey最後に追い出された（またはゼロ）アイテムのです。

注：replacementKeyは、オブジェクトが挿入またはアクセスされたときに計算され、オブジェクトと一緒に保存されます。最小のreplacementKeyを持つオブジェクトが削除されます。

LRUはシンプルで、多くの場合十分です。キャッシュが大きいほど、パフォーマンスが向上します。

LFUDAとGDSFはどちらもトレードオフです。LFUDAは、大きなオブジェクトへの1回のヒットが小さなオブジェクトの多くのヒットを構成すると仮定して、人気が低くても大きなオブジェクトを保持することを好みます。GDSFは基本的に反対のトレードオフを行い、少数の大きなオブジェクトよりも多くの小さなオブジェクトを維持します。あなたが書いたものから、後者はぴったりかもしれません。

これらのいずれもニーズを満たさない場合は、たとえば線形回帰を使用して、式と最適なアルゴリズムのパフォーマンスの違いである後悔Tを最小限に抑えることで、の最適値を計算し、 （NそしてRそれらを組み合わせるためにさまざまな式を比較して）できます。

于 2012-02-19T08:29:51.210 に答える
1

これは完全に主観的な問題です-あなた自身が指摘しているように。そして、明確な可能性は、テストケースがAよりBを好むペア（A、B）で構成されている場合、AよりB、BからCだけでなく、AよりもCを好むことがわかるかもしれません-つまり、注文。

注意しないと、関数が存在しない可能性があります。

係数と指数のさまざまなパラメーターを使用して、入力変数のスカラー関数を定義できる場合は、回帰を使用して前述のパラメーターを推定できる可能性がありますが、パラメーターが多い場合は、非常に多くのデータが必要になります。

これは、最初にデータを確認してモデルを識別し、次にそのモデルを使用してモデルの特定の実現を推定するという古典的な統計家のアプローチです。この主題に関する大きな本があります。

于 2012-02-19T03:13:36.743 に答える