@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) памяти
  • Вопрос задан
  • 3299 просмотров
Пригласить эксперта
Ответы на вопрос 3
vvpoloskin
@vvpoloskin
Инженер связи
Вот было обсуждение
Ответ написан
Комментировать
WoLfhOUnD
@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
Ответ написан
Комментировать
@bkurdasov
Из документации: 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'
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы