Syb*_*eus 6 c# random algorithm
我有一个有效的加权选择算法,但我想在两个方面(按重要性顺序)改进它:
编辑:为了我的目的,请求的数量通常很小(小于100).因此,具有复杂度O(t)或O(t + n)的算法,其中t是项的总数,由于O(t) > O(m),通常比O(nm)表现更差.
简化代码:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Security.Cryptography;
public class Program
{
static void Main(string[] args)
{
// List of items with discrete availability
// In this example there is a total of 244 discrete items and 3 types,
// but there could be millions of items and and hundreds of types.
List<Stock<string>> list = new List<Stock<string>>();
list.Add(new Stock<string>("Apple", 200));
list.Add(new Stock<string>("Coconut", 2));
list.Add(new Stock<string>("Banana", 42));
// Pick 10 random items
// Chosen with equal weight across all types of items
foreach (var item in Picker<string>.PickRandom(10, list))
{
// Do stuff with item
Console.WriteLine(item);
}
}
}
// Can be thought of as a weighted choice
// where (Item Available) / (Sum of all Available) is the weight.
public class Stock<T>
{
public Stock(T item, int available)
{
Item = item;
Available = available;
}
public T Item { get; set; }
public int Available { get; set; }
}
public static class Picker<T>
{
// Randomly choose requested number of items from across all stock types
// Currently O(nm), where n is requested number of items and m is types of stock
// O(n) or O(m) would be nice, which I believe is possible but not sure how
// O(1) would be awesome, but I don't believe it is possible
public static IEnumerable<T> PickRandom(int requested, IEnumerable<Stock<T>> list)
{
// O(m) : to calcuate total items,
// thus implicitly have per item weight -> (Item Available) / (Total Items)
int sumAll = list.Sum(x => x.Available);
// O(1)
if (sumAll < requested)
throw new ArgumentException("Requested amount must not exceed total available");
// O(1)
Random rng = new Random(Seed());
// O(n) for the loop alone : O(nm) total
for (int n = 0; n < requested; n++)
{
// O(1) to choose an item : uses implicit ordering
int choice = rng.Next(1, sumAll);
int current = 0;
// O(m) to find the chosen item
foreach (Stock<T> stock in list)
{
current += stock.Available;
if (current >= choice)
{
yield return stock.Item;
// O(1) to re-calculate weight once item is found
stock.Available -= 1;
sumAll--;
break;
}
}
}
}
// Sufficiently random seed
private static int Seed()
{
byte[] bytes = new byte[4];
new RNGCryptoServiceProvider().GetBytes(bytes);
return bytes[0] << 24 | bytes[1] << 16 | bytes[2] << 8 | bytes[3];
}
}
该函数PickRandom()使用yield return和IEnumerable,但不是必需的.我只是在第一次编写函数时试图变得聪明,这样它就可以迭代任何东西(甚至可以说从LINQ to SQL查询中可以枚举).之后,我发现虽然灵活性很好,但我从未真正需要它.
我首先考虑解决点#1(保证选择每个可能选择的最小数量)将是以完全非随机的方式从每种类型中选择所需的最小值,使用我现有的算法来选择剩余的无约束部分,然后将结果混合在一起.这似乎是最自然的,模仿我在现实生活中会做这样的事情,但我认为这不是最有效的方式.
我的第二个想法是首先创建一个结果数组,随机选择索引以首先填充所需的最小值,然后使用我现有的算法填充其余的,但在我所有的尝试中,这最终增加了"大O"的复杂性或作为一个到处都记录着大量的索引.我仍然认为这种方法是可行的,我还没有能够解决这个问题.
然后决定来这里,因为这个问题似乎可以被抽象为一个相当通用的算法,但我用来搜索的所有关键词通常都指向基本的加权随机数生成(而不是选择按类型分类的离散项目)可用性).并且无法找到任何限制每个项目类型的最小选择的问题,同时仍然保持随机化.因此,我希望有人能够看到一个简单有效的解决方案,或者之前听过这个问题的人知道一些比我更好的关键词并且可以指出我正确的方向.
这是一个粗略的想法；我确信它可以进一步改进：
假设每个可用项目都有一个在[0..sumAll[范围内的唯一 ID ，其中sumAll是可用项目数。因此，第一个苹果的 ID 为 0，最后一个苹果的 ID 为 199，第一个椰子的 ID 为 200，依此类推。确定sumAll和每种类型的子范围是O(m)，其中m是类型的数量。
选择一个随机 ID（所有 ID 具有相同的权重）。重复此操作，直到获得一组 10 个不同的 ID。这是O(n)，其中n是要挑选的物品数量。
使用二分搜索确定每个选取的 ID 的类型。这是O(n log m)。
从可用项目中删除选取的项目。这是O(m)。
为了保证为每种类型挑选的物品数量最少，在第 1 步之前挑选这些物品并将其从可用物品中删除听起来是个好主意。这是O(m)。