为了账号安全,请及时绑定邮箱和手机立即绑定

随机加权选择

/ 猿问

随机加权选择

MMMHUHU 2019-12-21 13:06:38

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


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;

                        }



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


有没有更准确的算法?


查看完整描述

4 回答

?
桃花长相依

您的算法几乎是正确的。但是,测试应<改为<=:


if (randomNumber < broker.Weight)

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


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


查看完整回答
反对 回复 2019-12-21
?
aluckdog

可以用于任何数据类型的通用性怎么样?


using System;

using System.Linq;

using System.Collections;

using System.Collections.Generic;


public static class IEnumerableExtensions {


    public static T RandomElementByWeight<T>(this IEnumerable<T> sequence, Func<T, float> weightSelector) {

        float totalWeight = sequence.Sum(weightSelector);

        // The weight we are after...

        float itemWeightIndex =  new Random().NextDouble() * totalWeight;

        float currentWeightIndex = 0;


        foreach(var item in from weightedItem in sequence select new { Value = weightedItem, Weight = weightSelector(weightedItem) }) {

            currentWeightIndex += item.Weight;


            // If we've hit or passed the weight we are after for this item then it's the one we want....

            if(currentWeightIndex >= itemWeightIndex)

                return item.Value;


        }


        return default(T);


    }


}

只需致电


    Dictionary<string, float> foo = new Dictionary<string, float>();

    foo.Add("Item 25% 1", 0.5f);

    foo.Add("Item 25% 2", 0.5f);

    foo.Add("Item 50%", 1f);


    for(int i = 0; i < 10; i++)

        Console.WriteLine(this, "Item Chosen {0}", foo.RandomElementByWeight(e => e.Value));


查看完整回答
反对 回复 2019-12-21
?
慕姐4208626

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; }

}


查看完整回答
反对 回复 2019-12-21
?
慕斯709654

由于这是Google的最佳结果:


我为随机选择的加权项目创建了一个C#库。


它同时实现了树选择和Walker别名方法算法,以在所有用例中提供最佳性能。

它已经过单元测试和优化。

它具有LINQ支持。

它是免费的开放源代码,并根据MIT许可进行了许可。

一些示例代码:


IWeightedRandomizer<string> randomizer = new DynamicWeightedRandomizer<string>();

randomizer["Joe"] = 1;

randomizer["Ryan"] = 2;

randomizer["Jason"] = 2;


string name1 = randomizer.RandomWithReplacement();

//name1 has a 20% chance of being "Joe", 40% of "Ryan", 40% of "Jason"


string name2 = randomizer.RandomWithRemoval();

//Same as above, except whichever one was chosen has been removed from the list.


查看完整回答
反对 回复 2019-12-21

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信