bearophile wrote:
Andrei Alexandrescu:
Given an array of length m, return a range that iterates the array in
random order such that the entire array is visited without going through
the same element more than once. Consume minimal amounts of memory and
time. Baseline solution: allocate an array of indices, shuffle it, then
follow indices stored in the array.
I have faced such problem more than once, and I have tried to solve it in
various ways. The faster solution was:
- create an array of m bits, set to zero
- Use a random generator to generate integer numbers in [0, m-1], if the
corresponding big is set, extract another random number, if it's not set then
set it, increment a counter, and return the array item that corresponds to the
bit.
- When about 90% of the bits is set, create an array with the remaining 10%
items of the array, shuffle them in place with the usual algorithm by Knuth,
and return them.
A quadratic algorithm applied to a fixed fraction of the input size will
still yield quadratic behavior. I understand how your solution may be
practical for a variety of needs, but if something is to be put in
Phobos, we need something principled.
Andrei
