从偏好列表中选择项目？

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