ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Случайный конь в вакууме
25 сообщений из 223, страница 4 из 9
  4  все
Случайный конь в вакууме
    #39925810
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hVostt
Участник
Имя пользователя1
поскольку входное число равновероятное, то мы могли бы плюнуть на него и просто вернуть 2 + floor(random() * 6). Это число было бы равновероятным 2...7, только независимым от входа.


Ну не...
...
Рейтинг: 0 / 0
12.02.2020, 16:09
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925812
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton
Не надо тестить. Ты получишь Гауссово распределение если сделаешь таких штук 20 сложений.

На двух - незаметно. Но форма уже меняется.

Представь что мы с тобой играем в кости на сумму.

И я регулярно ставлю на то что сумма равна 6 или 7 и выигрываю.

Ты - можешь ставить на любое число и с большей вероятностью проиграешь.

Похоже ты не заметил что смещение каждый раз разное, это предыдущее значение
Код: plaintext
1.
static int sum = 0;


PS Имя sum не очень подходящее. В процессе творчества смысл переменной поменялся, а название осталось ((
 
Потестил на C# тоже работаетРезультат
Код: plaintext
 83886080: 0.1666 0.1666 0.1666 0.1666 0.1666 0.1667
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
static class Program {
	const int N = 10;
	const int M = 6;

	static Random rand = new Random();
	static int prev = 0;

	static int my_rand() {
		prev = (prev + rand.Next(N) + rand.Next(N)) % M;
		return prev;
	}

	static void Main(string[] args) {
		var arr = new int[M];
		for (int i = 1; i < 100000000; i++) {
			if ((i & 0xFFFFFF) == 0) {
			Console.Write($"\r {i}: ");
				foreach(var x in arr) Console.Write($"0.{(Int64)x * 10000 / i} ");
			}
			arr[my_rand()]++;
		}
	}
}

...
Рейтинг: 0 / 0
12.02.2020, 16:10
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925819
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
hVostt
Значение из входа можно брать несколько раз, чтобы получить одно для выхода.
то есть входное значение используется как генератор случайных целых чисел из фиксированного набора, и никакого другого генератора мы использовать не можем?
...
Рейтинг: 0 / 0
12.02.2020, 16:16
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925824
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Давай отвлечемся.

Вот линейный метод.

Код: plaintext
1.
2.
3.
4.
int rand(void){
  next = next * 1103515245 + 12345;
  return (unsigned int)(next/65536) % (RAND_MAX + 1);
}



Может нам посмотреть на него и поднять кое-какие идеи?
...
Рейтинг: 0 / 0
12.02.2020, 16:22
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925830
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Кстати периодическое вычитывание генератора rand.Next(N) + rand.Next(N) должно быть обоснованным.

Хвост нас не ограничивал. Но я себе понимаю так что мы должны экономно и по хозяйски отнестись
к работе полученных случайных чисел. Может они ценны для нас? Криптографически сложны?
Может они идут из другой галлактики с длинным лагом?
...
Рейтинг: 0 / 0
12.02.2020, 16:27
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925833
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hVostt
Участник
Имя пользователя1
hVostt
Значение из входа можно брать несколько раз, чтобы получить одно для выхода.
то есть входное значение используется как генератор случайных целых чисел из фиксированного набора, и никакого другого генератора мы использовать не можем?


Да, всё верно, в этом и смысл :)
...
Рейтинг: 0 / 0
12.02.2020, 16:30
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925838
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hVostt
Участник
Dima T
PS Имя sum не очень подходящее. В процессе творчества смысл переменной поменялся, а название осталось ((
 
Потестил на C# тоже работает


Я потестил на C#, на больших объёмах, входящий поток RNGCryptoServiceProvider:

Код: powershell
1.
2.
3.
4.
5.
6.
7.
    0  100009746 14,29%
    1  100000838 14,29%
    2   99993654 14,28%
    3   99992243 14,28%
    4  100008260 14,29%
    5   99992411 14,28%
    6  100002848 14,29%



Видим небольшие, но всё же отклонения, хм..
...
Рейтинг: 0 / 0
12.02.2020, 16:32
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925855
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
hVostt
Dima T
PS Имя sum не очень подходящее. В процессе творчества смысл переменной поменялся, а название осталось ((
 
Потестил на C# тоже работает


Я потестил на C#, на больших объёмах, входящий поток RNGCryptoServiceProvider:

Код: powershell
1.
2.
3.
4.
5.
6.
7.
    0  100009746 14,29%
    1  100000838 14,29%
    2   99993654 14,28%
    3   99992243 14,28%
    4  100008260 14,29%
    5   99992411 14,28%
    6  100002848 14,29%



Видим небольшие, но всё же отклонения, хм..
отклонения в количествах всегда будут, даже если рандомайзер идеальный. Надо, чтобы с ростом количества вариантов отклонения стремились к нулю.

ещё вопрос: надо ли, чтобы самый первый вызов нашей функции, используя предоставленный рандомайзер целого числа [0 ... N-1] не более k раз, мог дать равновероятное число [0 ... M-1] ?
...
Рейтинг: 0 / 0
12.02.2020, 16:46
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925856
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hVostt
Участник
mayton
Кстати периодическое вычитывание генератора rand.Next(N) + rand.Next(N) должно быть обоснованным.

Хвост нас не ограничивал. Но я себе понимаю так что мы должны экономно и по хозяйски отнестись
к работе полученных случайных чисел. Может они ценны для нас? Криптографически сложны?
Может они идут из другой галлактики с длинным лагом?


Ну тут нормально, я просто смысла пока не понимаю.
Почему 2 раза, а не 3, допустим.
И ещё погонял на разных диапазонах, и получаю в принципе достойное распределение, с отклонениями не больше, чем в исходном потоке.

Задача решена? ))
...
Рейтинг: 0 / 0
12.02.2020, 16:46
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925858
Фотография ну я
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ну я
Участник
hVostt
Прошу прощения за такое название топика )

Вот задача.

На вход поступают случайные числа, допустим от 0 до 9, шанс выпадения любого из чисел одинаковый.
Однако нам нужны только случайные числа от 2 до 7, с таким же одинаковым шансом выпадения.

Решение, пропускать числа, не попадающие в рейндж, не очень интересно.
Нужно именно преобразование.
Можно что-то сохранять между операциями.
Но в идеале чистое математическое преобразование нужно :)

Если значения от 0 до 9 каждое является случайным, то их диапазон не важен. И фильтр по вхождению в диапазон и есть правильное решение.

Что касается перекодирования из одного диапазона (10 значений) в другой (6 значений) то надо знать физику значений. Если физика - это случайность, то можно перекодировать как угодно, главное не 2 входных в 1 выходное. И потому можно вырезать любые 6 значений из входных и переобозвать в любом соответствии с выходными.

Так что два варианта - фильтр по диапазону и перекодирование отличаются лишь видом фильтра и наличием перекодирования.
...
Рейтинг: 0 / 0
12.02.2020, 16:47
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925859
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hVostt
Участник
Имя пользователя1
ещё вопрос: надо ли, чтобы самый первый вызов нашей функции, используя предоставленный рандомайзер целого числа [0 ... N-1] не более k раз, мог дать равновероятное число [0 ... M-1] ?


Конечно, либо надо первое число целенаправлено выкинуть.
В идеале, хотелось бы решение без состояния.

Но и состояние тоже подойдёт, если будет понятно, что оно позволяет решить задачу.
...
Рейтинг: 0 / 0
12.02.2020, 16:48
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925862
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hVostt
Участник
ну я
Если значения от 0 до 9 каждое является случайным, то их диапазон не важен. И фильтр по вхождению в диапазон и есть правильное решение.


С фильтром понятно. Но мы можем долго не получать следующего значения при сужении фильтра.


ну я
Что касается перекодирования из одного диапазона (10 значений) в другой (6 значений) то надо знать физику значений. Если физика - это случайность, то можно перекодировать как угодно, главное не 2 входных в 1 выходное. И потому можно вырезать любые 6 значений из входных и переобозвать в любом соответствии с выходными.


Брать остаток от деления, например?
...
Рейтинг: 0 / 0
12.02.2020, 16:56
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925866
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
hVostt
mayton
Кстати периодическое вычитывание генератора rand.Next(N) + rand.Next(N) должно быть обоснованным.

Хвост нас не ограничивал. Но я себе понимаю так что мы должны экономно и по хозяйски отнестись
к работе полученных случайных чисел. Может они ценны для нас? Криптографически сложны?
Может они идут из другой галлактики с длинным лагом?


Ну тут нормально, я просто смысла пока не понимаю.
Почему 2 раза, а не 3, допустим.
И ещё погонял на разных диапазонах, и получаю в принципе достойное распределение, с отклонениями не больше, чем в исходном потоке.

Задача решена? ))

