https://stackoverflow.com/questions/56692
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
考虑级以下代表一个经纪人：
public class Broker
{
public string Name = string.Empty;
public int Weight = 0;
public Broker(string n, int w)
{
this.Name = n;
this.Weight = w;
}
}
我想随机选择一个经纪人从一个数组，考虑到他们的权重。
你认为是什么代码下面？
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();
}
}
}
我不那么有信心。当我运行此，经纪人有始终得到更多的命于经纪D、和他们拥有相同的权重。
是否有一个更精确算法？
谢谢！
解决方案
你的算法几乎是正确的。然而，测试应该是 < 而不是的 <=:
if (randomNumber < broker.Weight)
这是因为0包括在随机数量的话， totalWeight 是独特的。换句话说，一个经纪人与重0仍然会有一个小的被选择的机会的–不你想要什么。这一账户的经纪人一个具有更多的点击率比D.经纪人
其他比，你的算法是好的和事实上的规范的方式解决这个问题。
其他提示
怎么样东西一点更为通用，即，可用于任何数据的类型？
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));
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; }
}
一种替代方法主张速度当选择的经纪人在内存使用情况。基本上，我们创建的列表中包含相同数量的文献给一个经纪人实例作为指定的重量。
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];
由于这是顶级的结果在谷歌:
我已经创建了 C#库，用于随机选定的加权的项目.
- 它实现了这两个树选择和walker别名方法的算法，得到更好的性能，为所有使用情况。
- 这是单元的测试和最优化。
- 它有皇宫的支持。
- 它是自由和开放源，根据授权麻省理工学院许可证。
一些实例编码：
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.
如果你想更快的速度你可以考虑加权贮器取样，你没有找到总重量的时间提前(但你的样本往往从随机数发生器)。代码看起来可能会喜欢的东西
Broker selected = null;
int s = 0;
foreach(Broker broker in brokers) {
s += broker.Weight;
if (broker.Weight <= _rnd.Next(0,s)) {
selected = broker;
}
}
这需要会一旦通过该列表中的经纪人。然而，如果名单的经纪人是固定的还是不会改变，往往可以保持一系列的累计款项，即一个[i]的总和，加权的所有经纪人0,..,i-1。然后一个[n]的总量如果你选择一个数1之间的一个[n-1]，说x你找经纪人j s.t.一个[j-1] <=x < 一个[j].为了方便您让[0]=0.你可以找到了这个经纪人数j在日志(n)的步骤使用的二进制的搜索，我会离开的代码作为一个容易的运动。如果你的数据经常变化，这可能不是一个良好的路要走，因为每次一些重量的变化可能需要更新大部分数。
我已经想出了一个通用的版本的这个解决方案：
public static class WeightedEx
{
/// <summary>
/// Select an item from the given sequence according to their respective weights.
/// </summary>
/// <typeparam name="TItem">Type of item item in the given sequence.</typeparam>
/// <param name="a_source">Given sequence of weighted items.</param>
/// <returns>Randomly picked item.</returns>
public static TItem PickWeighted<TItem>(this IEnumerable<TItem> a_source)
where TItem : IWeighted
{
if (!a_source.Any())
return default(TItem);
var source= a_source.OrderBy(i => i.Weight);
double dTotalWeight = source.Sum(i => i.Weight);
Random rand = new Random();
while (true)
{
double dRandom = rand.NextDouble() * dTotalWeight;
foreach (var item in source)
{
if (dRandom < item.Weight)
return item;
dRandom -= item.Weight;
}
}
}
}
/// <summary>
/// IWeighted: Implementation of an item that is weighted.
/// </summary>
public interface IWeighted
{
double Weight { get; }
}
只是分享我自己的执行。希望你会发现它很有用。
// Author: Giovanni Costagliola <giovanni.costagliola@gmail.com>
using System;
using System.Collections.Generic;
using System.Linq;
namespace Utils
{
/// <summary>
/// Represent a Weighted Item.
/// </summary>
public interface IWeighted
{
/// <summary>
/// A positive weight. It's up to the implementer ensure this requirement
/// </summary>
int Weight { get; }
}
/// <summary>
/// Pick up an element reflecting its weight.
/// </summary>
/// <typeparam name="T"></typeparam>
public class RandomWeightedPicker<T> where T:IWeighted
{
private readonly IEnumerable<T> items;
private readonly int totalWeight;
private Random random = new Random();
/// <summary>
/// Initiliaze the structure. O(1) or O(n) depending by the options, default O(n).
/// </summary>
/// <param name="items">The items</param>
/// <param name="checkWeights">If <c>true</c> will check that the weights are positive. O(N)</param>
/// <param name="shallowCopy">If <c>true</c> will copy the original collection structure (not the items). Keep in mind that items lifecycle is impacted.</param>
public RandomWeightedPicker(IEnumerable<T> items, bool checkWeights = true, bool shallowCopy = true)
{
if (items == null) throw new ArgumentNullException("items");
if (!items.Any()) throw new ArgumentException("items cannot be empty");
if (shallowCopy)
this.items = new List<T>(items);
else
this.items = items;
if (checkWeights && this.items.Any(i => i.Weight <= 0))
{
throw new ArgumentException("There exists some items with a non positive weight");
}
totalWeight = this.items.Sum(i => i.Weight);
}
/// <summary>
/// Pick a random item based on its chance. O(n)
/// </summary>
/// <param name="defaultValue">The value returned in case the element has not been found</param>
/// <returns></returns>
public T PickAnItem()
{
int rnd = random.Next(totalWeight);
return items.First(i => (rnd -= i.Weight) < 0);
}
/// <summary>
/// Resets the internal random generator. O(1)
/// </summary>
/// <param name="seed"></param>
public void ResetRandomGenerator(int? seed)
{
random = seed.HasValue ? new Random(seed.Value) : new Random();
}
}
}
要点: https://gist.github.com/MrBogomips/ae6f6c9af8032392e4b93aaa393df447
执行在原来的问题似乎有点奇怪我
总重量的列表的是60使随机数是0至59.它始终检查的随机数反对的重量然后递减。在我看来，它会赞成的东西的列表中根据它们的顺序。
这是一个通用的执行我使用的关键是在随意性：
using System;
using System.Collections.Generic;
using System.Linq;
public class WeightedList<T>
{
private readonly Dictionary<T,int> _items = new Dictionary<T,int>();
// Doesn't allow items with zero weight; to remove an item, set its weight to zero
public void SetWeight(T item, int weight)
{
if (_items.ContainsKey(item))
{
if (weight != _items[item])
{
if (weight > 0)
{
_items[item] = weight;
}
else
{
_items.Remove(item);
}
_totalWeight = null; // Will recalculate the total weight later
}
}
else if (weight > 0)
{
_items.Add(item, weight);
_totalWeight = null; // Will recalculate the total weight later
}
}
public int GetWeight(T item)
{
return _items.ContainsKey(item) ? _items[item] : 0;
}
private int? _totalWeight;
public int totalWeight
{
get
{
if (!_totalWeight.HasValue) _totalWeight = _items.Sum(x => x.Value);
return _totalWeight.Value;
}
}
public T Random
{
get
{
var temp = 0;
var random = new Random().Next(totalWeight);
foreach (var item in _items)
{
temp += item.Value;
if (random < temp) return item.Key;
}
throw new Exception($"unable to determine random {typeof(T)} at {random} in {totalWeight}");
}
}
}
不隶属于 StackOverflow
