Какой алгоритм будет самым быстрым для случайного выбора N элементов из списка на основе распределения весов?

Question

У меня большой список элементов, у каждого элемента есть вес.

Я хотел бы выбрать N элементов случайным образом без замены, тогда как элементы с большим весом будут выбраны с большей вероятностью.

Я ищу наиболее эффективную идею. Производительность превыше всего. Есть идеи?

Answer 1

Если вы хотите образец элементов без замены , у вас есть множество вариантов.

• Используйте алгоритм взвешенного выбора с заменой (например, WeightedChoice ниже ) для выбора случайных индексов. Каждый раз, когда выбирается индекс, устанавливайте вес для выбранного индекса на 0, чтобы он не выбирался снова. Или ...
• Присвойте каждому индексу экспоненциально распределенное случайное число (со скоростью, равной весу этого индекса), составьте список пар, присваивающих каждое число индексу, затем отсортируйте этот список по этим числам. Затем возьмите каждый предмет от первого до последнего. Обратите внимание, что наивный способ сгенерировать случайное число, -ln(1-RNDU01())/weight, не является надежным (« Индекс неоднородных распределений » в разделе «Экспоненциальное распределение»).
• Tim Виейра приводит дополнительные параметры в своем блоге.
• A статья Брэма ван де Клундерт сравнивает различные алгоритмы.

EDIT (август. 19): Обратите внимание, что для этих решений вес показывает, насколько вероятно, что данный элемент появится первым в образце. Этот вес не обязательно является вероятностью того, что данная выборка из n элементов будет включать этот элемент (то есть, вероятность включения ). Приведенные выше методы не обязательно гарантируют, что данный предмет появится в случайной выборке с вероятностью, пропорциональной его весу; для этого см. « Алгоритмы выборки с равными или неравными вероятностями ».

Предыдущий пост:

Предполагая, что вы хотите выбирать элементы случайным образом с заменой, вот псевдокод, реализующий такой выбор. Учитывая список весов, он возвращает случайный индекс (начиная с 0), выбранный с вероятностью, пропорциональной его весу. См. Также « Взвешенный выбор ».

METHOD WChoose(weights, value)
    // Choose the index according to the given value
    lastItem = size(weights) - 1
    runningValue = 0
    for i in 0...size(weights) - 1
       if weights[i] > 0
          newValue = runningValue + weights[i]
          lastItem = i
          // NOTE: Includes start, excludes end
          if value < newValue: break
          runningValue = newValue
       end
    end
    // If we didn't break above, this is a last
    // resort (might happen because rounding
    // error happened somehow)
    return lastItem
END METHOD

METHOD WeightedChoice(weights)
    return WChoose(weights, RNDINTEXC(Sum(weights)))
END METHOD

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

• Метод псевдонима Восе, вариант исходного метода псевдонима Уокера. См. « Дартс, кости и монеты: выборка из дискретного распределения » Кейт Шварц для получения дополнительной информации.
• Быстро загружаемый ролик для игры в кости .

Answer 2

Пусть A будет массивом элементов с x itens. Сложность каждого метода определяется как

---

Если сортировка возможна:

1. сортировать A по весу itens.

2. создать массив B, например:

   • B = [ 0, 0, 0, x/2, x/2, x/2, x/2, x/2 ].
   • ясно видно, что B имеет большую вероятность выбора x/2.

3. если вы еще не выбрали n элементов, выберите случайный элемент e из B.

4. выберите случайный элемент из A в интервале e : x-1.

---

Если итерация по itens возможна:

1. итерация через A и нахождение средний вес w элементов.
2. определить максимальное количество попыток t.
3. попытаться (не более t раз) выбрать случайное число из A чей вес больше w.
   • тест для некоторых t, который дает хорошие / удовлетворительные результаты.

---

Если ничего из вышеперечисленного невозможно:

1. определяет максимальное количество попыток t.
2. если вы еще не выбрали n элементов, возьмите t случайные элементы в A.
3. выберите элемент с наибольшим значением.
   • тест для некоторых t, который дает хорошие / удовлетворительные результаты.