我有一个项目清单。当我创建列表时，每个项目都有平等的机会被选中。但是当一个项目被选中时，它的机会下降，而其他的机会上升。如果在此过程中添加了一个新项目，它应该有最高的机会被选中，而它的机会随着被选中而下降。我正在寻找一个可以实现这一点的好算法是 C#。
概括的想法：我有 5 个项目，随着时间的推移，所有 5 个项目将在 20% 的时间内被选中。我试图将选择保持在接近 20% 的范围内，减少异常值。如果存在一个，它将被更多/更少选择以使其重新排列。
问问题
2297 次
6 回答
9
使用桶加权队列：不使用列表，而是将您的集合划分为桶 - 每个桶都有相关的检索频率。项目在被选中时从频率较高的桶移动到频率较低的桶。
实现这一点的一种简单方法是为每个存储桶分配一个值范围，并在组合范围内生成一个随机数以选择一个存储桶。您可能希望将此集合抽象为某种类，这样您就不会让消费者接触到细节。
算法：
最初，所有项目都在同一个（顶级）存储桶中开始。
当您选择一个项目时，将其从它所在的存储桶移动到下一个较低的存储桶。如有必要，创建下一级存储桶。
添加新项目时，将其添加到最顶部（最常用）的存储桶中。
要随机选择一个项目，首先选择一个桶，然后在桶中选择一个项目。将所选项目向下移动到下一级存储桶中。请注意，将项目向下移动到较低频率的桶是可选的 - 您可以设置一些截止点。
创建新存储桶时，更新与所有存储桶关联的检索范围，为新集合提供您想要的频率分布特征。
通用分桶加权队列的 C# 实现（第一次切割）：
using System;
using System.Collections.Generic;
using System.Linq;
namespace Utility
{
public class BucketWeightedQueue<T>
{
private int m_MaxFallOff;
private readonly double m_FallOffRate;
private readonly List<List<T>> m_Buckets;
private readonly List<int> m_FallOffFactors;
private readonly Random m_Rand = new Random();
public BucketWeightedQueue(IEnumerable<T> items, double fallOffRate )
{
if( fallOffRate < 0 )
throw new ArgumentOutOfRangeException("fallOffRate");
m_MaxFallOff = 1;
m_FallOffRate = fallOffRate;
m_Buckets = new List<List<T>> { items.ToList() };
m_FallOffFactors = new List<int> { m_MaxFallOff };
}
public T GetRandomItem()
{
var bucketIndex = GetRandomBucketIndex();
var bucket = m_Buckets[bucketIndex];
var itemIndex = m_Rand.Next( bucket.Count );
var selectedItem = bucket[itemIndex];
ReduceItemProbability( bucketIndex, itemIndex );
return selectedItem;
}
private int GetRandomBucketIndex()
{
var randFallOffValue = m_Rand.Next( m_MaxFallOff );
for (int i = 0; i < m_FallOffFactors.Count; i++ )
if( m_FallOffFactors[i] <= randFallOffValue )
return i;
return m_FallOffFactors[0];
}
private void ReduceItemProbability( int bucketIndex, int itemIndex )
{
if( m_FallOffRate <= 0 )
return; // do nothing if there is no fall off rate...
var item = m_Buckets[bucketIndex][itemIndex];
m_Buckets[bucketIndex].RemoveAt( itemIndex );
if( bucketIndex <= m_Buckets.Count )
{
// create a new bucket...
m_Buckets.Add( new List<T>() );
m_MaxFallOff = (int)(m_FallOffFactors[bucketIndex] / m_FallOffRate);
m_FallOffFactors.Add( m_MaxFallOff );
}
var nextBucket = m_Buckets[bucketIndex + 1];
nextBucket.Add( item );
if (m_Buckets[bucketIndex].Count == 0) // drop empty buckets
m_Buckets.RemoveAt( bucketIndex );
}
}
}
于 2009-10-19T15:29:05.060 回答
8
在这里，我们将设计一个随机数生成器，它的分布倾向于低值。您可以使用它来选择列表开头的项目。要降低某项被选中的几率，请将该项向下移动到列表中。您有几个选项可用于将项目向下移动到列表中。让我们先回顾一下随机变量变换。
通过将以下函数应用于 0 和 1 之间的均匀随机变量：
index = Int(l*(1-r^(0.5)) # l=length, r=uniform random var between 0 and 1
你得到一个很酷的分布，大大降低了更大索引的几率
p(0)=0.09751
p(1)=0.09246
p(2)=0.08769
p(3)=0.08211
p(4)=0.07636
p(5)=0.07325
p(6)=0.06772
p(7)=0.06309
p(8)=0.05813
p(9)=0.05274
p(10)=0.04808
p(11)=0.04205
p(12)=0.03691
p(13)=0.03268
p(14)=0.02708
p(15)=0.02292
p(16)=0.01727
p(17)=0.01211
p(18)=0.00736
p(19)=0.00249
这是大小为 2 的列表的分布
0.75139
0.24862
尺寸 3
0.55699
0.33306
0.10996
尺寸 4
0.43916
0.31018
0.18836
0.06231
现在让我们讨论将项目向下移动的两个选项。我测试了两个：
ToEnd - 将最近选择的项目移动到列表末尾
排序 - 保留每个项目被选择次数的关联数组，并将列表从最少选择到最多排序。
我创建了一个模拟以从列表中选择并检查每个项目被选中的计数的标准偏差。标准差越低越好。例如，对包含 10 个项目的列表进行 1 次模拟，其中 50 个选择创建了价差：
{"a"=>5, "b"=>5, "c"=>6, "d"=>5, "e"=>4, "f"=>4, "g"=>5, "h"=>5, "i"=>6, "j"=>5}
该模拟的标准差是
0.63
借助运行模拟的能力，我通过运行模拟 500 次并提供每种方法的平均标准偏差来计算一些元统计数据：ToEnd 和 Sort。我预计对于低 # 选择的标准偏差会很高，但实际上对于 ToEnd 算法，标准偏差随着选择数量的增加而增加。排序方法解决了这个问题。
Testing ["a", "b", "c", "d", "e"]
-------------------------
Picks ToEnd (StdDev) Sort (StdDev)
5 0.59 0.57
10 0.76 0.68
15 0.93 0.74
20 1.04 0.74
25 1.20 0.73
30 1.28 0.73
35 1.34 0.74
40 1.50 0.75
45 1.53 0.75
45 1.56 0.77
80 2.04 0.79
125 2.52 0.74
180 3.11 0.77
245 3.53 0.79
320 4.05 0.75
405 4.52 0.76
500 5.00 0.78
以下是更大集合的一些测试结果。
Testing ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]
-------------------------
Picks ToEnd (StdDev) Sort (StdDev)
10 0.68 0.65
20 0.87 0.77
30 1.04 0.80
40 1.18 0.82
50 1.30 0.85
60 1.43 0.84
70 1.57 0.87
80 1.65 0.88
90 1.73 0.87
90 1.71 0.87
160 2.30 0.89
250 2.83 0.88
360 3.44 0.88
490 3.89 0.88
640 4.54 0.87
810 5.12 0.88
1000 5.66 0.85
有了一个好的测试框架，我忍不住尝试不同的随机数转换。我的假设是，如果我采用立方根而不是 x 的平方根，我的标准偏差会减小。事实上确实如此，但我担心这会降低随机性。当公式更改为时，您可以在此处观察一些模拟
index = Int(l*(1-r^(0.33)) # l=length, r=uniform random var between 0 and 1
现在检查实际的选择。正如我所想的，起初它非常重要。如果您想对此进行大量加权，您可能应该在开始之前随机化您的列表。
StdDev = 0.632455532033676
{"a"=>10, "b"=>10, "c"=>11, "d"=>9, "e"=>10}
a d e c b c e b a d b e c a d d e b a e e c c b d a d c b c e b a a d d b e a e a b c b d c a c e c
StdDev = 0.0
{"a"=>10, "b"=>10, "c"=>10, "d"=>10, "e"=>10}
b c d a a d b c b a d e c d e c b e b a e e d c c a b a d a e e b d b a e c c e b a c c d d d a b e
StdDev = 0.632455532033676
{"a"=>9, "b"=>10, "c"=>10, "d"=>10, "e"=>11}
b d a e b c a d c e e b a c a d d c b c e d a e b b a c d c d a e a e e b d c b e a b c b c d d e e
StdDev = 0.0
{"a"=>10, "b"=>10, "c"=>10, "d"=>10, "e"=>10}
a b e d c e a b d c b c c a d b e e b e a d d c e a d b b c c a a a b e d d e c c a b b e a c d e d
StdDev = 0.632455532033676
{"a"=>11, "b"=>10, "c"=>9, "d"=>10, "e"=>10}
b a d c d c a e b e a e b c d b c a a d e e d c d e c b a b b e d c d b c e a a a d b c e b e a d a
于 2009-10-20T18:37:55.083 回答
2
这完全取决于当一个给定的项目被选中时，被选中的概率应该如何变化。
实现此目的的一种简单方法是使用双绘图，您可以从输入列表（从不更改）和一个空列表开始，您可以将随机选择的项目添加到该列表中。每次正常绘制后，（从第一个列表中），您从第二个列表中绘制一个项目。如果再次出现相同的项目（或者更确切地说是项目值），则不会被选中（即无效抽奖，重新开始），否则抽奖计数并将相应的值添加到第二个列表中。
一般概念似乎与遍历来源有关。
DigitalJoe评论了这种方法的一个明显缺点。简而言之，Joe 指出，防止重复（不一定是连续重复，只是“重复”）先前绘制的项目值（在算法的第二个列表中找到的值）的概率在前几百张图中波动很大. 另一个隐含的评论是，在第二个列表包含几十个值之后，防止此类重复的概率极低。这些都是有效的点，并且需要资格。
这个推理符合我们对第二个列表工作方式的直观理解：那里的项目值越多，我们必须“双抽”的机会就越少，因此可以防止重复。这是真的，但它只关注第二个列表。需要考虑[从第一个列表] 之前看到的项目的概率。我们可以用两个例子来直观地理解这个想法，但这当然是一个梯度：
- 案例“A”：与绘制其他东西的概率相比，绘制给定项目值的概率相对较低。因此，在前几张图纸中多次绘制该物品的组合概率很低，并且由于列表二中的图纸而这样做然后丢弃它的概率甚至更低（即使后者的概率可能是高，由于第二个列表中的项目数量很少）。
- 案例“B”：抽取给定项目的概率相对于抽取其他项目的概率高。在这种情况下，在前几次抽签中重复的概率很高，并且由于防止实际重复（第二次抽签）的概率也很高（第二次抽签的确定性，50% 的机会在第二次抽奖时……在第 11 次抽奖时有 10% 的机会），“惩罚”一个高概率项目的总体概率很高。然而，这不是问题，因为从第一个列表中抽取项目的相对概率将确保在统计上，将有许多其他机会产生不会随着绘图数量的增加而被“强制”抑制的重复项.
在这两种情况下，重要的是实际图纸的整体分布与输入列表中的分布相匹配。随着图纸数量在统计上变得更加重要，这一点尤其正确。
关于重复过滤器可能太弱的问题，随着第二个列表越来越多地反映第一个列表的分布，这也变得不那么相关了。也许了解这一切的一种方法是考虑实现 OP 问题中描述的目标的替代方法。
替代算法：算法
1：从第一个列表中不替换地绘制。我们将使用原始列表的副本开始，每次绘制给定项目时，我们都会将其从该列表中删除，因此总体上不太可能再次出现相同的值。当我们绘制所有项目时，我们已经准确地复制了原始列表的分布。
算法 2：从原始列表已被复制给定次数的列表中无替换地绘制。这与上述类似，但引入了更多的随机性，即需要更多数量的图纸才能使图纸分布方法与原始列表匹配。
在某种程度上，我最初建议的两个列表算法（从原始列表中替换并管理第二个列表以有时防止重复）类似于算法 2，这些算法使绘图分布收敛于原始列表的分布。然而，原始算法的优点是它使列表的管理更容易（尽管公平地说，这样做的一个简单方法是用排序的“空”值替换绘制的项目，然后重新绘制然后点击这样的“空单元格”，实际上是相同的事情，相反，当第二个列表中的绘图产生相同的项目值时重绘..）
于 2009-10-19T15:30:32.343 回答
1
您可以做一些事情，例如制作一个自定义类（为您的列表），它存储项目加上权重。
添加项目时默认权重为 1，并存储（在“列表”中）所有项目的所有权重的总和。
然后，当您随机选择一个项目时，您可以在 0 -> 列表中所有项目的总权重之间选择一个数字，然后遍历列表以找到该“位置”的项目（通过加权）。减少该项目的权重（这可能是一些衰减，即：将其权重乘以 0.8 或 0.5 - 您可以很好地控制选择下降的概率有多快），然后返回它。
如果你有很多项目，这里的缺点是你的选择是 O(n) （因为你必须遍历列表）。因此，我可能会使用链表进行存储（无论如何您都必须步行进行检索，因此这可以让您更快地插入/删除）。
但是，如果您没有存储大量选项，这将很容易实现，并且可以让您在选择时对概率进行大量控制并降低概率。
于 2009-10-19T15:25:24.880 回答
0
使用自插入或上次选择项目以来的经过时间作为优先级修饰符...设置每个项目的优先级 = 自插入或上次选择以来的时间量，然后通过乘以此优先级来调整被选择的机会。
一旦你有所有项目的机会，将它们标准化，（将它们全部调整为相同的计算比率，使它们全部加起来为 1.000），然后使用这些值作为它们被选中的概率。
于 2009-10-19T15:26:47.407 回答
0
从列表中选择加权随机元素的一般策略是：给每个项目一个权重。标准化，使总权重为 1。（首先，每个项目的权重为 1/n）。按重量对列表进行排序。现在选择一个介于 0 和 1 之间的随机数，然后在列表中累积总数，直到您越过您的数字。例如，如果您的权重是 [0.4, 0.3, 0.2, 0.1] 并且您的随机数是 0.63215，那么您的前两个步骤总计 = 0.4，总计 = 0.7，然后注意到 0.7 大于 0.63215，因此您返回第二个元素。
一旦你选择了一个元素，你就向下调整它的权重（你需要尝试降低权重的公式，直到找到适合你的公式，最简单的就是每次将它乘以某个常数分数），然后重新归一化并重复.
请注意，如果您有很多元素，这是相当低效的，因为它在列表的长度中是 O(n)，但在实践中这并不重要，除非您在需要大量的内部循环中执行此操作优化或类似。如果事实证明这是一个问题，您可以查看几何数据结构（如范围树）来优化查找。
于 2009-10-19T15:38:25.853 回答