随机加权选择

Question

我有这样的数据：d = (  (701, 1, 0.2),  (701, 2, 0.3),  (701, 3, 0.5),  (702, 1, 0.2),  (702, 2, 0.3),  (703, 3, 0.5))其中（701，1，0.2）=（id1，id2，优先级）如果我知道ID1，是否有使用优先级选择ID2的好方法？Func（701）应该返回：  1-在20％的情况下  2-30％  3-50％百分比当然是粗糙的

Answer 1

因此，为每个ID1生成一个累积分布函数：

cdfs = defaultdict()

for id1,id2,val in d:

    prevtotal = cdfs[id1][-1][0]

    newtotal = prevtotal + val

    cdfs[id1].append( (newtotal,id2) )

所以你会有

cdfs = { 701 : [ (0.2,1), (0.5,2), (1.0,3) ], 

         702 : [ (0.2,1), (0.5,2) ],

         703 : [ (0.5,3) ] }

然后生成一个随机数并在列表中搜索。

def func(id1):

    max = cdfs[id1][-1][0]

    rand = random.random()*max

    for upper,id2 in cdfs[id1]:

        if upper>rand:

            return id2

    return None

Answer 2

意识到我的第一个答案在数学上有很多错误，我提出了一个新的主意。我相信这里的算法类似于其他几个答案的算法，但是这种实现似乎可以满足问题的“漂亮”（如果相等）的要求：

def func(id):

    rnd = random()

    sum = 0

    for row in d:

        if row[0] == id:

            sum = sum + row[2]

            if rnd < sum:

                return row[1]

使用OP中的示例数据，结果如下：

选择一个介于0到1.0之间的随机数

如果数字< 0.2返回第一个元素

否则，如果数字< 0.5返回第二个元素

否则（如果数字为< 1.0），则返回第三个元素