Погоди. Я себе представил 10 маленких коробок. В которые падают шары. Равномерно. Линейно.
Эти 10 малых коробок стоят на 7 больших коробках так что общая длина - ровная.
У коробок - нет дна и верха. Но случайных шар. Попавший в 2 верхнюю коробку с разной
долей вероятности попадает в 2 либо 3 большую нижнюю коробку.

Вобщем такая вот физическая метафора.
...
Рейтинг: 0 / 0
12.02.2020, 17:03
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925869
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
hVostt,
число штук элементов большего диапазона,
равное остатку от целочисленного деления N\M должно просто скользить по меньшему диапазону.
Остальные мапятся по кругу строго 1:1
вот и всё.
...
Рейтинг: 0 / 0
12.02.2020, 17:05
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925871
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
hVostt
Имя пользователя1
ещё вопрос: надо ли, чтобы самый первый вызов нашей функции, используя предоставленный рандомайзер целого числа [0 ... N-1] не более k раз, мог дать равновероятное число [0 ... M-1] ?


Конечно, либо надо первое число целенаправлено выкинуть.
В идеале, хотелось бы решение без состояния.

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

очевидно, задачу легко решить напрямую и без состояний, только если N k делится на M, потому что k использований рандомайзера дают N k равновероятных исходов, которые надо равномерно раскидать на M групп.
...
Рейтинг: 0 / 0
12.02.2020, 17:06
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925884
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Имя пользователя1
но это в любом случае не будет идеальный рандом в математическом смысле.
точнее, рандом-то будет идеальный (если использовать идеальный рандомайзер), но равные шансы для [0 ... M-1] никак не сделать.

