Самый эффективный способ заполнения вектора целых чисел без дубликатов
Я пытаюсь заполнить вектор целых чисел с одним миллиардом случайных чисел. Единственное ограничение состоит в том, что в массиве не может быть дубликатов.
#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
using namespace std;
int main()
{
srand(time(NULL));
vector<int> container;
vector<int>::iterator i1;
for (int i=0;i<1000000000;i++) //a billion numbers
{
int number = rand() ;
i1 = find (container.begin(),container.end() , number );
if ( i1 != container.end() )
{
container.push_back(number);
}
}
}
Как можно улучшить мое решение? Это может быть что угодно, например, время или сложность пространства.
4 ответа
Ваше решение в его нынешнем виде будет невероятно медленным - сложность O(n^2)
, поэтому вы смотрите примерно на 10 ^ 18 «операций» за миллиард чисел. Это связано с тем, что вам нужно искать через вектор по мере его роста, чтобы увидеть, есть ли у вас дубликат, который пройдет через вектор (в среднем) (1 + 2 + ... + 999,999,999) / 2
раз в течение алгоритма.
Изменить: на самом деле это на самом деле немного хуже, потому что, поскольку вы генерируете больше чисел, вероятность того, что вы создадите то, что вы уже видели, увеличивается.
Я бы предложил следующее: поскольку на большинстве платформ int
все еще 4 байта, это все еще имеет максимальное значение бит более 2 миллиардов. Следовательно, создайте вектор с порядком первого миллиарда и используйте std::shuffle
. Это даст вам миллиард «случайных» значений с ограничением, что ничто не будет выбрано из верхнего диапазона [1e9, INT_MAX].
int main()
{
constexpr int num_values = 1000000000;
std::vector<int> rand_values(num_values);
std::mt19937 eng{std::random_device{}()};
for(int i = 0; i < num_values; ++i) {
rand_values[i] = i;
}
std::shuffle(rand_values.begin(), rand_values.end(), eng);
}
Я бы просто загрузил из файла заданных случайных чисел:
std::ifstream randFile("NameOfFileWithRandoms");
std::vector<int> randvalues(std::istream_iterator<int>(randFile),
std::istream_iterator<int>());
Возможным решением было бы сохранить значения в std :: unordered_set (std :: unordered_set будет хранить только уникальные значения), и как только ваш набор достигнет желаемого размера, скопируйте набор в вектор.
Это, вероятно, не самое эффективное решение, но оно подталкивает логику определения того, являются ли значения уникальными в стандартной библиотеке и упрощают собственный код.
srand(time(NULL));
auto uniqueSetOfValues = unordered_set<int>();
while(uniqueSetOfValues.size() < 1000000000)
{
// this will only insert unique values into the set
uniqueSetOfValues.insert(rand());
}
// start the vector with the correct size
auto uniqueVectorOfValues = vector<int>(uniqueSetOfValues.size());
// copy the set into the vector
copy(
begin(uniqueSetOfValues),
end(uniqueSetOfValues),
begin(uniqueVectorOfValues));
Согласно Yuushi, поскольку верхний предел для int равен 2 миллиардам, вы можете просто начать с 0 и продолжать добавлять 1 или 2 миллиарда раз. Таким образом, вы гарантированы
- уникальные номера
- , чтобы оставаться в пределах диапазона int
- Поиск или свопы
Так что-то вроде этого:
#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
using namespace std;
int main()
{
srand(time(NULL));
vector<int> container;
int number = 0; //Start with the number 0
for (int i=0;i<1000000000;i++) //a billion numbers
{
number += rand() & 1 + 1; //Keep right most bit, add 1 to get 1 or 2
container.push_back(number);
}
}
Я не эксперт на C ++, не стесняйтесь, если я ошибаюсь.