Подскажите эффективный алгоритм!
Есть массив чисел. Нужно случайным образом выбрать из этого массива элемент (определить индекс), но при выборе учитывать вес элементов. Т.е. чем больше значение элемента массива, тем вероятнее выпадение этого элемента. Например, массив из 3 чисел: 2, 4, 8. Вероятность выбора 1го элемента -- 2/14, 2го -- 4/14, 3го -- 8/14.
Количество элементов может быть до 100, значения -- от 0 до 65535. Причем, при нулевом значении элемент никогда не выбирается. А таких элементов может быть достаточно много.
Как можно решить такую задачу минимизируя время и используемую память?
Количество элементов может быть до 100, значения -- от 0 до 65535. Причем, при нулевом значении элемент никогда не выбирается. А таких элементов может быть достаточно много.
Как можно решить такую задачу минимизируя время и используемую память?
Могу только подсказать разновероятностный генератор случайных чисел (получен из равновероятностной rand()).
Воспользуйся определением геометрической вероятности. Оно в данном случае нас устроит, так как события, сопоставленные данным вероятностям составляют полную группу (сумма вероятностей равна 1).
Пусть SUM - сумма элементов исходного массива A. Разобьем интервал 0-SUM на отрезки, равные соотв. значениям массива A. Фактически, нужно составить еще один массив B, по размеру равный исходному+1, соответствующий функции распределения ("интеграл" от исходного массива), последовательно суммируя элементы A и занося промежуточный результат в B (B будет больше на 1, чем А, так как последний элемент должен быть равен sum, число пар i,i+1 должно быть равно n - размер A). Далее получаем псевдослучайную равнораспределенную величину X с помощью rand() в интервале 0-SUM, проходим весь вновь полученный массив B и ищем индекс i, отвечающий условию: B>=X<B[i+1] (проходим все элементы от начального до n-1, где n - размер массива B). В случае, если интервал не найден (например, вероятность на данном участке 0, B=B[i-1]), то берем новое число X или возвращаем управление, сигнализируя о попадании в нуль-вероятностный интервал.
Вероятность выпадания каждого индекса равна:
p=A/SUM
Алгоритм по использованию памяти, как мне кажется, оптимальный, да и по быстодействию, т.е. достаточно эффективный. Массив B строим по следующей формуле:
i:=0,n;
s:=0
s:=s+A;
B=s;
Кстати, для массива B можно использовать сам массив A (!), если его значения дальше не понадобятся. Т.е. фактически нужно просто "проинтегрировать" А:
A:=A+A[i-1]
начиная с i=1 (второго элемента).
p.s. все выкладки приведены с учетом того, что первый элемент массива имеет индекс 0. Если он отличен от 0, то необходимо прежде чем выполнять обращения к A, B в алгоритме генерации нормировать индекс (прибавлять 1).
Воспользуйся определением геометрической вероятности. Оно в данном случае нас устроит, так как события, сопоставленные данным вероятностям составляют полную группу (сумма вероятностей равна 1).
Пусть SUM - сумма элементов исходного массива A. Разобьем интервал 0-SUM на отрезки, равные соотв. значениям массива A. Фактически, нужно составить еще один массив B, по размеру равный исходному+1, соответствующий функции распределения ("интеграл" от исходного массива), последовательно суммируя элементы A и занося промежуточный результат в B (B будет больше на 1, чем А, так как последний элемент должен быть равен sum, число пар i,i+1 должно быть равно n - размер A). Далее получаем псевдослучайную равнораспределенную величину X с помощью rand() в интервале 0-SUM, проходим весь вновь полученный массив B и ищем индекс i, отвечающий условию: B>=X<B[i+1] (проходим все элементы от начального до n-1, где n - размер массива B). В случае, если интервал не найден (например, вероятность на данном участке 0, B=B[i-1]), то берем новое число X или возвращаем управление, сигнализируя о попадании в нуль-вероятностный интервал.
Вероятность выпадания каждого индекса равна:
p=A/SUM
Алгоритм по использованию памяти, как мне кажется, оптимальный, да и по быстодействию, т.е. достаточно эффективный. Массив B строим по следующей формуле:
i:=0,n;
s:=0
s:=s+A;
B=s;
Кстати, для массива B можно использовать сам массив A (!), если его значения дальше не понадобятся. Т.е. фактически нужно просто "проинтегрировать" А:
A:=A+A[i-1]
начиная с i=1 (второго элемента).
p.s. все выкладки приведены с учетом того, что первый элемент массива имеет индекс 0. Если он отличен от 0, то необходимо прежде чем выполнять обращения к A, B в алгоритме генерации нормировать индекс (прибавлять 1).