考虑以下代表经纪人的类：

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。

我们如何看待下面的代码？

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\t\t" + result["A"]);
                Console.WriteLine("B\t\t" + result["B"]);
                Console.WriteLine("C\t\t" + result["C"]);
                Console.WriteLine("D\t\t" + result["D"]);

                result.Clear();
                Console.WriteLine();
                Console.ReadLine();
            }
        }
    }

我不太自信当我运行此代码时，经纪人A总是比经纪人D获得更多的匹配，而且它们的权重相同。

有没有更准确的算法？

谢谢！

解决方案

回答

算法几乎是正确的。但是，测试应该是<而不是<=：

if (randomNumber < broker.Weight)

这是因为随机数中包含0，而" totalWeight"中包含独占。换句话说，权重为0的经纪人仍然很少有机会被选中-根本不是我们想要的。这说明经纪人A的点击率高于经纪人D。

除此之外，算法很好，而且实际上是解决此问题的规范方法。

回答

选择超过存储器使用代理时的另一种方法的主张加快。基本上，我们创建的列表包含与指定权重相同数量的对代理实例的引用。

List<Broker> brokers = new List<Broker>();
for (int i=0; i<10; i++)
    brokers.Add(new Broker("A", 10));
for (int i=0; i<20; i++)
    brokers.Add(new Broker("B", 20));
for (int i=0; i<20; i++)
    brokers.Add(new Broker("C", 20));
for (int i=0; i<10; i++)
    brokers.Add(new Broker("D", 10));

然后，要选择一个随机加权的实例是O(1)操作：

int randomNumber = _rnd.Next(0, brokers.length);
selectedBroker = brokers[randomNumber];

回答

如果要提高速度，可以考虑使用加权储层采样，而不必提前找到总权重(但可以从随机数生成器中采样更多)。该代码可能看起来像

Broker selected = null;
int s = 0;
foreach(Broker broker in brokers) {
    s += broker.Weight;
    if (broker.Weight <= _rnd.Next(0,s)) {
        selected = broker;
    }
}

这需要经过列表经纪人一次。但是，如果经纪人列表是固定的或者没有变化，那么我们通常可以保留一系列累加和，即A [i]是所有经纪人的权重之和0，..，i-1. 然后，A [n]是总权重，如果我们选择一个介于1和A [n-1]之间的数字，则说x，我们会找到经纪人js.t。 A [j-1] <= x <A [j]。为方便起见，让A [0] =0。我们可以使用二进制搜索在log(n)步骤中找到该代理编号j，我将把代码保留为简单的练习。如果数据经常变化，那么这可能不是一个好方法，因为每次权重发生变化时，我们可能都需要更新阵列的很大一部分。

回答

class Program
{
    static void Main(string[] args)
    {
        var books = new List<Book> {
        new Book{Isbn=1,Name="A",Weight=1},
        new Book{Isbn=2,Name="B",Weight=100},
        new Book{Isbn=3,Name="C",Weight=1000},
        new Book{Isbn=4,Name="D",Weight=10000},
        new Book{Isbn=5,Name="E",Weight=100000}};

        Book randomlySelectedBook = WeightedRandomization.Choose(books);
    }
}

public static class WeightedRandomization
{
    public static T Choose<T>(List<T> list) where T : IWeighted
    {
        if (list.Count == 0)
        {
            return default(T);
        }

        int totalweight = list.Sum(c => c.Weight);
        Random rand = new Random();
        int choice = rand.Next(totalweight);
        int sum = 0;

        foreach (var obj in list)
        {
            for (int i = sum; i < obj.Weight + sum; i++)
            {
                if (i >= choice)
                {
                    return obj;
                }
            }
            sum += obj.Weight;
        }

        return list.First();
    }
}

public interface IWeighted
{
    int Weight { get; set; }
}

public class Book : IWeighted
{
    public int Isbn { get; set; }
    public string Name { get; set; }
    public int Weight { get; set; }
}