Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
В целом мысль понял и даже, частично! согласен. Только я бы упростил формулировку Есть N^K возможных значений, где K это кол-во данных/циферек на входе, нужно разложить по M равным кучкам.... Почему "частично", т.к. у автора поток данных скорее бесконечный и "Если кругов дофига, то имеет ли значение для задачи, насколько нек-рые из меньших цифр будут менее вероятны? на мизер ведь, и этот мизер с каждым кругом будет уменьшаться." Во вторых, все же остается не очень понятно, почему мы обязаны раскладывать все возможные значения по M равным кучкам. Предположим, что у нас есть M кучек, куда нам нужно разложить "ровно", +/dev/null куда мы можем выкинуть то, что не разложилось. Как я представлял бы данную задачу __практически__ (мы же в форуме программирование): Есть аппаратный генератор случайных чисел от 0..N (я бы для упрощения предложил 0 / 1), нужен алгоритм генерации числа 0..M максимально экономно использующий входные данные. Попытаюсь объяснить свою идея с /dev/null: Предположим на входе поток битов, нам нужно набрать байты. Пусть мы банально склееваем биты друг с другом. Понятно, что если на входе пришло 15 битов (k=15), мы можем склееть только один байт, а 7 оставшихся битов уйдут в /dev/null. Станет ли от этого первый получившися байт хуже "вероятным"? С точки зрения делетанта, сидящего на окладе ниже рыночного ))) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 22:42 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev все же остается не очень понятно, почему мы обязаны раскладывать все возможные значения по M равным кучкам. Предположим, что у нас есть M кучек, куда нам нужно разложить "ровно", +/dev/null куда мы можем выкинуть то, что не разложилось. 22078105 авторРешение, пропускать числа, не попадающие в рейндж, не очень интересно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 22:51 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev Почему "частично", т.к. у автора поток данных скорее бесконечный и "Если кругов дофига, то имеет ли значение для задачи, насколько нек-рые из меньших цифр будут менее вероятны? на мизер ведь, и этот мизер с каждым кругом будет уменьшаться." потому, можно сделать только приблизительную равновероятность. Некоторые кучки получат на единицу больше, их вероятность будет на 1/N k выше чем у "маленьких кучек", и увеличивая k, мы сокращаем разницу ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 22:54 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1, то, что работает с rand, это не функция, в формальном смысле, и не может ею быть. Это процесс, вычислительный. Процессу принципиально разрешается работать бесконечно. PS Красиво рассуждаешь. Чувствуется образование. Совсем не частый для форума случай ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 23:26 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 Leonid Kudryavtsev Почему "частично", т.к. у автора поток данных скорее бесконечный и "Если кругов дофига, то имеет ли значение для задачи, насколько нек-рые из меньших цифр будут менее вероятны? на мизер ведь, и этот мизер с каждым кругом будет уменьшаться." потому, можно сделать только приблизительную равновероятность. Некоторые кучки получат на единицу больше, их вероятность будет на 1/N k выше чем у "маленьких кучек", и увеличивая k, мы сокращаем разницу Вроде даже и согласен, но "не убедили" Даже сел писать код, но дошел до того, о чем говорил mayton 22078740 остаток получается в виде дроби, и что с ним потом делать (как применить операцию остаток от деления к дроби), в 3-и часа ночи после работы как-то сильно заумно ))) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 03:57 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Если мы будем делить 6 на 10 то получим рациональный коэффициент вида 6/10 или 3/5 Если мы будем умножать random(10) на рациональный тип данных вида rational(3,5) и в результате - получим красивое линейное распределение РАЦИОНАЛЬНЫХ чисел в диапазоне от 0 до 5. Далее - сложение и перенос в диапазон от 2 до 7. ну, допустим, вместо чисел 0...4 у нас появятся числа 0, 3/5, 6/5, 9/5, 12/5. Всё равно их не раскидать равномерно на 0, 1, 2 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 08:25 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
booby то, что работает с rand, это не функция, в формальном смысле, и не может ею быть. Это процесс, вычислительный. Процессу принципиально разрешается работать бесконечно. только на момент первого (да и любого по счету) результата рандомайзер будет вызван конечное количество раз. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 08:27 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 боюсь, что равномерно смапить (0, 1, ... 9) в (2, 3, ..., 7) не получится без вспомогательного рандома Брезенхем с этим не согласен. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 10:47 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Alibek B. Имя пользователя1 боюсь, что равномерно смапить (0, 1, ... 9) в (2, 3, ..., 7) не получится без вспомогательного рандома Брезенхем с этим не согласен. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 11:24 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
В чем проблема равномерно распределить смасштабированный вещественный диапазон 2..7 в целочисленный диапазон 2..7? Эта задача уже полвека, как решена. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 11:47 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Нам не нужен весь диапазон. Давайте представим что у нас есть отрезок от 0 до 30. Почему 30? Потому что НОК(6,10) = 30 И на него падают короткие отрезки длиной в 3 целых единицы. Далее - накопительный алгоритм который режет эти отрезки на единицы и распределяет их на пятёрки. Накапливаем гистограмму пятерок и решаем когда высота слолбика настолько высока чтобы сгенерировать следующее целое случаное число уже в диапазоне целых от 1 до 6. Или от 2 до 7. Как физическая аналогия - 10 стаканов в которые падают капли жидкости. И распределяются по 6 стаканам через систему труб в соотвествии с справедливостью. По подобию коробок которые я описывал. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 12:15 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Потому что НОК(6,10) = 30 Это частный случай. А в общем случае используется алгоритм Брезенхема. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 13:08 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Ты имеешь в виду не-кратные m,n ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 13:23 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Любые. На каждой итерации остатки накопляются и добавляются к текущему значению, после чего сбрасываются. Если считать, что случайные данные распределены равномерно и количество итераций велико, то и итоговые данные будут распределены равномерно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 13:44 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Какие рекомендации по накоплению и сбросу? Сколько прибавлять? И через сколько сбросить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 13:52 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Alibek B. количество итераций велико, то и итоговые данные будут распределены равномерно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 14:07 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Нет. Было написано: "с таким же одинаковым шансом выпадения". Если целочисленный диапазон 0..9 (с равномерным выпадением) привести к целочисленному диапазону 2..7 (2+x/9*5, с распределением дробной части по алгоритму Брезенхема), то там тоже будет равномерное выпадение. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 14:30 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Alibek B. Нет. Было написано: "с таким же одинаковым шансом выпадения". Если целочисленный диапазон 0..9 (с равномерным выпадением) привести к целочисленному диапазону 2..7 (2+x/9*5, с распределением дробной части по алгоритму Брезенхема), то там тоже будет равномерное выпадение. Брезенхем - это итеративный алгоритм. Он бежит по оси X, или Y (где уклон меньше) и делает опциональн либо инкремент +1 для противоположной оси либо не делает ничего на этой итерации. Он фиксирует ошибку коррекции по Y на каждой итерации. В настоящий момент - неясно как применить Брезенхема без O(n). Тоесть без линейного пробегания по всему диапазону. Разумеется мы не всегда ищем O(1) но хотелось - бы не снизить зависимость от длины интервала. Ведь Хвост мог захотеть отображать дипазон MAX_LONG на какое-то число раза в полтора меньшее чем MAX_LONG. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 14:35 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
господа, "алгоритм Брезенхама" - это про попиксельное рисование? не понимаю, как он относится к сабжу. вот у нас равновероятное число из набора (0, 1, 2, 3, 4), или, например, k таких чисел, если вызвали рандомайзер несколько раз как его равномерно смапить на набор (0, 1, 2) ? покажите на примере ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 14:47 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1, алгоритм заменяет частые импульсы на редкие за счет периода ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 14:55 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 вот у нас равновероятное число из набора (0, 1, 2, 3, 4), или, например, k таких чисел, если вызвали рандомайзер несколько раз как его равномерно смапить на набор (0, 1, 2) ? покажите на примере Сходу поправка. Надо помнить о законе больших чисел и о некой кумулятивной памяти которой обладает наш черный ящик или алгоритм. Если наш алгоритм это некая функция с состоянием F тогда его смапить можно только без детерминизма. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 15:02 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Имя пользователя1 вот у нас равновероятное число из набора (0, 1, 2, 3, 4), или, например, k таких чисел, если вызвали рандомайзер несколько раз как его равномерно смапить на набор (0, 1, 2) ? покажите на примере Сходу поправка. Надо помнить о законе больших чисел и о некой кумулятивной памяти которой обладает наш черный ящик или алгоритм. Если наш алгоритм это некая функция с состоянием F тогда его смапить можно только без детерминизма. задача - уметь создать число, равновероятное из М вариантов., пользуясь специальным рандомайзером. 22078797 тут я собрал условие в кучу, по ответам ТСа на вопросы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 15:13 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T Если числа целые, то нам надо 10 равновероятных вариантов превратить в 6 (2,3,4,5,6,7). ИМХО Без запоминания чего-нибудь после расчета никак не получить равную вероятность. Как вариант накапливать сумму Код: plaintext 1. 2. 3. 4. ИМХО Этот вариант был нормальный, не надо никаких лишних rand(), модель кривая получилась, подвел кривоватый rand() из C++. Результат 6-ти запусков на C# Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. Надо бы на ГСЧ посерьезней затестить, но и тут уже видно что есть отклонения всего на 0.005%, но они тоже случайные, каждый раз разные, не в пользу какого-то конкретного элемента. PS Только для случаев N>=M ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 15:17 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T, в шарпах тоже линейный конгруэнтный? Или там другая реализация? Можешь глянуть? Еще есть мысль что тебе не стоит париться о качестве встроенного генератора в данной конкретной задаче. Вряд-ли мы получим что-то более качественное. В качестве краш-сравнения я предлагаю заменить random(10) на циклический счетчик i % 10 И предлагаю подумать вообще о чем рассуждал Хвост когда он хотел просто получить "маппинг". Скорее всего маппинга не существует а есть некое управляющее воздействие на конечный автомат (FSM) который периодически выдает (а может и не выдать!) очередное псевдо-случайное число как отклик на внешнее воздействие. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 15:35 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton В качестве краш-сравнения я предлагаю заменить random(10) на циклический счетчик i % 10 И предлагаю подумать вообще о чем рассуждал Хвост когда он хотел просто получить "маппинг". Счетчик не взлетел, случайность нужна Код: plaintext 1. 2. 3. 4. 5. Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 15:44 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=39926193&tid=1339820]: |
0ms |
get settings: |
10ms |
get forum list: |
14ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
161ms |
get topic data: |
11ms |
get forum data: |
3ms |
get page messages: |
57ms |
get tp. blocked users: |
1ms |
| others: | 15ms |
| total: | 280ms |

| 0 / 0 |
