Взвешенная вероятность с длинными двойниками

Question

Взвешенная вероятность с длинными двойниками

Я работаю с массивом примерно 2000 элементов в C ++.

Каждый элемент представляет вероятность случайного выбора этого элемента.

Затем я преобразовал этот массив в накопительный массив, чтобы использовать его для определения, какой элемент выбрать при броске костей.

Пример массива:
{1,2,3,4,5}

Пример накопительного массива:
{1,3,6,10,15}

Я хочу иметь возможность выбрать 3 в совокупном массиве, когда выпадают числа 3, 4 или 5.

Дополнительная сложность заключается в том, что мой массив состоит из длинных двойных чисел. Вот пример нескольких последовательных элементов:

0,96930161525189592646367317541056252139242133125662803649902343750
0,96941377254127855667142910078837303444743156433105468750000000000
0,96944321382974149711383993199831365927821025252342224121093750000
0,96946143938926617454089618153290075497352518141269683837890625000
0,96950069444055009509463721739663810694764833897352218627929687500
0,96951751803395748961766908990966840065084397792816162109375000000

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

1

c++long-double probability vector

Решение

Другие решения

рассмотрите возможность хранения информации в виде целого числа и знаменателя, чтобы не допустить потери точности до последнего шага.

1

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

public static int selectRandomWeighted(double[] wts, Random rnd) {
int selected = 0;
double total = wts[0];

for( int i = 1; i < wts.length; i++ ) {
total += wts[i];

if( rnd.nextDouble() <= (wts[i] / total)) {
selected = i;
}
}

return selected;
}

Вышесказанное может быть дополнительно улучшено с помощью Суммирование Кахана если вы хотите сохранить как можно больше цифр точности в сумме.

Однако, если вы хотите рисовать из этого массива несколько раз, то предварительное вычисление массива частичных сумм и использование двоичного поиска для поиска правильного индекса будет быстрее.

1

Хорошо, я думаю, что решил это.

Я просто сделал бинарный поиск, но вместо того, чтобы просто

if (arr[middle] == value)

Я добавил в ИЛИ

if (arr[middle] == value || (arr[middle] < value && arr[middle+1] > value))

Это похоже на то, на что я надеялся.

0

Источник

Accepted Answer

Ты можешь использовать partial_sum:

unsigned int SIZE = 5;
int array[SIZE] = {1,2,3,4,5};
int partials[SIZE] = {0};

partial_sum(array, array+SIZE, partials);
// partials is now {1,3,6,10,15}

Требуемое значение из массива доступно из частичных сумм:

12 == array[2] + array[3] + array[4];

12 == partials[4] - partials[1];

Сумма, очевидно, является последним значением в частичных суммах:

15 == partial[4];

2