powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Случайный конь в вакууме
25 сообщений из 223, страница 6 из 9
Случайный конь в вакууме
    #39926035
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В целом мысль понял и даже, частично! согласен. Только я бы упростил формулировку

Есть N^K возможных значений, где K это кол-во данных/циферек на входе, нужно разложить по M равным кучкам....

Почему "частично", т.к. у автора поток данных скорее бесконечный и "Если кругов дофига, то имеет ли значение для задачи, насколько нек-рые из меньших цифр будут менее вероятны? на мизер ведь, и этот мизер с каждым кругом будет уменьшаться."

Во вторых, все же остается не очень понятно, почему мы обязаны раскладывать все возможные значения по M равным кучкам. Предположим, что у нас есть M кучек, куда нам нужно разложить "ровно", +/dev/null куда мы можем выкинуть то, что не разложилось.

Как я представлял бы данную задачу __практически__ (мы же в форуме программирование):
Есть аппаратный генератор случайных чисел от 0..N (я бы для упрощения предложил 0 / 1), нужен алгоритм генерации числа 0..M максимально экономно использующий входные данные.

Попытаюсь объяснить свою идея с /dev/null:
Предположим на входе поток битов, нам нужно набрать байты. Пусть мы банально склееваем биты друг с другом.
Понятно, что если на входе пришло 15 битов (k=15), мы можем склееть только один байт, а 7 оставшихся битов уйдут в /dev/null. Станет ли от этого первый получившися байт хуже "вероятным"?

С точки зрения делетанта, сидящего на окладе ниже рыночного )))
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926037
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
все же остается не очень понятно, почему мы обязаны раскладывать все возможные значения по M равным кучкам. Предположим, что у нас есть M кучек, куда нам нужно разложить "ровно", +/dev/null куда мы можем выкинуть то, что не разложилось.
пожелание автора топика.
22078105
авторРешение, пропускать числа, не попадающие в рейндж, не очень интересно.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926039
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
Почему "частично", т.к. у автора поток данных скорее бесконечный и "Если кругов дофига, то имеет ли значение для задачи, насколько нек-рые из меньших цифр будут менее вероятны? на мизер ведь, и этот мизер с каждым кругом будет уменьшаться."
но требуемая функция не может сколько угодно забирать данные из потока. Она должна отработать за конечное время.
потому, можно сделать только приблизительную равновероятность. Некоторые кучки получат на единицу больше, их вероятность будет на 1/N k выше чем у "маленьких кучек", и увеличивая k, мы сокращаем разницу
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926046
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1,

то, что работает с rand, это не функция, в формальном смысле, и не может ею быть.
Это процесс, вычислительный.
Процессу принципиально разрешается работать бесконечно.

PS
Красиво рассуждаешь.
Чувствуется образование.
Совсем не частый для форума случай
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926079
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
Leonid Kudryavtsev
Почему "частично", т.к. у автора поток данных скорее бесконечный и "Если кругов дофига, то имеет ли значение для задачи, насколько нек-рые из меньших цифр будут менее вероятны? на мизер ведь, и этот мизер с каждым кругом будет уменьшаться."
но требуемая функция не может сколько угодно забирать данные из потока. Она должна отработать за конечное время.
потому, можно сделать только приблизительную равновероятность. Некоторые кучки получат на единицу больше, их вероятность будет на 1/N k выше чем у "маленьких кучек", и увеличивая k, мы сокращаем разницу


Вроде даже и согласен, но "не убедили"

Даже сел писать код, но дошел до того, о чем говорил mayton 22078740
остаток получается в виде дроби, и что с ним потом делать (как применить операцию остаток от деления к дроби), в 3-и часа ночи после работы как-то сильно заумно )))
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926096
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926097
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby
то, что работает с rand, это не функция, в формальном смысле, и не может ею быть.
Это процесс, вычислительный.
Процессу принципиально разрешается работать бесконечно.
согласен.
только на момент первого (да и любого по счету) результата рандомайзер будет вызван конечное количество раз.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926148
Alibek B
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
боюсь, что равномерно смапить (0, 1, ... 9) в (2, 3, ..., 7) не получится без вспомогательного рандома

Брезенхем с этим не согласен.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926165
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Alibek B.
Имя пользователя1
боюсь, что равномерно смапить (0, 1, ... 9) в (2, 3, ..., 7) не получится без вспомогательного рандома

