Самый эффективный способ заполнения вектора целых чисел без дубликатов

Я пытаюсь заполнить вектор целых чисел с одним миллиардом случайных чисел. Единственное ограничение состоит в том, что в массиве не может быть дубликатов.

#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);
        }

    }    

}

Как можно улучшить мое решение? Это может быть что угодно, например, время или сложность пространства.

11 голосов | спросил Computernerd 10 FebruaryEurope/MoscowbMon, 10 Feb 2014 17:25:12 +0400000000pmMon, 10 Feb 2014 17:25:12 +040014 2014, 17:25:12

4 ответа


13

Ваше решение в его нынешнем виде будет невероятно медленным - сложность 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);
}
ответил Yuushi 10 FebruaryEurope/MoscowbMon, 10 Feb 2014 18:50:18 +0400000000pmMon, 10 Feb 2014 18:50:18 +040014 2014, 18:50:18
7

Я бы просто загрузил из файла заданных случайных чисел:

std::ifstream      randFile("NameOfFileWithRandoms");
std::vector<int>   randvalues(std::istream_iterator<int>(randFile),
                              std::istream_iterator<int>());
ответил Martin York 11 FebruaryEurope/MoscowbTue, 11 Feb 2014 04:07:21 +0400000000amTue, 11 Feb 2014 04:07:21 +040014 2014, 04:07:21
7

Возможным решением было бы сохранить значения в 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));
ответил YoungJohn 12 FebruaryEurope/MoscowbWed, 12 Feb 2014 00:34:56 +0400000000amWed, 12 Feb 2014 00:34:56 +040014 2014, 00:34:56
2

Согласно 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 ++, не стесняйтесь, если я ошибаюсь.

ответил konijn 12 FebruaryEurope/MoscowbWed, 12 Feb 2014 00:57:31 +0400000000amWed, 12 Feb 2014 00:57:31 +040014 2014, 00:57:31

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132