Случайный выбор элемента из взвешенного списка

Question

У меня есть список из 100 000 объектов.Каждый элемент списка имеет связанный с ним «вес», который является положительным целым числом от 1 до N.

Какой самый эффективный способ выбрать случайный элемент из списка?Я хочу, чтобы мое распределение случайно выбранных элементов соответствовало распределению весов в списке.

Например, если у меня есть список L = {1,1,2,5}, яхотите, чтобы 4-й элемент выбирался в среднем в 5/9 от времени.

Предположим, что вставки и удаления являются общими в этом списке, поэтому любой подход, использующий "таблицы интегральных областей", необходимо будет часто обновлять - надеясьСуществует решение с O (1) временем выполнения и O (1) дополнительной памятью.

Answer 1

Вы можете использовать расширенное двоичное дерево поиска для хранения элементов вместе с суммой весов в каждом поддереве.Это позволяет вставлять и удалять элементы и веса по своему усмотрению.Как для выборки, так и для обновления требуется время O (lg n) на операцию, а использование пространства равно O (n).

Выборка выполняется путем генерации случайного целого числа в [1, S], где S - сумма всех весов (S хранится в корне дерева), и выполнения двоичного поиска с использованием весовых суммсохраняется для каждого поддерева.

Answer 2

Мне действительно нравится решение Джондерри, но мне интересно, нужна ли этой проблеме такая сложная структура, как расширенное дерево бинарного поиска.Что если бы мы сохранили два массива, один с входными весами, скажем, a = {1,1,2,5}, а другой с совокупными весами (идея, очень похожая на решение Джондерри), которая была бы b = {1,2,4, 9}.Теперь сгенерируйте случайное число в [1 9] (скажем, x) и выполните его двоичный поиск в массиве накопленных сумм.Место i, где отмечены b [i] <= x и b [i-1]> x, и возвращается [i].Таким образом, если бы случайное число было 3, мы получили бы i = 3, и было бы возвращено [3] = 2.Это обеспечивает ту же сложность, что и решение с расширенным деревом, с более простой реализацией.

Answer 3

Решение, которое работает в O (n), состояло бы в том, чтобы начать с выбора первого элемента. Затем для каждого последующего элемента либо сохраните имеющийся элемент, либо замените его следующим. Пусть w будет суммой всех весов для рассмотренных элементов. Затем сохраните старый с вероятностью w / (w + x) и выберите новый с p = x / (w + x), где x - вес следующего элемента.

Answer 4

Вот что я сделал, чтобы решить:

def rchoose(list1, weights):
    '''
    list1   :    list of elements you're picking from.
    weights :    list of weights. Has to be in the same order as the 
                 elements of list1. It can be given as the number of counts 
                 or as a probability.
    '''

    import numpy as np

    # normalizing the weights list
    w_sum = sum(weights)
    weights_normalized = []
    for w in weights:
        weights_normalized.append(w/w_sum)

    # sorting the normalized weights and the desired list simultaneously
    weights_normalized, list1 = zip(*sorted(zip(weights_normalized, list1)))

    # bringing the sorted tuples back to being lists
    weights_normalized = list(weights_normalized)
    list1 = list(list1)

    # finalizing the weight normalization
    dummy = []; count = 0
    for item in weights_normalized:
        count += item
        dummy.append(count)
    weights_normalized = dummy

    # testing which interval the uniform random number falls in
    random_number = np.random.uniform(0, 1)
    for idx, w in enumerate(weights_normalized[:-1]):
        if random_number <= w:
            return list1[idx]

    return list1[-1]

Answer 5

Если вам известна сумма весов (в вашем случае 9) И вы используете структуру данных с произвольным доступом (список подразумевает O (n) время доступа), то это можно сделать быстро:

1) выберите случайный элемент (O (1)). Поскольку существует вероятность выбора элемента на этом шаге 1/num_elems, это позволяет нам использовать усиление num_elems* для шага 2), тем самым ускоряя алгоритм.

2) вычислить ожидаемую вероятность: num_elems * (weight/total_weight)

3) взять случайное число в диапазоне 0..1, и если оно меньше ожидаемой, у вас есть выход. Если нет, повторите с шага 1)