Быстрый взвешенный случайный выбор из очень большого набора значений

Question

В настоящее время я работаю над проблемой, которая требует случайного выбора элемента из набора.Каждый из элементов имеет вес (вероятность выбора), связанный с ним.

Моя проблема заключается в том, что для наборов с небольшим количеством элементов, скажем 5-10, сложность (время выполнения) решения, которым я былдопустимо, однако по мере увеличения количества элементов, скажем, для 1K или 10K и т. д., время работы становится неприемлемым.

Моя текущая стратегия:

1. Выберите случайное значение X с диапазоном [0, 1)
2. Повторять элементы, суммируя их веса, пока сумма не станет больше X
3. Элемент, из-за которого сумма превысила X, выбирается и возвращается

Длядля больших множеств и большого числа выборок этот процесс начинает проявлять квадратичное поведение, короче говоря, есть ли более быстрый путь?возможно, лучший алгоритм?

Answer 1

Вы хотите использовать алгоритм Уокера. С N элементами есть настройка стоимость O (N). Однако стоимость выборки составляет O (1). См

• A. Дж. Уокер, Эффективный метод генерации Дискретные случайные величины и общие распределения, ACM TOMS 3, 253-256 (1977).
• Кнут, TAOCP, том 2, раздел 3.4.1.A.

Класс RandomSelect a RandomLib реализует этот алгоритм.

Answer 2

Предполагая, что веса элементов фиксированы, вы можете работать с предварительно вычисленными суммами.Это похоже на работу с кумулятивной функцией вероятности напрямую, а не с функцией плотности.

Поиск может быть реализован в виде двоичного поиска и, следовательно, может быть log (N) по числу элементов.

Бинарный поиск, очевидно, требует random_access для контейнера весов.

В качестве альтернативы, используйте std::map<> и upper_bound() метод.

#include <iostream>
#include <map>
#include <stdlib.h>

int main ()
{
  std::map<double, char> cumulative;
  typedef std::map<double, char>::iterator It;

  cumulative[.20]='a';
  cumulative[.30]='b';
  cumulative[.40]='c';
  cumulative[.80]='d';
  cumulative[1.00]='e';

  const int numTests = 10;
  for(int i = 0;
      i != numTests;
      ++i)
  {
      double linear = rand()*1.0/RAND_MAX;  
      std::cout << linear << "\t" << cumulative.upper_bound(linear)->second << std::endl;
  }

  return 0;
}

Answer 3

Если у вас есть достаточно быстрый способ равномерной выборки случайного элемента, вы можете использовать выборку отклонения;все, что вам нужно знать, это максимальный вес.Это будет работать следующим образом. Предположим, максимальный вес равен M. Выберите число X равномерно в [0,1].Сэмплируйте элементы несколько раз, пока не найдете тот, чей вес составляет не менее M * X;выберите это.

Или приблизительное решение: выберите 100 элементов равномерно наугад;выберите один пропорциональный весу в этом наборе.