Управление памятью с небольшим объемом памяти: поиск и отслеживание дубликатов случайных возвращаемых значений функции

Question

Предположим, у меня есть функция, которая принимает 32-битное целое число и возвращает случайное 32-битное целое число.

Теперь я хочу посмотреть, сколько и какие повторяющиеся значения эта функция будет возвращать для всех возможных входных значений изОт 0 до 2 ^ 32-1.Я мог бы сделать это легко, если бы у меня было больше 4 ГБ свободного ОЗУ, но у меня не было более 1 ГБ ОЗУ.

Я попытался отобразить вычисленные значения на диске, используя файл 4 ГБ, где один байт представлял, сколько дублирует егополучил, но я заметил, что приблизительное время окончания будет 25 дней в будущем с моими скоростями HDD!(Я должен был использовать SSD, боясь сломать мой жесткий диск ...)

Итак, теперь следующим шагом является вычисление всего этого в оперативной памяти, а не использование диска вообще, но я побежал в стену, думая, какчтобы решить это элегантно.Единственный способ, о котором я мог подумать, - это зациклить (2 ^ 32) * (2 ^ 32) раза функцию, но это, очевидно, даже медленнее, чем мой метод HDD.

Теперь мне нужны некоторые неприятные идеичтобы ускорить это!

Редактировать: Функция на самом деле не является случайной функцией, но похожа на случайную функцию, но факт в том, что вам не нужно ничего знать о функции, ее нетпроблема здесь.Я хочу видеть все дубликаты своими невооруженными глазами, а не просто математически угадывать, сколько их может быть.Почему я это делаю?Из любопытства :) 1013 *

Answer 1

Чтобы проверить 2 ^ 32 возможных дубликатов, вам нужно всего 4 гигабита, что составляет 512 МБ, поскольку вам нужно только один бит на значение. Первый удар нулевого бита устанавливает его равным 1, и при каждом ударе 1 бита вы знаете, что у вас есть дубликат, и вы можете распечатать его или делать с ним все, что хотите.

т.е. Вы можете сделать что-то вроде этого:

int value = nextValue(...);
static int bits[] = new int[ 0x08000000 ]();

unsigned int idx = value >> 5, bit = 1 << ( value & 31 );
if( bits[ idx ] & bit )
   // duplicate
else
    bits[ idx ] |= bit;

в ответ на ваши комментарии

Да, помещать дубликаты в карту - хорошая идея, если их не слишком много и не так много разных дубликатов. Наихудший случай здесь - 2 ^ 31 записей, если каждое 2-е значение появляется ровно дважды. Если карта становится слишком большой для одновременного хранения в памяти, вы можете разделить ее, то есть разрешить только значения в определенном диапазоне, то есть четверть всего числового пространства. Это сделает карту только 1/4 размера всей карты, если дубликаты распределены довольно равномерно. Конечно, вам нужно будет запускать программу 4 раза в каждом квартале, чтобы найти все дубликаты.

Чтобы найти также 1-й дубликат, вы можете запустить его в два прохода: на первом проходе вы используете растровое изображение, чтобы найти дубликаты и поместить их в карту. На втором проходе вы пропускаете растровое изображение и добавляете значения в карту, если на карте уже есть запись, а значение еще не там.

Нет, нет веской причины для int над массивом int без знака. вы также можете использовать unsigned int, который на самом деле более уместен здесь.

Answer 2

Непростой вопрос: Почему? . чего ты пытаешься достичь?

Это какой-то эксперимент Монте-Карло?

Если нет, просто посмотрите алгоритм реализации вашего (P) RNG, и он точно скажет, каким будет распределение значений.

Посмотрите на Boost.Random , чтобы найти больше вариантов, чем вы можете себе представить, и он будет иметь, например uniform_int<> и генераторы переменных, которые могут ограничивать ваш выходной диапазон, в то же время обладая четко определенными гарантиями распределения значений по выходной области