Какие есть способы реализации случайной выборки с учетом веса?

Question

[Darsatan]

Имеется список таплов, например
inp = [('a', 1), ('b', 3), ('c', 2)]
Как можно реализовать выборку случайного элемента, с учетом его веса?
Сейчас на ум приходит только 2 варианта

1. Прописать каждому элементу "промежуток", где длина = вес, т.е. что-то типо
   tmp = [('a', 0, 1), ('b', 2, 4), ('c', 5, 6)]
   генерировать случайное число [0, 6] и находить соответствие в списке
2. Сделать новый массив, где количество повторений каждого элемента = его весу, т.е.
   

   lst = []
   for elem, weight in inp:
       lst.extend([elem] * weight)

   
   И далее random.choice(lst)

Update: оптимальным вариантом оказался следующий способ:

1. подсчитываем сумму всех весов в переданном списке, обозначим ее weight_sum.
2. находим случайное число от 1 до weight_sum, запомним как rand_res
3. проходим по списку и вычитаем от rand_res вес текущего элемента. Там где rand_res <= 0 лежит искомый случайный элемент./li>
   

Этот способ при минимальной доработке хорошо работает если необходимо вернуть k случайных элементов. Работает за О(n*(k+1)) и требует О(k) памяти

Comments

[Mintormo]

Если заранее считать сумму весов и передавать ее в функцию как параметр, то можно улучшить эффективность до O(n*k), так как считать сумму весов не надо и мы избавляемся от одного N. Вот бы еще придумать как сделать требование по памяти O(1) и функция бы считала за O(n*k) с подсчетом суммы весов!

Answer 1

[Валентин]

Вот было обсуждение

Answer 2

[WoLfhOUnD]

Не помню откуда взял:

import random

def choice_equel(seq, p):
        p = list(p)
    for i in range(len(p) - 1):
        p[i+1] = p[i+1] + p[i]
 
    rnd = random.random()
    for index, value in enumerate(p):
        if rnd <= value:
            return index 
 
if __name__ == '__main__':
    system = [
        'SMALL',
        'MEDIUM',
        'LARGE'
    ]
    stats = [0,0,0]
    for i in xrange(1000000):
        index = choice_equel(system, (0.3, 0.5, 0.2))
        stats[index] = stats[index] + 1
    print stats

Answer 3

[Boris]

Из документации: A common task is to make a random.choice() with weighted probabilities. If the weights are small integer ratios, a simple technique is to build a sample population with repeats:

>>> weighted_choices = [('Red', 3), ('Blue', 2), ('Yellow', 1), ('Green', 4)]
>>> population = [val for val, cnt in weighted_choices for i in range(cnt)]
>>> random.choice(population)
'Green'