從偏好列表中選擇項目？

Question

給定項目x1 ... xn和相關概率p1 ... pn的列表，總計爲1，有一個衆所周知的過程，通過根據權重對列表進行排序來選擇隨機項目及其相關的可測性，選擇一個隨機1和0之間的值，並加起來，直到超過所選值並返回此時的項目。所以如果我們有x1-> 0.5，x2-> 0.3，x3-> 0.2，如果隨機選擇的值小於0.5，將選擇0.5x1，如果在0.5和0.8之間，x2和x3。

這需要排序，所以它需要O（nlogn）時間。有沒有比這更有效的東西？

Answer 1

我不認爲你實際上需要排序算法的工作列表。

X1 = 0.2，X2 = 0.7，X3 = 0.1

如果您排序，那麼你必須：

x3: 0.0 to 0.1 = 10% 
x1: 0.1 to 0.3 = 20% 
x2: 0.3 to 1.0 = 70% 

如果你沒有，你反而得到：

x1: 0.0 to 0.2 = 20% 
x2: 0.2 to 0.9 = 70% 
x3: 0.9 to 1.0 = 10% 

只是消除排序和迭代將使它O（n）。