Tha*_*had 10 c# math probability weighted-average
我有一个项目清单.当我创建列表时,每个项目都有相同的机会被选中.但是当一个项目被选中时,它的机会会下降,而其他机会会上升.如果在此过程中添加了一个新项目,那么它应该被选中的机会最大,并且在选中它时机会会下降.我正在寻找一个可以实现这个C#的好算法.
Generalizaed想法:我有5个项目,随着时间的推移,所有5个项目将被选中20%的时间.我试图让选择尽可能接近20%,减少对外界的影响.如果存在,将更多/更少地选择它以使其恢复正常.
使用存储桶加权队列:不使用列表,而是将集合划分为存储桶 - 每个存储桶都具有相关的检索频率.在选择项目时,项目从较高频率的桶移动到较低频率的桶.
实现此目的的一种简单方法是为每个存储桶分配一系列值,并在组合范围内生成随机数以选择要选择的存储桶.您可能希望将此集合抽象为某种类,以便您不会将消费者暴露给细节.
算法:
最初,所有项目都在同一个(顶级)存储桶中启动.
当您选择一个项目时,将其从其所在的桶中移动到下一个较低的桶中.如有必要,请创建下一级存储桶.
添加新项目后,将其添加到最顶层(最常用)的存储桶中.
要随机选择项目,首先选择一个桶,然后选择桶中的项目.将所选项目向下移动到下一级别存储桶中.请注意,将项目向下移动到较低频率的存储桶是可选的 - 您可以设置一些截止点.
创建新存储桶时,更新与所有存储桶关联的检索范围,以便为新设置提供所需的频率分布特性.
通用分块加权队列的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 );
}
}
}
在这里,我们将设计一个随机数生成器,其分布有利于低值.您可以使用它来选择列表开头的项目.要降低选择内容的几率,请将该项目向下移动到列表中.您可以通过几个选项将项目向下移动到列表中.让我们先回顾一下随机变量转换.
通过将以下函数应用于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 - 将最近选择的项目移动到列表末尾
排序 - 保留每个项目被选中次数的关联数组,并将列表从最少选择到最多选择.
我创建了一个模拟以从列表中选择并检查每个项目被选中的计数的标准偏差.标准差越低越好.例如,1个模拟10个项目的列表,其中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