从排序列表中加权随机选择

Question

我有一个很大的项目列表按 "weights" 排序的问题。我需要能够从此列表中随机选择 select 项，但越靠近开头（权重越大）的项必须有更大的机会根据 "elitism" 因素被 selected .

我知道以前有人问过类似的问题，但这里要注意的是这个列表会随着时间的推移而改变。删除最后一项时，新值将被排序到列表中（以保持 "optimized" 值的恒定大小池）。

首先，进行 selection 最有效的方法是什么？必须从 50 到 1000 项长度的列表中实时进行选择。

其次，在这里使用什么数据结构最好？我正在使用 C#。

我只是想到了一个可能的解决方案，但我想要一些关于这个想法的反馈。如果我要生成一个特定范围内的随机浮点值，然后按照对它求平方的方式做一些事情，会怎样？小值会 return 小值，大值会 return 大得多的值。据我所知，将此结果映射到列表的长度应该会产生预期的效果。这听起来对吗？

Answer 1

我会做类似的事情：

string[] names = new[] { "Foo", "Bar", "Fix" };

// The weights will be 3, 2, 1
int[] weights = new int[names.Length];
for (int i = 0; i < names.Length; i++)
{
    weights[i] = names.Length - i;
}

int[] cumulativeWeights = new int[names.Length];

// The cumulativeWeights will be 3, 5, 6
// so if we generate a number, 1-3 Foo, 4-5 Bar, 6 Fiz
cumulativeWeights[0] = weights[0];
int totalWeight = weights[0];

for (int i = 1; i < cumulativeWeights.Length; i++)
{
    cumulativeWeights[i] = cumulativeWeights[i - 1] + weights[i];
    totalWeight += weights[i];
}

var rnd = new Random();

while (true)
{
    int selectedWeight = rnd.Next(totalWeight) + 1; // random returns 0..5, +1 == 1..6
    int ix = Array.BinarySearch(cumulativeWeights, selectedWeight);
    // If value is not found and value is less than one or more 
    // elements in array, a negative number which is the bitwise 
    // complement of the index of the first element that is 
    // larger than value.
    if (ix < 0)
    {
        ix = ~ix;
    }

    Console.WriteLine(names[ix]);
}

我构建了一个 weight 的数组。我使用了线性方法。第一个元素的权重等于 (元素数量)，第二个元素的权重等于 (元素数量 - 1)，依此类推。您可以使用您的算法，但如果权重是整数，则更容易。

然后我计算了一个cumulativeWeights数组和一个totalWeight.

然后我可以提取 1 和 totalWeight 之间的二进制数，并找到具有 <= 随机数的 cumulativeWeight 的索引。被 cumulativeWeights 排序（显然 :-) ），我可以使用 Array.BinarySearch，它的优点是如果找不到确切的数字，则会给出下一个最大数字的索引。

现在，有了 double weights，Random 部分变得有点复杂：

string[] names = new[] { "Foo", "Bar", "Fix" };

// The weights will be 3.375, 2.25, 1.5
double[] weights = new double[names.Length];
for (int i = 0; i < names.Length; i++)
{
    weights[i] = Math.Pow(1.5, names.Length - i);
}

double[] cumulativeWeights = new double[names.Length];

// The cumulativeWeights will be 3.375, 3.375+2.25=5.625, 3.375+2.25+1.5=7.125
// so if we generate a number, 1-3.375 Foo, >3.375-5.625 Bar, >5.625-7.125 Fiz
// totalWeight = 7.125
cumulativeWeights[0] = weights[0];
double totalWeight = weights[0];

for (int i = 1; i < cumulativeWeights.Length; i++)
{
    cumulativeWeights[i] = cumulativeWeights[i - 1] + weights[i];
    totalWeight += weights[i];
}

var rnd = new Random();

while (true)
{
    // random returns (0..1 * totalWeight - 1) + 1 = (0...6.125) + 1 = 1...7.125
    double selectedWeight = (rnd.NextDouble() * (totalWeight - 1)) + 1; 

    int ix = Array.BinarySearch(cumulativeWeights, selectedWeight);
    // If value is not found and value is less than one or more 
    // elements in array, a negative number which is the bitwise 
    // complement of the index of the first element that is 
    // larger than value.
    if (ix < 0)
    {
        ix = ~ix;
    }

    Console.WriteLine(names[ix]);
}

Random.NextDouble() 方法 returns 一个数字 0<=x<1 我们必须将其转换为我们的体重。

基于该原理，可以构建一个使用它的 List<T> class:

public class ListWithWeight<T>
{
    private readonly List<T> List = new List<T>();

    private readonly List<double> CumulativeWeights = new List<double>();

    private readonly Func<int, double> WeightForNthElement;

    private readonly Random Rnd = new Random();

    public ListWithWeight(Func<int, double> weightForNthElement)
    {
        WeightForNthElement = weightForNthElement;
    }

