Is there a faster way, to get random numbers, from a specific pool of numbers

Question

im looking for a faster method, which allows me, to get a random number from a certain pool of numbers which are stored in an array.

I'll need the method multiple times, and the current method is terribly slowing down the code.

#include <cstdlib>
#include <ctime>

int main()
{      
    const int size = 8;
    int numberArray[size] = { 0, 0, 3, 4, 0, 6, 7, 0 };
    srand(time(0));

    int rndIndex;
    int rndNumber;
    do 
    {
        rndIndex = rand() % size;
        rndNumber = numberArray[rndIndex];
    } while (rndNumber <= 0);
}

I like to get a random number from the array, except the random number is less than 0

I'm programming the knight's tour (https://en.wikipedia.org/wiki/Knight%27s_tour), this array represents the possible moves for the knight, the 0 represents an move, which is not possible, because of the edge, or the field is already passed — Modgudr, Jul 26 '19 at 05:44
If the code does nothing when you get a zero the first thing I would do is to create a smaller array without zero and then simply use rnd `Index = rand() % size_without_zero` — Picaud Vincent, Jul 26 '19 at 06:03
Of the predefined random number generators from [](https://en.cppreference.com/w/cpp/numeric/random), the mersenne twister engine `mt19937` is blazingly fast and a very high quality PRNG. — Jesper Juhl, Jul 26 '19 at 06:34
I profiled your code compiled with a recent MSVC as of the time of this writing, testing an unrealistic million calls to a function using your method and yet it used up less than 1% of total CPU time on even my i7-4600U. I suspect your issue may really be an outdated compiler(likely including a slower rand() implementation). Try updating your compiler. — Koby Duck, Jul 26 '19 at 07:07

score 1 · Answer 1 · answered Jul 26 '19 at 07:29

If I understand correctly, then you want to repeatedly pick a non-zero number from numberArray, but the numbers in the array changes after each pick (because the knight moves to a different square with different move options). But your current solution goes slower and slower as the knight progresses, because there are more and more zeroes in the move array, making you have to loop more times before a non-zero value is picked.

One solution to this problem, that I see, is to first count the number of non-zero elements in the array. Then do a random selection (n) up to that number, and finally select the n'th non-zero number in the array. Quick code showing the idea here:

const int size = 8;
int numberArray[size] = { 0, 0, 3, 4, 0, 6, 7, 0 };
srand(time(0));

int numNonZero = 0;
for (int i = 0; i < size;++i) {
    if (numberArray[i] > 0)
        ++numNonZero;
}

int selectionNum;
int rndNumber;

selectionNum = rand() % numNonZero;

for (int i = 0; true; ++i) {
    rndNumber = numberArray[i];
    if (rndNumber > 0 && selectionNum-- == 0)
        break;
}

This trades a random number of loops, with a rand() draw in each, for two loops of max 8 elements and a single rand() draw.

BY THE WAY!

Since I am already typing this up, I am just going to mention that rand() % X is an outdated way of generating random numbers (0 to X-1), and that STL has a better way of doing it today.

A better way would be to do something like this:

const int size = 8;
int numberArray[size] = { 0, 0, 3, 4, 0, 6, 7, 0 };
std::random_device rd;
std::mt19937 mt(rd());  // initialize the random generator

int numNonZero = 0;
for (int i = 0; i < size;++i) {
    if (numberArray[i] > 0)
        ++numNonZero;
}

int selectionNum;
int rndNumber;

std::uniform_int_distribution<int> distribution(0, numNonZero - 1); // Set the distribution: 0 to numNonZero-1, both inclusive
selectionNum = distribution(mt);  // Generate random number in the selected range

for (int i = 0; true; ++i) {
    rndNumber = numberArray[i];
    if (rndNumber > 0 && selectionNum-- == 0)
        break;
}

You can read more here: http://www.cplusplus.com/reference/random/ or here Generate random numbers using C++11 random library

I thought as well to proceed the array to remove the zeroes, but the problem is you have to process through whole array at least once. Because you don't know until the array has been processed, how much zeroes you have. And the duration of the processing is equivalent of the OP's code. See [this benchmark](http://quick-bench.com/wXw6SCFUMZCraHcZFBl6r2f2McI) — Guillaume D, Jul 26 '19 at 08:27
“A better way...”: that depends on your definition of “better”. Look at the hoops you had to jump through to avoid using rand! — TonyK, Jul 26 '19 at 09:22

Is there a faster way, to get random numbers, from a specific pool of numbers

1 Answers1