Брезенхем с этим не согласен.
?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926179
Alibek B
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В чем проблема равномерно распределить смасштабированный вещественный диапазон 2..7 в целочисленный диапазон 2..7?
Эта задача уже полвека, как решена.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926193
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Нам не нужен весь диапазон. Давайте представим что у нас есть отрезок от 0 до 30. Почему 30? Потому что НОК(6,10) = 30

И на него падают короткие отрезки длиной в 3 целых единицы. Далее - накопительный алгоритм
который режет эти отрезки на единицы и распределяет их на пятёрки.

Накапливаем гистограмму пятерок и решаем когда высота слолбика настолько высока чтобы сгенерировать
следующее целое случаное число уже в диапазоне целых от 1 до 6. Или от 2 до 7.

Как физическая аналогия - 10 стаканов в которые падают капли жидкости.
И распределяются по 6 стаканам через систему труб в соотвествии с справедливостью.

По подобию коробок которые я описывал.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926215
Alibek B
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Потому что НОК(6,10) = 30

Это частный случай.
А в общем случае используется алгоритм Брезенхема.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926225
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ты имеешь в виду не-кратные m,n
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926244
Alibek B
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Любые. На каждой итерации остатки накопляются и добавляются к текущему значению, после чего сбрасываются.
Если считать, что случайные данные распределены равномерно и количество итераций велико, то и итоговые данные будут распределены равномерно.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926249
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Какие рекомендации по накоплению и сбросу?

Сколько прибавлять? И через сколько сбросить.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926263
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Alibek B.
количество итераций велико, то и итоговые данные будут распределены равномерно.
ставилась задача не о равномерном распределении на множестве итераций, а о равновероятности каждого конкретного результата
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926270
Alibek B
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Нет. Было написано: "с таким же одинаковым шансом выпадения".
Если целочисленный диапазон 0..9 (с равномерным выпадением) привести к целочисленному диапазону 2..7 (2+x/9*5, с распределением дробной части по алгоритму Брезенхема), то там тоже будет равномерное выпадение.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926272
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Alibek B.
Нет. Было написано: "с таким же одинаковым шансом выпадения".
Если целочисленный диапазон 0..9 (с равномерным выпадением) привести к целочисленному диапазону 2..7 (2+x/9*5, с распределением дробной части по алгоритму Брезенхема), то там тоже будет равномерное выпадение.

Брезенхем - это итеративный алгоритм. Он бежит по оси X, или Y (где уклон меньше)
и делает опциональн либо инкремент +1 для противоположной оси либо не делает
ничего на этой итерации. Он фиксирует ошибку коррекции по Y на каждой итерации.

В настоящий момент - неясно как применить Брезенхема без O(n). Тоесть без линейного
пробегания по всему диапазону.

Разумеется мы не всегда ищем O(1) но хотелось - бы не снизить зависимость от длины интервала.

Ведь Хвост мог захотеть отображать дипазон MAX_LONG на какое-то число раза в полтора меньшее чем MAX_LONG.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926279
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
господа, "алгоритм Брезенхама" - это про попиксельное рисование?

не понимаю, как он относится к сабжу.

вот у нас равновероятное число из набора (0, 1, 2, 3, 4), или, например, k таких чисел, если вызвали рандомайзер несколько раз
как его равномерно смапить на набор (0, 1, 2) ?
покажите на примере
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926284
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1,

алгоритм заменяет частые импульсы на редкие за счет периода
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926286
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1

вот у нас равновероятное число из набора (0, 1, 2, 3, 4), или, например, k таких чисел, если вызвали рандомайзер несколько раз
как его равномерно смапить на набор (0, 1, 2) ?
покажите на примере

Сходу поправка. Надо помнить о законе больших чисел и о некой кумулятивной памяти которой обладает
наш черный ящик или алгоритм. Если наш алгоритм это некая функция с состоянием F тогда его смапить
можно только без детерминизма.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926289
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Имя пользователя1

вот у нас равновероятное число из набора (0, 1, 2, 3, 4), или, например, k таких чисел, если вызвали рандомайзер несколько раз
как его равномерно смапить на набор (0, 1, 2) ?
покажите на примере

Сходу поправка. Надо помнить о законе больших чисел и о некой кумулятивной памяти которой обладает
наш черный ящик или алгоритм. Если наш алгоритм это некая функция с состоянием F тогда его смапить
можно только без детерминизма.
закон больших чисел - следствие вероятностей. Не надо от него плясать.

