std.string and ranges

[Denis Koroskin]

On Thu, 12 Feb 2009 07:46:31 +0300, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> Andrei Alexandrescu wrote:
>> Denis Koroskin wrote:
>> [about shuffling ranges]
>>> I'm with bearophile here. Not because his version is shorter, but  
>>> because
>>> 1) some containers/ranges might not have a dup method
>>> 2) it is potentially faster because it may avoid unnecessary data  
>>> copying (relevant for large arrays).
>>>
>>> That said, having both versions is preferred by me with names like  
>>> shuffle and shuffledCopy.
>>> The same could be applied to sort - sortedCopy might be useful, too.
>>  Oh, I understand now. Incidentally topNCopy exists already, and it  
>> becomes a sortedCopy for n = input.length. But perhaps an explicit  
>> function would drive the point home better.
>>  About shuffleCopy, you and Leonardo are both right that it could be  
>> significantly faster than copying and then shuffling the copy. The  
>> solution that I see most in the spirit of the new range design is to  
>> have a ShuffledRange that, given another range, iterates it in a random  
>> manner. An ordinary copy() call closes the deal if a copy is needed.
>
> 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:

     Random rnd;
     auto gen = RandomNumbers(10, rnd);

     foreach (n; gen) {
         writefln(n);
     }

Sample output:

2
6
8
1
4
7
5
9
0
3

Sample implementation is attached.

Next we need RandomItems - a finite range the acepts a random access range  
and returns random elements one-by-one without repeating:

struct RandomItems(Range, Rnd = Random)
{
    // ...
}

It makes use of RandomNumbers generator and is very simple (sample source  
attached, too). Now we can create shuffledCopy easily:

auto shuffledCopy(Range)(Range range)
{
     auto gen = RandomItems!(Range)(range);
     typeof(range[0])[] copy = new typeof(range[0])[range.length];

     foreach (ref elem; copy) {
         elem = gen.head;
         gen.next();
     }

     return copy;
}
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test.d
Type: application/octet-stream
Size: 2859 bytes
Desc: not available
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20090212/2cd19484/attachment.obj>