Skip to content

[core] LoadRandomSequence is too heavyweight #5393

@orcmid

Description

@orcmid

Please, before submitting a new issue verify and check:

  • I tested it on latest raylib version from master branch
  • [X ] I checked there is no similar issue already reported
  • I checked the documentation on the wiki
  • [ X] My code has no errors or misuse of raylib

Issue description

LoadRandomSequence(count, min, max) has a very inefficient solution. It is also unfortunately defined. It
also uses a deficient uniform randomness generation. The line

        value = (rand()%(abs(max - min) + 1) + min);

should at least be replaced by use of the repaired GetRandomValue(min, max) resolved with issue #5374 and pull request #5392.

Going Farther (Speculative)

In addition, LoadRandomSequence has a rejection-of-duplicates method that ends up searching the already-chosen values to ensure the next-derived value is not a duplicate. It gets slower the larger count is and if count is too high, it can never terminate. The worst successful case is when count = max-min+1, and the larger that range is, the worse it gets.

Another way to look at LoadRandomSequence is to consider a deck of cards, numbered from min to max. with LoadRandomSequence() taken as shuffling that deck and dealing the first count cards. The next call shuffles the whole deck again.

It turns out there is a simple and very-effective technique to shuffle such a deck with one pass through it.

The tricky part is wanting to do this with a value[count] array, and not one with max-min+1 elements.

On the other hand, for reasonable max-min+1 values, having a full deck might not be so bad. That a larger-than-count deck might be returned would simply be sleight-of-hand. The caller would just be
assured that there are count values.

The difficulty is not knowing the use-case. An alternative would be to have a

void RandomDeckShuffle(int values[], int count);

where values[count] are shuffled.

This leaves initialization of the initial deck up to the application, and the adjustment by any min depends on the application as well. As compensation, we no longer care what the values are (so they could be in a [min, max] range), including duplicates when that's interesting (Canasta anyone?). And each shuffle happens in a nearly-linear o(count) instead of o(count^2) ) time based on using GetRandomValue(0,count-1) as repaired by #5392.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions