random - 随机选择与最近的先前选择加权

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) 的函数，它定义了所需的加权行为。

r * n / watermark作为参数的“ ”weight()用于规范化参数范围。对于某些加权函数的选择，可能不需要这种归一化。