Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I am trying to populate a vector of integers with one billion random number. The only constraint is that there can be no duplicates in the array.

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

    }    

}

How can my solution be improved on? It can be anything, like time taken or space complexity.

share|improve this question
    
1) rand sucks. On some machines there might not even be enough distinct values for rand to return. RAND_MAX may be as small as 2^15. 2) A hash set based approach would be much faster. Alternatively you could also use a sorting or tree based approach, but those tend to be slower than hashing. –  CodesInChaos Feb 10 at 14:26
add comment

4 Answers

Your solution as it stands currently is going to be incredibly slow - it's complexity is O(n^2), so you're looking at roughly 10^18 "operations" for a billion numbers. This is because you need to search through the vector as it grows to see if you have a duplicate, which will go through the vector (on average) (1 + 2 + ... + 999,999,999) / 2 times over the course of the algorithm.

Edit: In fact, it's actually slightly worse than this, since as you generate more numbers, the probability that you generate something you've already "seen" increases.

I'd suggest the following: since an int on most platforms is still 4 bytes, this still has a maximum value of a bit over 2 billion. Hence create a vector with the first billion values in order, and use std::shuffle. This will give you a billion "random" values, with the constraint that nothing will be selected from the upper range [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);
}
share|improve this answer
    
In the event that OP wishes to use truly random numbers, this approach will not work. The constraint of the domain of values doesn't seem reasonable in the general case. –  Emily L. Feb 17 at 23:24
add comment

I would just load from a file of predetermined random numbers:

std::ifstream      randFile("NameOfFileWithRandoms");
std::vector<int>   randvalues(std::istream_iterator<int>(randFile),
                              std::istream_iterator<int>());
share|improve this answer
add comment

A possible solution would be to store the values in a std::unordered_set (std::unordered_set will only store unique values), and once your set reaches the desired size, to copy the set into a vector.

This is probably not the most efficient solution but it would push the logic of determining if values are unique into the standard library and simplify your own code.

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));
share|improve this answer
1  
You might even be able to use std::move instead of std::copy since you probably don't need to keep the unordered_set around. –  YoungJohn Feb 11 at 20:36
    
This has amortized O(n) time complexity. I approve. :) –  Emily L. Feb 17 at 23:27
add comment

As per Yuushi, since the upper limit for int is 2 billion, you might just want to start with 0 and keep adding 1 or 2 a billion times. This way you are guaranteed

  • unique numbers
  • to stay within the int range
  • no lookups or swaps

So something like this:

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

I am not a C++ expert, feel free to burninate if I am wrong.

share|improve this answer
1  
-1 you have way too much rep to be a regular javascript bunny. (nah, kidding) –  Mat's Mug Feb 12 at 1:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.