Steven Schveighoffer wrote:
"Denis Koroskin" wrote
On Thu, 12 Feb 2009 15:14:34 +0300, Steve Schveighoffer
On Thu, 12 Feb 2009 14:41:26 +0300, Denis Koroskin wrote:
On Thu, 12 Feb 2009 07:46:31 +0300, Andrei Alexandrescu
<[email protected]> wrote:
Wait, I take that back. I don't know of solid ways to sort into a copy
or shuffle into a copy. For shuffling I'd need auxiliary memory (in
addition to the copy itself), and for sorting I'd be better off copying
and then sorting in place. Could anyone illuminate me about better
ways?
Andrei
That's why I said it /might/ be faster. It doesn't have to, the default
implementation may look as follows:
typeof(Range.first)[] shuffledCopy(Range)(Range range) {
return shuffle(createCopy(range));
}
However, it may be implemented quite differently if not inplace. For
this to work we need two primitives that I didn't find in std.range (I
know names are not good, feel free to rename them as you please):
struct RandomNumbers(Rnd = Random)
{
// ...
}
A finite range of length 'max' that generates random numbers in interval
[0..max) without repeating. An example:
That's the problem. How do you do this without remembering all the
number you have returned so far (i.e. generate an array of N integers)?
I've done algorithms like this, and generally you have to mutate the
source array (swapping used items with the item at the location you took
from). You may save some time on swapping by building a temporary array
of pointers or indexes, but you still have to build a temporary array,
which is what Andrei was saying.
-Steve
Well, I've attached the source code, so take a look at it. I don't
remember all the values returned so far but I still use O(N) temporary
storage.
Yes, you are remembering. The O(N) temporary storage is the part that
remembers what you have returned (or rather, what you have not yet
returned). However, it is clever how you do not have to initialize the
array to begin with. I'm still not quite sure how it works.
Yah, the implementation is neat. The thing is it's not "RandomNumbers",
it's "RandomPermutation" because what it really generates is a
permutation of the numbers {0, 1,...., n}. Maybe a convenient way to
generate permutations in std.random would please everybody. Then you
index an array by a random permutation of its indices and you obtain a
random cover of the array.
Andrei
