CODEWITHSUNDEEP
c++arraysperformancerandom
Geobor
Geobor

Reputation: 3

Iterate through an array randomly but fast

I have a 2d array that I need to iterate through randomly. This is part of an update loop in a little simulation, so it runs about 200 times a second. Currently I am achieving this by creating a array of the appropriate size, filling it with a range, and shuffling it to use to subscript my other arrays.

std::array<int, 250> nums;
std::iota(nums.begin(), nums.end(), 0);

timer += fElapsedTime;
if (timer >= 0.005f)
{
    std::shuffle(nums.begin(), nums.end(), engine);

    for (int xi : nums)
    {
        std::shuffle(nums.begin(), nums.end(), engine);

        for (int yi : nums)
        {
            // use xi and yi as array subscript and do stuff
        }
    }

    timer = 0.0f;
}

The issue with this solution is that is is really slow. Just removing the std::shuffles increases the fps by almost 2.5x, so the entire program logic is almost insignificant compared to just these shuffles.

Is there some type of code that would allow me to generate a fixed range (0 - 249) of non-repeating randomly generated ints that I could either use directly or write to an array and then iterate over?

Upvotes: 0

Views: 191

Answers (1)

doug
doug

Reputation: 4299

You should shuffle the entire matrix rather than going through one row/column at a time. This should work pretty fast. It's 125k and should be reasonably cache friendly.

constexpr int N = 250;
std::array<uint16_t, N* N> nums;
std::iota(nums.begin(), nums.end(), 0);
std::shuffle(nums.begin(), nums.end(), engine);

for (auto x : nums)
{
    auto xi = x / N;
    auto yi = x % N;
    // Do Stuff indexed on x and y
}

Upvotes: 3

Related Questions