On Friday, 26 February 2016 at 08:05:09 UTC, Joseph Rushton
Wakeling wrote:
On Thursday, 25 February 2016 at 17:27:25 UTC, Andrei
Alexandrescu wrote:
So we have
https://dlang.org/phobos/std_random.html#.randomCover which
needs to awkwardly allocate memory to keep track of the
portions of the array already covered.
Yes, this is definitely a standout in terms of being an
unpleasant solution. It means that you require o(N) memory
even when you're dealing with a lazily-evaluated range -- it
would probably be more efficient in practice to just write the
input into an array and do an in-place shuffle. :-(
This could be fixed by devising a PRNG that takes a given
period n and generates all numbers in [0, n) in exactly n
steps.
However, I've had difficulty finding such PRNGs. Most want the
maximum period possible so they're not concerned with a given
period. Any insights?
I'll try to see what I can find. This must be something that
other lazy/functional communities (Haskell, Clojure, ...) have
had to contend with.
Last few links:
https://www.quora.com/What-is-the-most-efficient-way-to-randomize-shuffle-a-linked-list?share=1
https://en.wikipedia.org/wiki/Gilbert%E2%80%93Shannon%E2%80%93Reeds_model
https://stackoverflow.com/questions/12167630/algorithm-for-shuffling-a-linked-list-in-n-log-n-time/27624106#27624106
