std.string and ranges

[Andrei Alexandrescu]

bearophile wrote:
> Andrei Alexandrescu:
>> There's plenty of more work to do on random, particularly on generating non-uniform distributions, and probably others so I'd appreciate your input.<
> 
> In my dlibs there's a random module too, I have not finished it, but it already contains some useful stuff.
> http://www.fantascienza.net/leonardo/so/dlibs/random.html

Are you sure we're looking at the same libraries? What I see is that the 
std.algorithm has most of what you ask below, and that dlibs random is 
rather thin.

> A module like that in a standard lib needs functions like:
> - choice: given an iterable of items, picks one at random

int array[100];
auto rnd = Random(unpredictableSeed);
auto rndElement = array[uniform(rnd, 0, 100)];

> - randInt: gives a random integer in an interval, the lower bound is zero by default.

auto randInt = uniform(rnd, 0, 10);

> - shuffle: to shuffle randomly a given array (or range with random access, I'd say) in place.

randomShuffle(array, rnd);

> - shuffled: like shuffle, but creates a copy of the items. Return an array.

auto another = array.dup;
randomShuffle(another, rnd);

> - uniform: gives a random real/float/double in a given interval

double d = uniform(rnd, 0, 1);

> - sample: extracts n items from an iterable with uniform distribution, without replacement

I'll add this.

> - weightedChoice: like choice, but the user can specify the relative probability of choosing each item.

auto x = dice(rnd, 70, 20, 10);

> I can assure you that such functions are hugely useful in tons of programs. Yet, you don't need more than few days to implement all those things (I already have implementations of most of them).

Again, I'm looking at dlibs/random and std/random and am a bit confused. 
  I should be saying what you're saying! Are you sure you're not talking 
about rand in D 1.0 and about a dlibs from the future?

> Few basic and easy distributions may be useful too.

That I'd definitely appreciate your help with. For example, things like 
Gaussian and Poisson distribution would be very useful for many machine 
learning applications.

> A random module has to be used by lot of different people in many different situations:
> - Some people need very good random numbers, even if they are slow to produce. Other people may also need a thread safe random generator.
> - Some people need just to write a 15-lines long D program that looks like a script. Their code often doesn't need to be very fast, but the code must be as simple as possible, and the faster possible to write, so the syntax has to be short and very intuitive. The programmer doesn't want to read the docs to write such code.
> - Some people need to produce tons of random numbers, as fast as possible, but they don't need to be high quality. In such situation thread safety may be less important.
> - Some people just need to write safe and fast code, something normal.
> 
> So to fulfill all such purposes I think the random module needs needs three different random generators:
> - A really fast one. I think R250/521 is the best for this purpose, it's faster than the usual one used in C and it's much better. It needs a certain amount of good random numbers to start, that can be given by the other slower and better random generators. Such code is designed to be as fast as possible.

std.random offers MinStdRand0 and MinStdRand, two linear congruential 
random generators that are fast. Also you can use 
LinearCongruentialEngine to create your own, with different parameters.

> - A multi-purpose average random generator, very easy to use, so it doesn't need to instantiate a class if you are writing a single threaded program, you just use simple functions. A generator like KISS of Tango is good here, but the API can be made simpler and very easy.

Perhaps there is some merit in having some random generation that 
doesn't involve creating an object. I don't think it's paramount, but 
it's a marginal convenience.

> - A very good generator, thread safe. For this a variant of the Mersenne Twister is good.

Like std.random.MersenneTwisterEngine I presume :o).

> Info about R250/521:
> http://www.informs-cs.org/wsc97papers/0127.PDF

How does R250/521 compare with linear congruential and the Mersenne 
Twister engine? A cursory look failed to answer that question, and I 
don't have time for a closer read.

Anyhow, it would be great to include more generators in Phobos, so if 
you plan to contribute some please let me know. The planned interface is 
similar with the range interface.



Andrei