7

С помощью гпсп 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
  • Если вам дан исчерпывающий ответ, отметьте его как верный (галка напротив выбранного ответа). 8 фев 2016 в 10:22

5 ответов 5

9

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

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

5
  • Идею с bitset хорошо понял, сейчас попробую реализовать. А вот с хэшами не очень. Для каждого генерируемого числа нужно подсчитать хэш и заполнить ими таблицу?
    – StayCool
    7 фев 2016 в 15:10
  • +1, но почему не std::unsorted_set?
    – VladD
    7 фев 2016 в 15:33
  • Да просто битовый вектор на 30 млн бит (3750000 байт) и цикл while (n < 800000) { v = newnumber(); if (такого еще нет) array[n++] = v;}
    – avp
    7 фев 2016 в 15:45
  • @VladD, я его и имел в виду под «хэш таблицей», просто написать явно забыл :)
    – ixSci
    7 фев 2016 в 17:24
  • @StayCool, обновил ответ
    – ixSci
    7 фев 2016 в 17:24
7

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

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

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

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

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

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

1
  • Отлично. А элемент битового массива лучше делать размером с машинное слово (32 или 64 бита). Ну и делить/брать остаток от размера элемента конечно. На 800к операций на платформе intel разница в скорости будет существенной. ru.stackoverflow.com/questions/476191/…
    – Mike
    7 фев 2016 в 16:15
5

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

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

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

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

2
  • 2
    Т. е. в более абстрактных терминах сгенерировать случайную перестановку из 1..30 000 000 (Фишер-Йейтс/Дуршенфельд, O(N)) и взять первые 800 000 её элементов. Если такое потребление памяти допустимо, проще подхода просто нет.
    – user181100
    7 фев 2016 в 15:06
  • 1
    Вы правы. Это намного проще чем всё остальное.
    – StayCool
    7 фев 2016 в 15:17
4

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

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

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

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

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

std::set<int> set;
std::vector<int> v;
v.reserve(800'000);
while (v.size() < 800'000) {
  auto x = distribution(prng);
  if (set.insert(x).second) v.push_back(x);
}
3
  • тут есть еще один подвох. Если человеку нужно не из 800 000 значений и именно из 30 000 000. Тогда как быть?
    – Saidolim
    7 фев 2016 в 15:13
  • да, значения должны быть именно от 0 до 30 миллионов. Это адреса байтов в файле размеров 30МБ. 30 мегабайт - 30 миллионов адресов. Если числа будут до 800тысяч то я запишу всю информацию в начало файла, что неприемлимо
    – StayCool
    7 фев 2016 в 15:19
  • @Abyx да вы правы, это функция поможет.
    – Saidolim
    7 фев 2016 в 15:53
1

Создать массив неповтворяющихся псевдослучайных чисел можно, например, так:
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 раз).

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.