CODEWITHSUNDEEP
list
Harrison
Harrison

Reputation: 114

Ideal way to randomly traverse enormous list?

I have an enormous list of numbers (tens of millions), and I want to go through them in a random order without repeats

Is there an effective way to do this in C++, Java, Python?

Upvotes: 2

Views: 30

Answers (1)

Ken Y-N
Ken Y-N

Reputation: 15008

In C++, this might do:

std::list<T> foo;
std::vector<T *> bar(foo.size());
std::transform(foo.begin(), foo.end(), bar.begin(),
    [](T &a) -> T *
    { 
        return &a;
    });
std::random_shuffle(bar.begin(), bar.end());
for (auto &one_bar: bar)
    do_whatever(*one_bar);

Basically, create a vector of the same size and copy pointers to the original list into the vector, then shuffle the vector. Now you can step through and call do_whatever(T) on each element in a random order.

Furthermore, if you wish to eliminate duplicate values:

std::list<T> foo;
std::vector<T *> bar(foo.size());
std::transform(foo.begin(), foo.end(), bar.begin(),
    [](T &a) -> T *
    { 
        return &a;
    });
std::sort(bar.begin(), bar.end(),
    [](T *a, T *b) -> bool
    { 
        return *a > *b; 
    });
std::unique(bar.begin(), bar.end(),
    [](T *a, T *b) -> bool
    { 
        return *a == *b; 
    });
std::random_shuffle(bar.begin(), bar.end());
for (auto &one_bar: bar)
    do_whatever(*one_bar);

Assuming your class has these operators defined.

Upvotes: 2

Related Questions