当前位置：文江博客话题详情

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

发布于 2024-10-07 17:35:21 字数 189 浏览 8 评论 0原文

我想选择列表中的一个元素，其中每个元素的权重是自上次选择以来的时间。

我可以创建一个 LRU（最近最少使用）列表，其中基于队列中的位置对函数进行加权，这将是很优雅的，除了最初所有元素都应同等加权这一事实。

在选择权重后仅仅将权重减去或除以一定的量似乎在直觉上并不正确。有没有更好的方法也许使用对数或倒数等数学概念？（不是我的强项）

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

鹿童谣 2024-10-14 17:35:21

怎么样：

让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”用于标准化参数范围。也许对于权重函数的某些选择不需要这种归一化。

How about something like this:

Let n = number of elements, list = array of elements, 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]

Here we divide the list into two parts, weighted and uniform, with boundary tracked by watermark. Initially the weighted part is empty, but gradually it grows, in the end consuming the entire list.

random() is a function that returns a random number in [0.0, 1.0).

weight(x) is a function from [0.0, 1.0) into [0.0, 1.0) that defines required weighting behaviour.

The "r * n / watermark" as argument of weight() serves to normalize the argument range. Maybe this normalization is not needed for some choices of the weighting function.

回复收藏 0 原文

~没有更多了~