    public void Add(T element)
    {
        List.Add(element);

        double weight = WeightForNthElement(List.Count);

        if (CumulativeWeights.Count == 0)
        {
            CumulativeWeights.Add(weight);
        }
        else
        {
            CumulativeWeights.Add(CumulativeWeights[CumulativeWeights.Count - 1] + weight);
        }
    }

    public void Insert(int index, T element)
    {
        List.Insert(index, element);

        double weight = WeightForNthElement(List.Count);

        if (CumulativeWeights.Count == 0)
        {
            CumulativeWeights.Add(weight);
        }
        else
        {
            CumulativeWeights.Add(CumulativeWeights[CumulativeWeights.Count - 1] + weight);
        }
    }

    public void RemoveAt(int index)
    {
        List.RemoveAt(index);
        CumulativeWeights.RemoveAt(List.Count);
    }

    public T this[int index]
    {
        get
        {
            return List[index];
        }

        set
        {
            List[index] = value;
        }
    }

    public int Count
    {
        get
        {
            return List.Count;
        }
    }

    public int RandomWeightedIndex()
    {
        if (List.Count < 2)
        {
            return List.Count - 1;
        }

        double totalWeight = CumulativeWeights[CumulativeWeights.Count - 1];
        double selectedWeight = (Rnd.NextDouble() * (totalWeight - 1.0)) + 1;

        int ix = CumulativeWeights.BinarySearch(selectedWeight);
        // If value is not found and value is less than one or more 
        // elements in array, a negative number which is the bitwise 
        // complement of the index of the first element that is 
        // larger than value.
        if (ix < 0)
        {
            ix = ~ix;
        }

        // We want to use "reversed" weight, where first items
        // weight more:

        ix = List.Count - ix - 1;
        return ix;
    }
}

和

var lst = new ListWithWeight<string>(x => Math.Pow(1.5, x));
lst.Add("Foo");
lst.Add("Bar");
lst.Add("Fix");
lst.RemoveAt(0);
lst.Insert(0, "Foo2");

while (true)
{
    Console.WriteLine(lst[lst.RandomWeightedIndex()]);
}

Answer 2

这就是我要做的：

private static int GetPosition(double value, int startPosition, int maxPosition, double weightFactor, double rMin)
{
    while (true)
    {
        if (startPosition == maxPosition) return maxPosition;

        var limit = (1 - rMin)*weightFactor + rMin;
        if (value < limit) return startPosition;
        startPosition = startPosition + 1;
        rMin = limit;
    }
}

static void Main()
{
    const int maxIndex = 100;
    const double weight = 0.1;

    var r = new Random();
    for (var i = 0; i < 200; i++)
        Console.Write(GetPosition(r.NextDouble(), 0, maxIndex, weight, 0) + " ");
}

0.1 的权重因子意味着第一个项目有 10% 的机会被选中。所有其他项目都有 90%。

第2项占剩余90%的10%=9%

第三项占剩余81%的10% = 8.1%

...

随着权重因子的增加，选择列表中第一个项目的可能性会高于最后一个项目。系数为 1 时，只会选择第一项。

对于权重为 0.1 和 10 的项目，以下是每个索引的概率：

0: 10%
1: 9%
2: 8.1%
3: 7.29%
4: 6.56%
5: 5.9%
6: 5.31%
7: 4.78%
8: 4.3%
9: 3.87%

编辑

当然，这只适用于许多索引（0.1 至少有 10 个），否则它会为最后一个索引提供更大的概率。例如，如果 weight = 0.1 且 maxIndex = 1，则索引 0 的概率为 10%，而索引 1 的概率为 90%。

Answer 3

很遗憾，我现在无法提供任何代码，但有一些想法：

由于您的列表是从高权重到低权重排序的，您应该能够使用基于正态分布的随机数生成器。如果手边没有这样的随机数生成器，可以使用此处的代码将均匀分布转换为正态分布：Random Gaussian Variables

我不太擅长解释，但我会尝试：您可以将偏差（平均值）定义为 0，将西格玛（偏差）定义为 3。然后您从生成的数字中获取绝对值，因为您可能会得到负数。

这将为您提供一个数字生成器，它在偏差数（上例中为 0）附近的概率很高，而偏离那里的数字概率较低。

正如我所说，我不善于解释

Answer 4

创建一棵二叉树，按权重排序（不需要排序，除非在问题中指定），并为每个节点记录所有children的总权重。在这个上面我们可以计算出整个列表的总权重。

在零和所有物品的总重量之间选择一个随机值 r。在每个节点，如果当前节点的权重大于 r 那么这就是你的结果。否则从r中减去当前节点的权重。现在，如果所有左边 children 的总重量小于 r 则向左走。否则从r中减去所有左边children的总重量，然后向右走。重复直到得到结果。

插入和删除成本取决于您选择如何实现和平衡您的树，但您还必须遍历所有祖先来更新它们的权重。

如果您实际上不需要对其进行排序，那么将其设为堆可能会改善 fast-out 行为。

从排序列表中加权随机选择

Weighted Random Selection from a Sorted List

c#

random

sortedlist

data-structures