Временная тема

[capzap]

Всё время стараюсь быть порядочным. Иногда и до такого доходит:

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

[Владимир Ситников]

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

Это шикарно. Поясню, что имею ввиду: capzap оскорбляет фразами "да у Вас комплексы", но при этом никак не подтверждает их. Capzap полностью игнорирует #74 и #113, в которых фраза "capzap, ты неправ" подтверждается конкретными примерами, а не абстрактным "свои срывы".

Цитируйте -- обсудим что было не так с моей стороны.

Жаль, что моё сообщение про "capzap сядет в лужу" удалили (ну, то, я где-то после 138 понял, что float 0..1 получится и capzap зря дискуссию разводит)

[rovki]

0) Для каких-то задач "генератор без повторений" может и потребоваться. Но слепо использовать его для всех задач -- нехорошо.

Если говорить чем "в целом" плох генератор, который выдаёт циклами без повторений, то
1) Плохо то, что он предсказуем. Например, если генерируем числа от 0 до 4, и 0, 1, 2, 3 уже выпали, то с вероятностью 100% выпадет число 4.
2) Плохо то, что нет эффективной реализации для произвольного диапазона. Нет от слова "совсем". Хорошую реализацию можно сделать через массив. Т.е. заполнить его числами от 0 до N, перемешать, и выдавать по одному. На ST это тривиально, а в ОЛ уже проблематично. Но, стоит понимать, что большие массивы держать в памяти и перемешивать всё равно время займёт.
3) Для частных случаев (некоторых N) можно сделать алгоритм не требующий массива, но он при этом будет выдавать лишь часть из возможных перестановок.

0) Не хорошо не приводить расчеты и аргументы ,а только фразы
1)Для меня равновероятно ,имхо -это когда каждое число может выпасть с равной вероятностью .для 1из 10 -10% ,а 1 из 1-100% ,естественно .Тоесть сначала вероятность у всех 10% ,потом 11.1 ,12.5 ,14.3, 16.7 ,20 ,25,33.3,50,100. по сравнению с начальной кучей .Тоесть вероятность растет у оставшихся по сравнению с общей кучей (10шт) ,но между собой они имеют равную вероятность быть выташенными ,что 3 из 3 ,что 5 из 5 каждый имеет равную вероятность .Меня не интересует вероятность оставшихся по сравнению с общей кучей ,меня интересует выроятность вытащенных значений (генерации) между собой .Да, цикл (куча) генерится вновь ,поэтому не 1из 1 остается ,а постоянно 1 из 10
2)использование массивов не представляется возможным при разности скоростей приема\передачи в 10раз ,ни какого стека не хватит ,он переполнится .

[capzap]

насколько я понимаю, раз Ваши комменты удаляют, значит не только у меня есть чувство, что Вы бестактны. Комплексы Ваши сами выходят наружу, это могут видеть все, будь Вы стократ грамотнее вех тут вместе взятых. Цитировать Ваше хамство я не буду, это Ваш удел цепляться ко всему. Я не вижу своей не правоты, до такой степени чтоб извинятся. А по поводу реала, вот когда повторите это для 32 битного слова, тогда и "кричите на весь мир" что поймали меня на не знании законов математики в плк. Кстати про лужу я продублировал если что и без Вашего коммента

[Владимир Ситников]

А по поводу реала, вот когда повторите это для 32 битного слова, тогда и "кричите на весь мир" что поймали меня на не знании законов математики в плк

Про 32бита я "кричу на весь мир", т.к. это один из примеров, где безоговорочно понятно, что вы неправы, а вы всё равно упираетесь и пытаетесь всячески оправдаться.

[capzap]

Про 32бита я "кричу на весь мир", т.к. это один из примеров, где безоговорочно понятно, что вы неправы, а вы всё равно упираетесь и пытаетесь всячески оправдаться.

Вы показывали работу ПК, а где скрин с реально работающего плк, обрабатывающий генерацию случайных 32-битных чисел, xorshift не проходит тест. Собственно чего это я, опять сейчас услышу, что законы математики везде одинаковы и кому то достаточно результатов на ПК
ЗЫ если побежали проверять на плк, чтоб не было фраз у меня вышло, договаривайте сколько добавили лишних символов в код, не говорю про строки, всё помещается может и в одну

[AI!]

Если говорить чем "в целом" плох генератор, который выдаёт циклами без повторений, то
1) Плохо то, что он предсказуем. Например, если генерируем числа от 0 до 4, и 0, 1, 2, 3 уже выпали, то с вероятностью 100% выпадет число 4.
2) Плохо то, что нет эффективной реализации для произвольного диапазона. Нет от слова "совсем".

А ничего что я уже написал сей макрос?
Который генерирует число от 0 до n без повторений, где n произвольное, меньше 1024.
А называется макрос rnd1024.

PS если есть желание, сам генератор можно легко поменять на ваш, а обработчик массива оставить мой.

[Владимир Ситников]

