Генерация без повторений. Как ускорить проверку на дубликаты?

#cpp #алгоритм

С помощью гпсп mt19937_64 генерирую 800 тысяч чисел в диапазоне от 0 до 30 миллионов.
Каждое генерируемое число должно быть исключительным, то есть с каждой генерацией приходится
сравнивать полученное число со всеми уже сгенерированными: 

unsigned array[800 000]; 

for (int i = 0; i < 800 000; i++)
{

  generate_again:      

  buffer = uid(rng);     // генерация в буфер

    for (int j = 0; j < i; j++) // сравниваем с каждым сгенерированным числом
    {
        if (buffer == array[j])
        {
            goto generate_again; // если такое число уже есть - переход к генерации
        }
    }
    array[i] = pepper; // если число исключительное - записываем в массив
}


Этот процесс занимает 16 минут. Есть ли способ ускорить этот процесс?
Спасибо.
    

Ответы

Ответ 1

Можно хранить полученные данные в дереве(std::set) — получите O(lgn) на вставку и
поиск или в hash таблице(std::unordered_set), где вставка тоже довольно дёшева(не помню
сколько точно), а поиск O(1). Это гарантировано ускорит процесс.

Если же оставить массив, то можно к нему добавить std::bitset на 30 000 000 бит.
Выставлять i-й бит, если i было сгенерировано, и, соответственно, проверять на каждой
итерации, не было ли оно сгенерировано. Это тоже должно ускорить процесс.


Ответ 2

прежде всего, уберите проверку проходом по массиву. Это отнимает линейное время от
числа чисел. Если у вас всего 30 млн вариантов и достаточно памяти, кладите их в массив
флагов. Это будет стоить примерно 30Мб. Ещё одна оптимизация по памяти - упаковка флагов
в битовую маску. Один флаг тогда занимает один бит. Такой подход будет стоить в 8 раз
дешевле. Имея 30Мб/8 (~4Мб) массив флагов, вы можете делать проверку существования
числа за константное время. Это значительно ускорит процесс. Но имеется ещё одна проблема:
будут коллизии при достаточно большом количестве уже полученных чисел.

доступ к флагу:

arr[i%8] & (1 << (i/8)) != 0


установка флага:

arr[i%8] |= (1 << (i/8))


Стоить отметить, что именно такой способ хранения информации о файле принят в фс
NTFS, да и в некоторых других тоже.


Ответ 3

800 000 / 30 000 000 = 2.6% это очень много. Могу предложить такой вариант:

Если вам нужно все 30 000 000 тогда алгоритм будет работать больше. Но если 100 000
хватить, тогда он будет работать быстрее. И так шаги


Создать массив А с 30 000 000 элементами
Заполнить массив Элементами от 0 до 30 000 000
Сделать цикл от K = 0 до 800 000 (можно и больше, даже 30 000 000, но не меньше)
в цикле берем рандомно число R = от K до 30 000 000
Меняем местами числа A[K] <=> A[R]
после завершении цикла берете первые 800 000 элементов.


6*. Если в шаг (3) делали больше чем 800 000 шагов цикла, то можно в пункт (6) начать
из другого индекса.


Ответ 4

800'000 чисел - это довольно мало. Их можно класть в std::set, тогда получится сортированный
набор уникальных чисел.

std::mt19937_64 prng(seeds);
std::uniform_int_distribution distribution(0, 30'000'000);
std::set set;
while (set.size() < 800'000)
  set.insert(distribution(prng));


Далее можно просто переложить эти числа в вектор и перемешать их:

std::vector v(begin(set), end(set));
std::shuffle(begin(v), end(v), prng);


Либо можно класть числа сразу и в set, и в вектор:

std::set set;
std::vector v;
v.reserve(800'000);
while (v.size() < 800'000) {
  auto x = distribution(prng);
  if (set.insert(x).second) v.push_back(x);
}


Ответ 5

Создать массив неповтворяющихся псевдослучайных чисел можно, например, так:
1. Записать в массив A H=2R=33 554 432, R=25 подряд идущих чисел.
2. Задать верхний предел диапазона индексов h = H-1 (или сколько надо -   например,
29999999) и его разрядность r = 25.
3. Сгенерировать очередное случайное число P в диапазоне 0..H-1.
4. Вычислить p = P >> (R-r);.
5. Если p > h, то перейти к п. 3.
6. Записать Ap в массив результата.
7. Присвоить Ap = Ah-1;.
8. Уменьшить диапазон индексов: h--;.
9. Если h == ((1 << (r-1)) - 1), то уменьшить разрядность: r--;.
10. Повторить пп. 3-9 до заполнения массива результата (800 000 раз).