從排序列表中加權隨機選擇

Question

我遇到了一個問題，其中有一個按「權重」排序的大量項目列表。我需要能夠從這個列表中隨機選擇項目，但接近開始的項目（更大的權重）必須基於「精英主義」因素選擇的機會更大。

我意識到之前已經問過類似的問題，但這裏的問題在於這個列表會隨着時間而改變。當最後一項被刪除時，新值將被分類到列表中（以保持恆定大小的「優化」值池）。

首先，做選擇最有效的方法是什麼？選擇必須實時從50到1000項長的任何一個列表中進行。

第二，這裏最好的數據結構是什麼？我正在使用C＃。謝謝！

我剛想到一個可能的解決方案，但我想對這個想法提出一些反饋意見。如果我要在一定範圍內生成一個隨機浮動值，然後按照平方線做一些事情呢？小值會返回小值，而大值會返回很大的值。從我所知道的情況來看，將這個結果映射到列表的長度應該會產生預期的效果。這聽起來正確嗎？

Answer 1

創建一個二叉樹，按重量分選（不需要，只不過它在問題中指定排序），併爲每個節點記錄所有的總重量這些孩子。在這個頂部，我們可以計算整個列表的總重量。

挑選一個隨機值r之間的零和總重量的一切。在每個節點上，如果當前節點的權重大於r，那麼這就是你的結果。否則，從r減去當前節點的權重。現在，如果所有剩下的孩子的總重量小於r，則向左走。否則，從r中減去所有剩下的孩子的總重量，然後往右走。重複，直到你有結果。

插入和刪除成本取決於您選擇如何實現和平衡您的樹，但您還必須遍歷所有祖先以更新其權重。

如果您實際上並不需要它，那麼將它作爲堆可能會改善快速行爲。

Answer 2

我會做這樣的事情：

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，它的優點是，如果沒有找到確切的數字，給出下一個最大數字的索引。

現在，隨着doubleweight的IT變得有點複雜了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()方法返回一個數0<=x<1，我們必須轉換爲我們的體重。

基於這一原則，就可以建立一個使用它的List<T>類：

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 3

這是我會做：

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％。

的第二項具有的剩餘的90％= 9％

的第三項具有的剩餘81％= 8.1％

10％10％...

如果增加權重因子，則更有可能選擇列表中最後一項的第一項。 因數爲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% 

EDIT

當然，這將工作僅對於許多索引（至少10爲0.1），否則它會給上一個指數提供更大的概率。 例如，如果weight = 0.1且maxIndex = 1，則索引0將具有10％的概率，但索引1將具有90％。

Answer 4

不幸的是，我不能提供任何代碼的權利，但一些想法：

當你的列表是從高權重低加權排序，你應該能夠使用基於正常的隨機數發生器分配。如果您手頭沒有這樣的隨機數發生器，您可以使用此處找到的代碼將均勻分佈轉換爲正態分佈：Random Gaussian Variables

我很難解釋，但我會嘗試： 您可以定義0的偏差（平均值）和3的西格瑪（偏差）。然後，從生成的數字中獲取絕對值，因爲您可能會得到負數。

這會給你一個數字發生器，它在偏差數（在上面的例子中爲0）附近的可能性很高，並且數字的偏離概率較低。

正如我所說的，我很可怕的解釋