随机加权选择 [英] Random weighted choice
问题描述
考虑下面代表 Broker 的类:
Consider the class below that represents a Broker:
public class Broker
{
public string Name = string.Empty;
public int Weight = 0;
public Broker(string n, int w)
{
this.Name = n;
this.Weight = w;
}
}
我想从数组中随机选择一个 Broker,同时考虑到它们的权重.
I'd like to randomly select a Broker from an array, taking into account their weights.
你觉得下面的代码怎么样?
What do you think of the code below?
class Program
{
private static Random _rnd = new Random();
public static Broker GetBroker(List<Broker> brokers, int totalWeight)
{
// totalWeight is the sum of all brokers' weight
int randomNumber = _rnd.Next(0, totalWeight);
Broker selectedBroker = null;
foreach (Broker broker in brokers)
{
if (randomNumber <= broker.Weight)
{
selectedBroker = broker;
break;
}
randomNumber = randomNumber - broker.Weight;
}
return selectedBroker;
}
static void Main(string[] args)
{
List<Broker> brokers = new List<Broker>();
brokers.Add(new Broker("A", 10));
brokers.Add(new Broker("B", 20));
brokers.Add(new Broker("C", 20));
brokers.Add(new Broker("D", 10));
// total the weigth
int totalWeight = 0;
foreach (Broker broker in brokers)
{
totalWeight += broker.Weight;
}
while (true)
{
Dictionary<string, int> result = new Dictionary<string, int>();
Broker selectedBroker = null;
for (int i = 0; i < 1000; i++)
{
selectedBroker = GetBroker(brokers, totalWeight);
if (selectedBroker != null)
{
if (result.ContainsKey(selectedBroker.Name))
{
result[selectedBroker.Name] = result[selectedBroker.Name] + 1;
}
else
{
result.Add(selectedBroker.Name, 1);
}
}
}
Console.WriteLine("A " + result["A"]);
Console.WriteLine("B " + result["B"]);
Console.WriteLine("C " + result["C"]);
Console.WriteLine("D " + result["D"]);
result.Clear();
Console.WriteLine();
Console.ReadLine();
}
}
}
我没那么自信.当我运行这个时,Broker A 总是比 Broker D 获得更多的点击,并且它们具有相同的权重.
I'm not so confident. When I run this, Broker A always gets more hits than Broker D, and they have the same weight.
有更准确的算法吗?
谢谢!
推荐答案
你的算法几乎是正确的.但是,测试应该是 <
而不是 <=
:
Your algorithm is nearly correct. However, the test should be <
instead of <=
:
if (randomNumber < broker.Weight)
这是因为 0 包含在随机数中,而 totalWeight
是不包含的.换句话说,权重为 0 的经纪人仍然有很小的机会被选中——根本不是你想要的.这说明经纪商 A 的点击量比经纪商 D 多.
This is because 0 is inclusive in the random number while totalWeight
is exclusive. In other words, a broker with weight 0 would still have a small chance of being selected – not at all what you want. This accounts for broker A having more hits than broker D.
除此之外,您的算法很好,实际上是解决此问题的规范方法.
Other than that, your algorithm is fine and in fact the canonical way of solving this problem.
这篇关于随机加权选择的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!