隨機選擇加權最近的選擇

Question

我想選擇一個列表中的元素，其中每個元素的重量是自上次選擇後的時間。

我可以做一個LRU（最近最少使用）列表，根據隊列中的位置加權一個函數，除了事實上最初所有元素應該加權相等之外，這將是優雅的。

只是在選擇一定量後減去或除以一定量，看起來並不直觀。有沒有更好的方法可能使用數學概念，如對數或反轉？ （不是我的強項）

Answer 1

怎麼是這樣的：

讓n = 號元素的，list = 數組元素的，watermark：= 0

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] 

這裏我們將列表分成兩部分，加權和統一，邊界由watermark跟蹤。最初的加權部分是空的，但逐漸增長，最終消耗整個列表。

random()是一個返回[0.0，1.0）中的隨機數的函數。

weight(x)是從[0.0,1.0）到[0.0,1.0）中定義所需加權行爲的函數。

作爲參數weight()的「r * n/watermark」用於標準化參數範圍。也許這種標準化對於權重函數的一些選擇是不需要的。