Pull to refresh

Comments 16

давайте рассмотрим дроби 999999/1000000 и 1/1000000

Иметь массив с миллионом значений — это как-то странно. Зачем? Когда мы получили индекс в условной честной кости, просто сравниваем — индекс меньше 999999? Значит ноль. Больше — один. Массив с 999999 нулями абсолютно не нужен.


Дальше не стал читать, не похоже, что автор исходной статьи профессионал.

Боюсь, что непрофессионал — это вы. Потому что если рассмотреть случай кости с одной гранью, алгоритм вообще не нужен, можно сразу вернуть константу. Как вы упустили такую очевидную оптимизацию?

Я её не упустил. Автор рассмотрел две грани, я тоже рассмотрел две грани. Зачем вы говорите про одну грань, мне не понятно. В случае N граней схема примерно такая же. Если выбросили меньше шести — ответ ноль. Меньше 6+4 — ответ один. Меньше 6+4+1 — ответ два. Иначе — ответ три. (Это для случая самой первой шуллерской кости из статьи)


Генерация таких условий достаточно проста и намного выгоднее по памяти, чем массив. Если минусующие кроме минуса ещё и пояснят, в чем я ошибаюсь, буду благодарен.

Формально — в том, что для произвольного количества граней ваш вариант будет О(n) по времени (ну, O(log(n)), если с двоичным поиском). А вариант с массивом — О(1). То есть хотя бы по одной метрике авторский вариант превосходит ваш.

По сути — в том, что вы заранее предполагаете, что автора глупее вас. И столкнувшись с примером, который он приводит для подготовки к введению действительно крутого алгоритма, утверждаетесь в своём предположении и до этого алгоритма не дочитываете.

Alias — действительно крутой алгоритм, тут возражений нет. Но качество алгоритма и качество статьи стоит рассматривать отдельно.


ну, O(log(n)), если с двоичным поиском

Согласен, я действительно упустил этот момент.

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

Минусы этого алгоритма, кстати, понятны — НОК может быть очень высок и не влезать в MAX_INT используемого языка программирования. Придется использовать библиотеку для работы с большими числами. Рулетка более удобна. Но генерировать массив — это явно странное решение, разве нет?

Шулерская кость из честных костей/несимметричных монет
(бросание дротика)
Не будет ли, для этого метода, худшим случаем бесконечное число бросков? Ведь если для любого броска существует вероятность не попасть, то, существует вероятность, что мы не попадем никогда. Или я что-то не учитываю?
Автор просто в колонку «наихудшее» поместил ожидаемое значение, а не наихудшее.
Худший случай в данном случае и есть «бесконечное много бросков», т.к. вероятность попасть за N бросков стремится к 1, при N->∞
Вот спасибо. Давно искал нечто подобное для генерации новых фишек на поле, с вероятностью, зависящей от их количества на поле. До этого приходилось делать кучу и из неё выборку…
Очень странная терминология использована в статье: вместо «шулерских монет» обычно говорят о распределении Бернулли, «Alias-метод Воуза» куда чаще называют «методом Уолкера», более того — его постоянно применяют, например, он используется в R в функции sample(). И уж куда большую ошибку при моделировании вносят не double-ы с их мантиссой аж в 52 бита, а используемый датчик псевдослучайных чисел (у которого состояние или выход и вовсе может быть в 32 бита).
Речь вроде была о влиянии точности вычислений на сходимость алгоритма построения таблиц. Причем тут вообще ГСЧ? В построении таблиц он никак не участвует.
Очень полезная статья. Много раз в задачах моделирования и/или симуляции сталкивался с необходимостью делать выборки из различных распределений. С непрерывными распределениями все достаточно очевидно, а вот с дискретными приходилось возиться. И чем меньше симметрии, тем больше возни. Alias-метод сильно упрощает дело. Автору спасибо.
Пример на дробях наглядно показывает, что можно реализовать аналогичный целочисленный алгоритм без погрешности, если НОК знаменателя не велик.
Sign up to leave a comment.

Articles