根据最近的先前选择加权随机选择

我想选择一个列表元素,其中每个元素的权重是自上次选择以来的长度。 我可以创建一个LRU(最近最少使用的)列表,其中加权函数基于队列中的位置,这将是优雅的,除了最初所有元素应该被加权相等的事实。 在选择之后将权重减去或除以一定数量似乎并不直观。是否有更好的方法可能使用数学概念,如对数或逆? (不是我的强项)     
已邀请:
这样的事情怎么样: 设
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
”用于归一化参数范围。对于加权函数的某些选择,可能不需要这种标准化。     

要回复问题请先登录注册