есть большое число 2^48, нужно получить всё множество его значений,
но не последовательно (как циклом for (i=0; i<2^48; i++...)),
а в хаотичной последовательности, как это можно сделать?
Здравствуйте, Аноним, Вы писали:
А>есть большое число 2^48, нужно получить всё множество его значений, А>но не последовательно (как циклом for (i=0; i<2^48; i++...)), А>а в хаотичной последовательности, как это можно сделать?
Здравствуйте, TheBeard, Вы писали:
TB>Здравствуйте, Аноним, Вы писали:
А>>есть большое число 2^48, нужно получить всё множество его значений, А>>но не последовательно (как циклом for (i=0; i<2^48; i++...)), А>>а в хаотичной последовательности, как это можно сделать?
TB>Например, использовать линейный конгруэнтный генератор псевдослучайных чисел с модулем 2^48.
Так не получится так как будут дубликаты. Это классическая задача тасования чисел
Есть линейный O(n) алгоритм генерации случайной последовательности K из интервала [1;N] без проверки на дубликаты. У Кнута есть доказательство суммы вероятностей. Алгоритм простецкий, на строк на 6.
Здравствуйте, PaulMinelly, Вы писали:
TB>>Например, использовать линейный конгруэнтный генератор псевдослучайных чисел с модулем 2^48.
PM>Так не получится так как будут дубликаты. Это классическая задача тасования чисел
У Кнута (том 2, если не ошибаюсь) как раз описано, как подбирать параметры LCM, чтобы сгенерированные числа не повторялись на всем периоде.
Здравствуйте, TheBeard, Вы писали:
TB>Здравствуйте, PaulMinelly, Вы писали:
TB>>>Например, использовать линейный конгруэнтный генератор псевдослучайных чисел с модулем 2^48.
PM>>Так не получится так как будут дубликаты. Это классическая задача тасования чисел
TB>У Кнута (том 2, если не ошибаюсь) как раз описано, как подбирать параметры LCM, чтобы сгенерированные числа не повторялись на всем периоде.
Точно, можно так сделать. ЛКГ с периодом 2^48. ИМХО задача будет сложнее чем тасование чисел на основе существующего ГСЧ = 6 строк кода и готово. Хотя конечно на любителя Вдруг в теоритических проблемах разбираться интереснее — тогда ЛКГ.
А>>>есть большое число 2^48, нужно получить всё множество его значений, А>>>но не последовательно (как циклом for (i=0; i<2^48; i++...)), А>>>а в хаотичной последовательности, как это можно сделать?
TB>>Например, использовать линейный конгруэнтный генератор псевдослучайных чисел с модулем 2^48.
PM>Так не получится так как будут дубликаты.
В первых же строчках приведённой статьи есть критерии выбора параметров ЛКГ для получения последовательности максимальной длины. Подобрать числа, соответствующие этим критериям элементарно, особенно для модулей вида 2^n. Другой вопрос — несколько качественным будет полученный ЛКГ — для серьёзных применений лучше не рисковать, а если просто нужна видимость "хаоса" — тогда сойдёт (достаточно проверить ЛКГ на отсутствие явных "узоров" при выводе случайных точек на плоскости).
PM>Это классическая задача тасования чисел PM>Есть линейный O(n) алгоритм генерации случайной последовательности K из интервала [1;N] без проверки на дубликаты. У Кнута есть доказательство суммы вероятностей. Алгоритм простецкий, на строк на 6.
Ага, вот только N у нас не слабое — 2^48(!)
У ЛКГ таких проблем нет — у него сложность O(1)
Здравствуйте, PaulMinelly, Вы писали:
PM>Здравствуйте, TheBeard, Вы писали:
TB>>Здравствуйте, PaulMinelly, Вы писали:
TB>>>>Например, использовать линейный конгруэнтный генератор псевдослучайных чисел с модулем 2^48.
PM>>>Так не получится так как будут дубликаты. Это классическая задача тасования чисел
TB>>У Кнута (том 2, если не ошибаюсь) как раз описано, как подбирать параметры LCM, чтобы сгенерированные числа не повторялись на всем периоде.
PM>Точно, можно так сделать. ЛКГ с периодом 2^48. ИМХО задача будет сложнее чем тасование чисел на основе существующего ГСЧ = 6 строк кода и готово. Хотя конечно на любителя Вдруг в теоритических проблемах разбираться интереснее — тогда ЛКГ.
Ну и как Вы тут случайное тасование делать собираетесь на 2^48 данных? Код в студию.
Здравствуйте, andy1618, Вы писали:
А>>>>есть большое число 2^48, нужно получить всё множество его значений, А>>>>но не последовательно (как циклом for (i=0; i<2^48; i++...)), А>>>>а в хаотичной последовательности, как это можно сделать?
TB>>>Например, использовать линейный конгруэнтный генератор псевдослучайных чисел с модулем 2^48.
PM>>Так не получится так как будут дубликаты.
A>В первых же строчках приведённой статьи есть критерии выбора параметров ЛКГ для получения последовательности максимальной длины. Подобрать числа, соответствующие этим критериям элементарно, особенно для модулей вида 2^n. Другой вопрос — несколько качественным будет полученный ЛКГ — для серьёзных применений лучше не рисковать, а если просто нужна видимость "хаоса" — тогда сойдёт (достаточно проверить ЛКГ на отсутствие явных "узоров" при выводе случайных точек на плоскости).
PM>>Это классическая задача тасования чисел PM>>Есть линейный O(n) алгоритм генерации случайной последовательности K из интервала [1;N] без проверки на дубликаты. У Кнута есть доказательство суммы вероятностей. Алгоритм простецкий, на строк на 6.
A>Ага, вот только N у нас не слабое — 2^48(!) A>У ЛКГ таких проблем нет — у него сложность O(1)
Сложность в этом смысле у них одинаковая. На одно число -- одна операция. В одном случае случайное число, в другом -- умножение + взятие по модулю (короче, сложность та же).
Вопрос в том, сколько ПАМЯТИ надо для такого перебора в каждом случае.
A>>В первых же строчках приведённой статьи есть критерии выбора параметров ЛКГ для получения последовательности максимальной длины. Подобрать числа, соответствующие этим критериям элементарно, особенно для модулей вида 2^n. Другой вопрос — несколько качественным будет полученный ЛКГ — для серьёзных применений лучше не рисковать, а если просто нужна видимость "хаоса" — тогда сойдёт (достаточно проверить ЛКГ на отсутствие явных "узоров" при выводе случайных точек на плоскости).
PM>>>Это классическая задача тасования чисел PM>>>Есть линейный O(n) алгоритм генерации случайной последовательности K из интервала [1;N] без проверки на дубликаты. У Кнута есть доказательство суммы вероятностей. Алгоритм простецкий, на строк на 6.
Поискал — судя по всему, это "Алгоритм P (Перемешивание)" из раздела 3.4.2 второго тома.
A>>Ага, вот только N у нас не слабое — 2^48(!) A>>У ЛКГ таких проблем нет — у него сложность O(1)
V>Сложность в этом смысле у них одинаковая. На одно число -- одна операция. В одном случае случайное число, в другом -- умножение + взятие по модулю (короче, сложность та же).
Для варианта с тасованием — ведь ещё надо исходный массив для тасования подготовить (хотя бы обнулить) — это ведь тоже O(n)
Впрочем, по-любому всё в память упирается
Здравствуйте, andy1618, Вы писали:
A>>>В первых же строчках приведённой статьи есть критерии выбора параметров ЛКГ для получения последовательности максимальной длины. Подобрать числа, соответствующие этим критериям элементарно, особенно для модулей вида 2^n. Другой вопрос — несколько качественным будет полученный ЛКГ — для серьёзных применений лучше не рисковать, а если просто нужна видимость "хаоса" — тогда сойдёт (достаточно проверить ЛКГ на отсутствие явных "узоров" при выводе случайных точек на плоскости).
PM>>>>Это классическая задача тасования чисел PM>>>>Есть линейный O(n) алгоритм генерации случайной последовательности K из интервала [1;N] без проверки на дубликаты. У Кнута есть доказательство суммы вероятностей. Алгоритм простецкий, на строк на 6.
A>Поискал — судя по всему, это "Алгоритм P (Перемешивание)" из раздела 3.4.2 второго тома.
A>>>Ага, вот только N у нас не слабое — 2^48(!) A>>>У ЛКГ таких проблем нет — у него сложность O(1)
V>>Сложность в этом смысле у них одинаковая. На одно число -- одна операция. В одном случае случайное число, в другом -- умножение + взятие по модулю (короче, сложность та же).
A>Для варианта с тасованием — ведь ещё надо исходный массив для тасования подготовить (хотя бы обнулить) — это ведь тоже O(n) A>Впрочем, по-любому всё в память упирается
Ну так и я про то же. Сложность у обоих алгоритмов линейная. В случае с тасованием надо на каждом шаге помнить, что еще не перетасовано, а в случае со случайным генератором -- не надо. Так что в первом случае проблемы с памятью, а во втором нет.
Можно подумать, что первый алгоритм выигрывает за счет того, что там берется "случайное" перемешивание. Но если так подумать, то это самое "случайное" перемешивание в конечном счете такая же детерминированная последовательность псевдослучайных чисел.
V>Ну так и я про то же. Сложность у обоих алгоритмов линейная.
Для нашей задачи (генерация k неповторяющихся случайных чисел в диапазоне от 1 до N) общая сложность будет отличаться — ЛКГ сможет работать сразу, а для генератора с тасованием придётся заранее потратить O(n) операций на инициализацию массива. При k << N разница будет существенная. Я вот это имел ввиду.
V>Можно подумать, что первый алгоритм выигрывает за счет того, что там берется "случайное" перемешивание. Но если так подумать, то это самое "случайное" перемешивание в конечном счете такая же детерминированная последовательность псевдослучайных чисел.
Ага. Кстати, у Кнута как раз этот момент расписан после алгоритма тасования — что если использовать для тасования обычный ГПСЧ с не очень большим периодом, то далеко не все возможные перестановки могут быть реализованы.
Здравствуйте, andy1618, Вы писали:
V>>Ну так и я про то же. Сложность у обоих алгоритмов линейная.
A>Для нашей задачи (генерация k неповторяющихся случайных чисел в диапазоне от 1 до N) общая сложность будет отличаться — ЛКГ сможет работать сразу, а для генератора с тасованием придётся заранее потратить O(n) операций на инициализацию массива. При k << N разница будет существенная. Я вот это имел ввиду.
Ну если надо генерить только k, то в случайной перетасовке тоже не обязательно генерить всю последовательность (тот же алгоритм Кнута позволяет сделать только k операций), а вот хранить придется по крайней мере 2k значений (т.к. при этом надо еще помнить, какие числа попали не на свои места в оставшейся "колоде"). В общем, все зависит от применения в конечном счете. Если генерируемые числа надо сразу использовать и забывать, то ГСЧ выигрывает с огромным преимуществом. Если же надо хранить всю последовательность, то так на так, хотя ГСЧ сделает это быстрее, и по крайней мере в два раза экономнее по памяти.
V>>Можно подумать, что первый алгоритм выигрывает за счет того, что там берется "случайное" перемешивание. Но если так подумать, то это самое "случайное" перемешивание в конечном счете такая же детерминированная последовательность псевдослучайных чисел.
A>Ага. Кстати, у Кнута как раз этот момент расписан после алгоритма тасования — что если использовать для тасования обычный ГПСЧ с не очень большим периодом, то далеко не все возможные перестановки могут быть реализованы.
V>>>Можно подумать, что первый алгоритм выигрывает за счет того, что там берется "случайное" перемешивание. Но если так подумать, то это самое "случайное" перемешивание в конечном счете такая же детерминированная последовательность псевдослучайных чисел.
A>>Ага. Кстати, у Кнута как раз этот момент расписан после алгоритма тасования — что если использовать для тасования обычный ГПСЧ с не очень большим периодом, то далеко не все возможные перестановки могут быть реализованы.
Немного про старую тему. Если ГПСЧ основан на ЛКГ с большим периодом то это будет тоже самое что использовать тасование за одним исключением что ГПСЧ не требует памяти O(n) при тасовании. Но с этим понятно, про это сказали. Сложность в том, чтобы найти такие коэфициенты ЛКГ чтобы его цикл был равен n, давал не коррелирующие значения и равномерные при этом. Для этого надо делать работу, проверять ЛКГ на гипотезы, смотреть корреляции. Работа не простая. Далее даже подобрав коэфициенты для периода, проверив на равномерность, мы получим только одну последовательность, а что если надо генерить много последовательностей? Проводить много тестов подбирая коэфициенты ЛКГ? При условии что это действительно трудоемкая работа, как я и расписал.
По второму моменту: Код я не привел сразу так как его не было рядом, но сейчас нашел в Кормене LOL, вот он код перемешивания за время O(n) и конечно память O(n) (Второе изд. русского Кормена с.153):
Randomize_In_Place(A)
n = length[A]
For i=1 to n
Swap(A[i], A[RANDOM(i,n)])
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[10]: обход чисел в хаотичной последовательности
Здравствуйте, PaulMinelly, Вы писали:
PM>Немного про старую тему. Если ГПСЧ основан на ЛКГ с большим периодом то это будет тоже самое что использовать тасование за одним исключением что ГПСЧ не требует памяти O(n) при тасовании. Но с этим понятно, про это сказали. Сложность в том, чтобы найти такие коэфициенты ЛКГ чтобы его цикл был равен n, давал не коррелирующие значения и равномерные при этом. Для этого надо делать работу, проверять ЛКГ на гипотезы, смотреть корреляции. Работа не простая. Далее даже подобрав коэфициенты для периода, проверив на равномерность, мы получим только одну последовательность, а что если надо генерить много последовательностей? Проводить много тестов подбирая коэфициенты ЛКГ? При условии что это действительно трудоемкая работа, как я и расписал.
Это все да. Еще, изменение n на 1 приводит к абсолютно новой задаче!
PM>По второму моменту: Код я не привел сразу так как его не было рядом, но сейчас нашел в Кормене LOL, вот он код перемешивания за время O(n) и конечно память O(n) (Второе изд. русского Кормена с.153): PM>
PM> Randomize_In_Place(A)
PM> n = length[A]
PM> For i=1 to n
PM> Swap(A[i], A[RANDOM(i,n)])
PM>
Здравствуйте, Аноним, Вы писали:
А>есть большое число 2^48, нужно получить всё множество его значений, А>но не последовательно (как циклом for (i=0; i<2^48; i++...)), А>а в хаотичной последовательности, как это можно сделать?
Найти блочный шифр с размером блока 48 бит, и зашифровать им последовательность чисел от 0 до 2^48 — 1
Re[11]: обход чисел в хаотичной последовательности
Здравствуйте, vadimcher, Вы писали:
V>Гу это как раз "Алгоритм Кнута".
Вообще это улучшенный алгоритм Фишера-Ятеса. Просто он приведен в книге у Кнута.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[12]: обход чисел в хаотичной последовательности
Здравствуйте, techgl, Вы писали:
T>Здравствуйте, vadimcher, Вы писали:
V>>Гу это как раз "Алгоритм Кнута". T>Вообще это улучшенный алгоритм Фишера-Ятеса. Просто он приведен в книге у Кнута.
Все новое -- хорошо забытое старое. Кнут в первой редакции книги не упомянул, что были люди до него, кто изобрел этот алгоритм, и есть подозрение, что он не знал об этом, ну т.е. был алгоритм, хорошо известный в его профессиональных кругах, безымянный, а потому куда он там уходит корнями -- никто и не пытался выяснить. Во второй редакции ему уже подсказали, кого стоит упомянуть. Но так как он популяризовал его, все говорят о "Knuth shuffle". Ну а теперь, как видите, многие на Кормена ссылаются.
А вот зайца кому, зайца-выбегайца?!
Re[13]: обход чисел в хаотичной последовательности
Здравствуйте, vadimcher, Вы писали:
V>Все новое -- хорошо забытое старое. Кнут в первой редакции книги не упомянул, что были люди до него, кто изобрел этот алгоритм, и есть подозрение, что он не знал об этом, ну т.е. был алгоритм, хорошо известный в его профессиональных кругах, безымянный, а потому куда он там уходит корнями -- никто и не пытался выяснить.
Вообще этот алгоритм, на сколько я понял, разрабатывался как чисто математический. Математики вообще любят карты, как объект для размышлений.
V>Во второй редакции ему уже подсказали, кого стоит упомянуть. Но так как он популяризовал его, все говорят о "Knuth shuffle". Ну а теперь, как видите, многие на Кормена ссылаются.
В CLR вообще авторство не указано, к сожалению.
В принципе такого эффекта несложно достичь, применив к последовательности от 0 до 2**48-1 обратимую функцию, дающую хорошее перемешивание (в криптографическом смысле этого слова). Тут уже предложили взять какой-нибудь блочный шифр. Это в общем-то правильная идея, только это а) сложно б) еще надо найти блочный шифр с блоком в 48 бит. Но можно сделать и проще. Я бы предложил такой вариант.
Идея тут такая, что умножение хорошо подмешивает младшие биты к старшим, а сдвиг вправо подмешивает старшие биты к младшим. Число взято от балды, важно только, что оно нечетное. Поскольку все операции обратимы, получаемая последовательность должна быть перестановкой чисел от 0 до 2**48-1.
And if you listen very hard the alg will come to you at last.
Здравствуйте, subdmitry, Вы писали:
S>В принципе такого эффекта несложно достичь, применив к последовательности от 0 до 2**48-1 обратимую функцию, дающую хорошее перемешивание (в криптографическом смысле этого слова). Тут уже предложили взять какой-нибудь блочный шифр. Это в общем-то правильная идея, только это а) сложно б) еще надо найти блочный шифр с блоком в 48 бит. Но можно сделать и проще. Я бы предложил такой вариант.
S>
S>Идея тут такая, что умножение хорошо подмешивает младшие биты к старшим, а сдвиг вправо подмешивает старшие биты к младшим. Число взято от балды, важно только, что оно нечетное. Поскольку все операции обратимы, получаемая последовательность должна быть перестановкой чисел от 0 до 2**48-1.
Кто сказал, что они обратимые? Операция & в конце обратимая? Где гарантия, что два числа не дадут один и тот же результат по модулю (1<<48)-1 после умножения?
Если даже это так, то насколько взятое наугад число дает хорошие характеристики получаемой случайной последовательности?
Вдруг в теоритических проблемах разбираться интереснее — тогда ЛКГ.