А ничего что я уже написал сей макрос?
Который генерирует число от 0 до n без повторений, где n произвольное, меньше 1024.
А называется макрос rnd1024.

Поясню, что я имею ввиду: по сути, задача "выборки n значений от 0 до n-1 без повторений" эквивалентна задаче "генерации случайной перестановки чисел от 0 до n-1" (по-английски это random shuffle)

1) Задача random shuffle обычно решается через массив: Тасование Фишера–Йетса
Если бы было можно просто "брать и генерировать очередное значение", то такой алгоритм наверняка бы упомянули в wikipedia. Но, нет, там про тасовку значений пишут, что всё-таки нужен массив, и при реализации Фишера–Йетса нужно быть внимательным, т.к. легко ошибиться и тасовка станет очень плохой.

Кстати, в OSCAT функция _ARRAY_SHUFFLE неправильная (там в 2 раза меньше перестановок чем надо, там плохой генератор и т.п.): https://github.com/simsum/oscat/blob...LE.EXP#L27-L34

Следующий момент -- для генерации перестановки большого количества элементов нужен ГСЧ очень высокого качества.
Например, из 1024 элементов есть 1024! перестановок. Для кодирования такого количества нужно log(1024!, 2) бит информации, т.е. примерно 8769 бит.
Это почти в 70 раз больше, чем внутреннее состояние xorshift128. Т.е. нужен либо ГСЧ с большим состоянием, либо нужно эффективно подмешивать энтропию "по ходу генерации". Да, тактование (выборка результата ГСЧ в случайный момент) является одним из таких действий, но тут большой вопрос сколько бит энтропии даёт подобное действо.

Получается, нужно крайне аккуратно следить за ГСЧ, иначе большая часть "возможных перестановок" вообще никогда не будет сгенерирована.


2) Есть ещё второй вариант -- pseudorandom permutation. Более известное как "симметричный шифр".
Например если есть алгоритм шифрования, шифрующий значения 0..63 с помощью ключа K, то "псевдослучайную перестановку" можно получить, если зашифровать значения 0, 1, 2 и т.п. последовательно. Т.е. Encrypt(0, K), Encrypt(1, K), и так далее. Разумеется, после каждого цикла нужно менять ключ шифрования и/или алгоритм шифрования.

Но тут 2 вопроса: во первых, ключ шифрования должен быть немалой длины (ну, чтобы хотя бы в теории закодировать все возможные n! перестановок), а во-вторых, на ум не приходят алгоритмы шифрования, у которых входной-выходной диапазон можно менять как параметр.
Ну, можно найти семейство алгоритмов, которые работают в числах 0...2ⁿ-1. В частности, 0..63, но если понадобится генератор "от 0 до 62 без повторений", то нужно будет ещё что-то придумывать.

Например, сработает такой алгоритм (но внутренний цикл while(nextValue>n) неудобно реализовывать на ОЛ):

int n=49; // хотим получить перестановки от 0 до n
int k=42; // ключ шифрования
for(int i=0; i < n; i++) {
  int nextValue = Encrypt(i, k); // Считаем, что Encrypt выдаёт значения от 0 до 63
  while(nextValue > n) { // Если оказалось 50..63, то значение не подходит -- шифруем его пока не попадёт в диапазон 0..49
    nextValue = Enrcypt(nextValue, k); // да, повторно шифруем значение, если оно выходит за диапазон
  }
  System.out.println("next value = " + nextValue);
}

Для справки, ln(64!)/ln(2) == 296. Т.е. для описания всех возможных 64! перестановок нужно почти 300 бит энтропии.

3) Идея с "давайте просто запоминать выпавшие числа, и если выпадет повторно, то бросать кость заново" понятна, но в ОЛ это убого, и приходится идти на уступки вида "если значение уже было, то возьмём просто следующее свободное". Это самое "следующее свободное" нарушает "случайность" перестановки -- т.е. генератор генерирует biased (как оно по-русски? смещённые? неравномерно распределённые?) последовательности.

[AI!]

Не понимаю зачем вся эта теория...
У меня делается просто, ка говорил rovki:

Мне нужно ,что бы было как в игре старинной -лото .Вытащил бочонок из кубышки и его уже нет в списке .После последнего бочонка снова тусуем мешок и продолжаем вытаскивать бочонки (но без повторения значений) .Количество бочонков в мешке- это диапазон случайных чисел .

При этом соседние "игры" запросто могут быть одинаковые, или одинаковыми могут быть последний бочонок предыдущей игры и первый следующей, но пока как бочонки не кончатся, повторений не будет!

PS раз вы дописали, то и я допишу... Мой макрос работает по алгоритму описанному в третьем пункте предыдущего сообщения.

[Владимир Ситников]

Не понимаю зачем вся эта теория...

Попробую ещё раз: что делает ваш алгоритм, если генератор возвращает число, которое "уже было в этой игре"? Я полагал, что возвращает "максимальное из оставшися" или "минимальное из оставшихся". Так?