1

各要素が最後に選択されてからの時間によって重み付けされているリストの要素を選択したいと思います。

キュー内の位置に基づいて関数を重み付けすることで、LRU (最近使用されていない) リストを作成できます。これは、最初はすべての要素を均等に重み付けする必要があることを除けば、洗練されたものです。

重みを選択した後で、重みを特定の量で減算または除算するだけでは、直感的に正しくないように思えます。おそらく対数や逆数などの数学的概念を使用するより良い方法はありますか? （私の長所ではありません）

4

1 に答える 1

0

このようなものはどうですか：

=要素数、n=要素の配列、 : = 0 とします。listwatermark

r := random()
i := floor(r * n)

if i >= watermark :
    index := i
    watermark := watermark + 1  // weighted part grows
else :
    index := floor(weight(r * n / watermark) * watermark)
endif

move list[index] to list[0]     // shifting elements list[0..index-1] up one place
result := list[0]

ここでは、リストを重み付きと均一の 2 つの部分に分割し、境界を で追跡しwatermarkます。最初は重み付けされた部分は空ですが、徐々に大きくなり、最終的にはリスト全体を消費します。

random()[0.0, 1.0) の乱数を返す関数です。

weight(x)[0.0, 1.0) から [0.0, 1.0) への関数で、必要な重み付け動作を定義します。

r * n / watermarkの引数としての " "weight()は、引数の範囲を正規化するのに役立ちます。重み付け関数の一部の選択では、この正規化は必要ないかもしれません。

于 2010-12-15T15:39:47.150 に答える