есть ли более быстрый способ поиска по совокупному распределению?

У меня есть List<Double>, который содержит вероятности (веса) для выборки элемента. Например, List содержит 5 следующих значений.

0.1, 0.4, 0.2, 0.1, 0.2

Каждое i-е Double значение представляет собой вероятность выборки i-го элемента из другого List<Object>.

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

Я пробовал что-то вроде этого, где я сначала преобразовал список вероятностей в кумулятивную форму.

0.1, 0.5, 0.7, 0.8, 1.0

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

Random r = new Random();
double p = r.nextDouble();
int total = list.size();
for(int i=0; i < total; i++) {
 double d = list.get(i);
 if(d > p) {
  return i;
 }
}
return total-1;

Этот подход медленный, поскольку я просматриваю список последовательно. На самом деле мой список состоит из 800 000 пунктов, связанных с весами (вероятностями), из которых мне нужно выбрать. Так что, разумеется, этот последовательный подход медленный.

Я не знаю, чем может помочь двоичный поиск. Скажем, я сгенерировал p = 0,01. Затем бинарный поиск может использовать рекурсию со списком следующим образом.

compare 0.01 to 0.7, repeat with L = 0.1, 0.5
compare 0.01 to 0.1, stop 
compare 0.01 to 0.5, stop

0,01 меньше 0,7, 0,5 и 0,1, но я, очевидно, хочу только 0,1. Так что критерии остановки мне все еще не ясны при использовании бинарного поиска.

Если есть библиотека, которая поможет с подобными вещами, мне тоже было бы интересно.


java random algorithm probability
person Jane Wayne    schedule 30.05.2014    source источник
comment
Вы используете одни и те же гири несколько раз? В таком случае поможет двоичный поиск , потому что вы можете преобразовать свой список индивидуальных весов в совокупный список. Однако это не поможет для генерации единственного значения.   -  person Jon Skeet    schedule 30.05.2014
comment
@ GáborBakos Это не совсем сработает, но это правильный подход. Вы генерируете случайное значение, а затем выполняете двоичный поиск в совокупном списке, понимая, что это может быть неточное совпадение.   -  person David Ehrmann    schedule 30.05.2014

Ответы (2)


arrow_upward
2
arrow_downward

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

public static void main (String[] args) {
    double[] cdf = {0.1, 0.5, 0.7, 0.8, 1.0};
    double random = 0.75;  // generate randomly between zero and one
    int el = Arrays.binarySearch(cdf, random);
    if (el < 0) {
        el = -(el + 1);
    }
    System.out.println(el);
}

P.S. Когда список вероятностей невелик, простое линейное сканирование может оказаться таким же эффективным, как двоичный поиск.

person NPE    schedule 30.05.2014

arrow_upward
2
arrow_downward

Это не самый эффективный с точки зрения памяти подход, но используйте NavigableMap, где значения вашего совокупного списка являются ключами. Тогда вы можете просто использовать floorEntry(randon.nextDouble()). Как и бинарный поиск, это пространство журнала (n) и n памяти.

So...

NavigableMap<Double, Object> pdf = new TreeMap<>();
pdf.put(0.0, "foo");
pdf.put(0.1, "bar");
pdf.put(0.5, "baz");
pdf.put(0.7, "quz");
pdf.put(0.8, "quuz");

Random random = new Random();

pdf.floorEntry(random.nextDouble()).getValue();
person David Ehrmann    schedule 30.05.2014