задача - уметь создать число, равновероятное из М вариантов., пользуясь специальным рандомайзером.

22078797 тут я собрал условие в кучу, по ответам ТСа на вопросы.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926291
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
Если числа целые, то нам надо 10 равновероятных вариантов превратить в 6 (2,3,4,5,6,7).

ИМХО Без запоминания чего-нибудь после расчета никак не получить равную вероятность.

Как вариант накапливать сумму
Код: plaintext
1.
2.
3.
4.
thread_local int sum = 0;
sum += rand();
while (sum > 5) sum -= 6;
return sum + 2;


ИМХО Этот вариант был нормальный, не надо никаких лишних 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.
0: 99995522     16,6659%
1: 99998844     16,6665%
2: 99998109     16,6664%
3: 99988758     16,6648%
4: 100003266    16,6672%
5: 100015500    16,6693%

0: 100005194    16,6675%
1: 99993056     16,6655%
2: 100007572    16,6679%
3: 99989516     16,6649%
4: 99998428     16,6664%
5: 100006233    16,6677%

0: 99986272     16,6644%
1: 100012836    16,6688%
2: 100022654    16,6704%
3: 100000588    16,6668%
4: 99980680     16,6634%
5: 99996969     16,6662%

0: 99998352     16,6664%
1: 99997879     16,6663%
2: 99979625     16,6633%
3: 99996773     16,6661%
4: 100013016    16,6688%
5: 100014354    16,6691%

0: 99990543     16,6651%
1: 100008784    16,6681%
2: 99998934     16,6665%
3: 100013355    16,6689%
4: 99990095     16,6650%
5: 99998288     16,6664%

0: 99994203     16,6657%
1: 100024501    16,6708%
2: 99991417     16,6652%
3: 99992826     16,6655%
4: 99994362     16,6657%
5: 100002690    16,6671%

Код: 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.
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)) % M;
		return prev;
	}

	static void Main(string[] args) {
		var arr = new int[M];
		for (int i = 1; i < 100000000*M; i++) {
			if ((i & 0xFFFFF) == 0) {
				int min = 100000000, max = 0;
				foreach(var x in arr) {
					if(x < min) min = x;
					if(x > max) max = x;
				}
				Console.Write($"\r {i}  min:{min}  max:{max} delta:{((double)max/min-1)*100:N4}%");
			}
			arr[my_rand()]++;
		}
		Console.Write("\r                                                                \r");
		for(int i = 0; i < arr.Length; i++) {
			Console.WriteLine($"{i}: {arr[i]}\t{(double)arr[i]/1000000/M:N4}%");
		}
	}
}


Надо бы на ГСЧ посерьезней затестить, но и тут уже видно что есть отклонения всего на 0.005%, но они тоже случайные, каждый раз разные, не в пользу какого-то конкретного элемента.

PS Только для случаев N>=M
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926298
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T, в шарпах тоже линейный конгруэнтный? Или там другая реализация? Можешь глянуть?

Еще есть мысль что тебе не стоит париться о качестве встроенного генератора в данной конкретной задаче.
Вряд-ли мы получим что-то более качественное.

В качестве краш-сравнения я предлагаю заменить random(10) на циклический счетчик i % 10
И предлагаю подумать вообще о чем рассуждал Хвост когда он хотел просто получить "маппинг".

Скорее всего маппинга не существует а есть некое управляющее воздействие на конечный автомат
(FSM) который периодически выдает (а может и не выдать!) очередное псевдо-случайное число
как отклик на внешнее воздействие.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926305
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
В качестве краш-сравнения я предлагаю заменить random(10) на циклический счетчик i % 10
И предлагаю подумать вообще о чем рассуждал Хвост когда он хотел просто получить "маппинг".

Счетчик не взлетел, случайность нужна
Код: plaintext
1.
2.
3.
4.
5.
0: 209999999    35,0000%
1: 90000000     15,0000%
2: 0    0,0000%
3: 210000000    35,0000%
4: 90000000     15,0000%
5: 0    0,0000%
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
	static int prev = 0;
	static int rnd = 0;

	static int my_rand() {
		//prev = (prev + rand.Next(N)) % M;
		rnd++;
		if(rnd >= N) rnd = 0;
		prev = (prev + rnd) % M;
		return prev;
	}
...
Рейтинг: 0 / 0
25 сообщений из 223, страница 6 из 9
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Случайный конь в вакууме
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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