по сути, здесь любое состояние - это результат предыдущих вызовов рандомайзера, то есть опять всё те же N k исходов
...
Рейтинг: 0 / 0
12.02.2020, 17:18
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925887
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hVostt
Участник
mayton
Погоди. Я себе представил 10 маленких коробок. В которые падают шары. Равномерно. Линейно.
Эти 10 малых коробок стоят на 7 больших коробках так что общая длина - ровная.
У коробок - нет дна и верха. Но случайных шар. Попавший в 2 верхнюю коробку с разной
долей вероятности попадает в 2 либо 3 большую нижнюю коробку.

Вобщем такая вот физическая метафора.


Да, прекрасная метафора!
Хотелось бы формулу ))
...
Рейтинг: 0 / 0
12.02.2020, 17:21
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925895
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Вобщем всё просто.

Просто выдаем шар из той нижней коробки в которой их больше.

Только буфер надо.

Грубо говоря мой алгоритм - буферизированный. Например как только рухноло
с неба > 50 шаров - начинаем на каждый новый шар просто извлекать
из самой тяжелой коробки.

Profit.
...
Рейтинг: 0 / 0
12.02.2020, 17:28
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925899
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Dima T

Потестил на C# тоже работает

потестил на Java - результат противоречит математике и здравому смыслу

Задал N=2, M=1000

Понятно, что последовательность нифига не случайная, но вывод программы этого не показывает
...
Рейтинг: 0 / 0
12.02.2020, 17:33
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925901
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ну.. в малой коробке еще ест варианты.
1) Мы однозначно кидаем шар в большую.
2) Есть выбор кинуть чуть правее или чуть левее. Здесь не нужно случайный генератор.
Здесь нужно просто шары по кругу разбрасывать. чтоб 30% падало например в 1 большой
ящик и 40% в следующий большой.

Мою мысль легко понять если нарисовать коробки и падающие шары.
...
Рейтинг: 0 / 0
12.02.2020, 17:34
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925902
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
mayton,
то, что ты говоришь, можно понимать двояко.

Одно из пониманий дает возможность точно предсказать, какой следующий шар извлечется.
т.е. тогда на входе поток случайный у тебя окажется, а на выходе последовательно детерминированный.
заполнение выходного потока должно сохранять видимость случайности той же характеристики, какова случайность входного потока.
...
Рейтинг: 0 / 0
12.02.2020, 17:34
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925903
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да это добротность генератора. О которой хвост пока еще не говорил.
Линейность - будет. Добротность - ХЗ.
...
Рейтинг: 0 / 0
12.02.2020, 17:35
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925905
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
mayton

....начинаем на каждый новый шар просто извлекать
из самой тяжелой коробки.

Profit.

Нифига не понял.

Самое главное, не понимаю, что значит "самой тяжелой коробки"
может ли быть такое, что коробки одинаковые по весу?
если да, то фигня получится - даже матиматически доказывать не надо )))
...
Рейтинг: 0 / 0
12.02.2020, 17:36
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925908
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Фуух.
...
Рейтинг: 0 / 0
12.02.2020, 17:40
| Ответить | Цитировать | Написать  
Случайный конь в вакууме
    #39925909
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Leonid Kudryavtsev
Dima T

Потестил на C# тоже работает

потестил на Java - результат противоречит математике и здравому смыслу

Задал N=2, M=1000

Понятно, что последовательность нифига не случайная, но вывод программы этого не показывает
последовательность случайная, но для каждого результата нет равновероятности
...
Рейтинг: 0 / 0
12.02.2020, 17:42
| Ответить | Цитировать | Написать  
25 сообщений из 223, страница 4 из 9
  4  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Случайный конь в вакууме
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]