调整从列表中选择项目的机会
https://stackoverflow.com/questions/1589321
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我有一份物品清单。当我创建列表时，每个项目都有同等的机会被选择。但当一个项目被选择时，它的机会就会下降，而其他项目的机会就会上升。如果在此过程中添加了新项目，则该项目被选择的机会应该最高，但随着被选择的机会会下降。我正在寻找一个可以完成此任务的好算法，即 C#。
概括的想法：我有 5 个项目，随着时间的推移，所有 5 个项目将有 20% 的时间被选择。我试图将选择率尽可能保持在 20% 左右，减少异常值。如果存在，它将被更多/更少地选择以使其恢复一致。
解决方案
在这里，我们将设计一个随机数生成器，其分布有利于低值。您可以使用它来优先选择列表开头的项目。要减少选择某项的可能性，请将该项目向下移动到列表中。您可以通过多种方式选择如何将项目移至列表下方。让我们首先回顾一下随机变量变换。
将以下函数应用于 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
现在让我们讨论将项目向下移动列表的两个选项。我测试了两个：
结束 - 将最近选择的项目移动到列表末尾
种类 - 保留每个项目被选择的次数的关联数组，并按从最少到最多选择的顺序对列表进行排序。
我创建了一个模拟来从列表中进行选择并检查每个项目被选择的计数的标准偏差。标准差越低越好。例如，对包含 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 算法，标准偏差随着选择数量的增加而增加。排序方法解决了这个问题。
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
其他提示
使用铲斗加权队列：而不是使用一个列表的，划分您的收集到存储桶 - 每个桶具有检索相关联的频率。项目从较高频率移动水桶以降低频率的人，因为它们都被选中。
要实现这个的一个简单方法是将每个桶分配一个值的范围，并产生一个随机数组合的范围内选择一个桶选择。你可能会想摘要收集到某种类的，让你不暴露消费者的细节。
<强>算法：
最初，所有的项目在同一（顶级）桶启动。
当你选择一个项目，从它在水桶，走向下一个更低的桶。如果必要，创建一个新的水平桶。
当添加新的项目，将其添加到最顶部（最频繁使用的）桶。
要随机地选择一个项目，首先选择一个桶，然后挑选铲斗内的项目。将所选的项目分解成一个新的水平桶。注意，该移动的项目向下到较低的频率桶是可选的 - 你可以设置一些截止点
当创建一个新的桶，更新与所有桶相关联的检索范围，得到新的一组所需的频率分布特性。
<强> 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 );
}
}
}
这完全取决于选择给定项目时被选择的概率如何变化。
实现此目的的一个简单方法是使用双绘图，即从输入列表（永远不会改变）和一个空列表开始，您可以在其中添加随机选择的项目。每次正常绘制后（从第一个列表），您从第二个列表中绘制一个项目。如果相同的项目（或者更确切地说是项目值）再次出现，则不会选择它（即）无效抽奖，重新开始），否则抽奖计数并将相应的值添加到第二个列表中。
一般概念似乎与遍历源有关。
数码乔 评论了这种方法的一个明显缺点。简而言之，乔指出，防止先前绘制的项目值（在算法的第二个列表中找到的值）重复（不一定是连续重复，只是“重复”）的概率在前几百个绘图中波动很大。另一个隐含的评论是，在第二个列表包含几十个值之后，防止这种重复的概率极低。这些都是有效的观点，并且需要资格。
这个推理符合我们对第二个列表工作方式的直观理解：里面的物品值越多，我们“双重抽奖”的机会就越少，从而防止重复。这是事实，但它只关注第二个列表。需要考虑[从第一个列表]提取先前看到的项目的概率。我们可以用两个例子来直观地理解这个想法，但这当然是一个梯度：
- 情况“A”：与抽取其他物品的概率相比，抽取给定项目值的概率相对较低。因此，在前几次抽奖期间多次抽奖此项目的组合概率很低，并且这样做然后由于列表二中的抽奖而丢弃它的概率甚至更低（即使后一个概率可能是高，因为第二个列表中的项目数量较少）。
- 情况“B”：绘制给定项目的概率相对于绘制其他项目的概率较高。在这种情况下，在前几次抽奖中出现重复的概率很高，并且由于防止实际重复（第二个列表中的抽奖）的概率也很高（第二次抽奖的确定性，50％的机会）在第二张图上...第 11 张图的概率为 10%），“惩罚”高概率物品的总体概率很高。然而，这不是问题，因为从第一个列表中绘制项目的相对概率将确保从统计上看，有许多其他机会产生重复项，而这些重复项不会随着绘图数量的增加而被“强制”抑制。
在这两种情况下，重要的是实际绘图的总体分布与输入列表中的分布相匹配。当图纸数量变得更多时尤其如此 具有统计显着性.
关于重复过滤器可能太弱的问题，这也变得不太相关，因为第二个列表越来越多地反映第一个列表的分布。也许感受这一切的一种方法是考虑实现OP问题中描述的目标的替代方法。
替代算法:
算法1： 绘图无需更换 从第一个列表中。我们将使用原始列表的副本来开始，并且每次绘制给定项目时，我们都会将其从该列表中删除，因此总体上不太可能再次出现相同的值。当我们绘制所有项目时，我们已经准确地再现了原始列表的分布。
算法2：绘图无需更换, ，从列表中 原始列表已被复制给定次数. 。这与上面类似，但引入了更多的随机性，即通过要求更多的图纸来使图纸分布接近并与原始列表相匹配。
在某种程度上，我最初建议的双列表算法（从原始列表中进行替换绘制并管理第二个列表以有时防止重复）类似于 Algo 2，这些算法使绘图分布向原始列表的分布收敛。然而，原始算法的优点是它使列表的管理更容易（尽管公平地说，这样做的一个简单方法是将绘制的项目替换为“空”值，然后重新绘制，然后点击这样的“空单元格”，这实际上是相同的事情，相反，当第二个列表中的绘图产生相同的项目值时重新绘制..）
您可以做一些事情，如使自定义类（列表），其存储的项目加上权重。
默认的加权为1时加一个项目，并存储（在“列表”）的总所有所有项目的权重的。
您可以的话，当你随机选择一个项目，随便挑一个数字0之间 - >列表中的所有项目的总权重，并遍历这个列表找到那个“位置”的项目（通过加权） 。递减该项目的权重（这可能是一些衰减，即：乘它是由0.8或0.5加权 - 你必须在它的概率选择的速度有多快脱落了很多控制），并返回
这里的缺点是，如果你有很多的项目，那是你的选择是O（n）（因为你必须在列表中行走）。正因为如此，我可能会使用一个链表存储（你将不得不反正步行检索，所以这让你更快的插入/删除）。
如果你不存储选项的数量庞大，不过，这将是很容易实现，并给你的选择很多时间在概率加上概率熄火控制。
使用，因为该项目被插入或最后选定为优先mofifier所经过的时间...设置每个项目的优先级=要通过乘以选择，因为它已经被插入或最后选择的，然后对其进行调整的机会，时间量这一重点。
一旦有了所有项目的机会，他们正常化，（adjsut它们全部由相同的计算出的比率，以让他们都加起来1.000），然后使用这些值作为其被选择的概率。
用于拾取从一个列表中的加权随机元件的一般策略是这样的：给每个项目的权重。归一化，使得总重量为1（因此，开始时，每一个项具有重量的1 / n）。排序权重列表。现在挑0和1之间的随机数，直到你过你的电话号码下井名单累积总数。例如如果你的权重是[0.4，0.3，0.2，0.1]和您的随机数为0.63215，你的前两个步骤共有= 0.4，总= 0.7，然后通知，0.7比0.63215更大所以返回第二元件。
一旦你选择一个元素，调整其加权向下（你需要用的公式降低权重进行实验，直到你找到一个适合你的作品，最简单的就是通过一些固定比例每次乘它），然后renormalise并重复。
请注意，这是非常低效的，如果你有一个的很多的元素，因为它是O（n）的列表的长度，但它不应该的问题在实践中，除非你正在做的这在一个内部循环需要被高度优化，或类似的。如果结果是一个问题，你可以看到像范围树的几何数据结构，以优化查找。
