Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Added shuffle functions #4

Merged
merged 1 commit into from Jul 30, 2022
Merged

Conversation

jmcwilliams403
Copy link
Contributor

based on Knuth shuffle. May need to add clarification in comments for where this algorithm came from.

Seeds are given as capital Long object wrappers to allow null seeds to indicate unseeded randomness.

based on Knuth shuffle. May need to add clarification in comments for where this algorithm came from.

Seeds are given as capital Long object wrappers to allow null seeds to indicate unseeded randomness.
@tommyettinger
Copy link
Owner

Hm... The implementation of the Knuth (AKA Fisher-Yates) shuffle algorithm looks solid, but instantiating new Random objects for each shuffle creates unexpected garbage. I'm also not certain how well Random mixes its seed, since it takes a 64-bit seed but only has a period of 2 to the 48, so if setSeed() doesn't adequately mix its input, identical shuffles with different Long seeds could be produced intentionally. My preference would be to take a Random as an argument, rather than one Long, which allows for subclasses of Random to be used (my juniper library is full of those subclasses, and also already has shuffling). Using a Random as a parameter also allows libGDX's RandomXS128 to be used.

Just within digital, there are a few static methods in Hasher that can generate pseudo-random bounded ints given a long seed. Using a sequential seed within the shuffle should work with any of randomize1Bounded, randomize2Bounded, or randomize3Bounded, but it might have detectable quirks/bias if you had several arrays of the same length, like arrayA, arrayB, and arrayC, and called shuffle(arrayA, 1L) and then shuffle(arrayB, 2L), shuffle(arrayC, 3L), etc. (changing the seed only by a small amount).

So, I'm thinking I won't merge this as-is, but I can merge it and then make the changes I have in mind. Mostly, I just want to avoid creating garbage references to temporary Random objects, but there are some other things I could add too -- shuffling rectangular 2D arrays so any element can be shuffled to any position is harder than it seems, and having some support for that could be nice.

@tommyettinger tommyettinger merged commit c3cbd18 into tommyettinger:main Jul 30, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

2 participants