std.string and ranges

[bearophile]

Andrei Alexandrescu:

>What I see is that the std.algorithm has most of what you ask below,<

"shuffle"/"shuffler" are of course algorithms, but I think mixing all kind of algorithms into a module isn't good, it's better to move the random-related algorithms into std.random. It helps the memory of the programmer to know where to look for, and avoids lumping too many mixed things into a single module.


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

That's just a starting point, now you can wrap that into a nice single function with this interface:
choice(iterable)
that works with any iterable, lazy too.
I know that's slow code, but in many situations you don't care and you want handy and safe functions. And where you need max speed, you don't use it.

I don't like this:
uniform(rnd, 0, 100)
This seems better:
rnd.uniform(0, 100)
Then 0 can be the default lower bound:
rnd.uniform(100)
And for simple usages you may just want the default struct:
uniform(100)


>> - randInt: gives a random integer in an interval, the lower bound is zero by default.
>auto randInt = uniform(rnd, 0, 10);
>> - uniform: gives a random real/float/double in a given interval
> double d = uniform(rnd, 0, 1);

How can uniform return ints or doubles according to the input? I think it may be better to have two different functions.
(And you can optimize efficiency if you know you need an integral value as result).

A normal(avg, stddev) function can be good too, where avg may be by default zero again :-)

A fastNormal(avg, stddev) function too can be useful, less precise but faster.


>> - shuffled: like shuffle, but creates a copy of the items. Return an array.
> auto another = array.dup;
> randomShuffle(another, rnd);

shuffled() is meant to be used in a single line, so you can use it into an expression.
And dup works with arrays only, so you need to put into shuffled() a call to something like the array() function of my libs to have something more general.


>> - weightedChoice: like choice, but the user can specify the relative probability of choosing each item.<
>auto x = dice(rnd, 70, 20, 10);<

I don't understand that interface, this isn't good. I was talking about a function that given an iterable of items and an iterable of frequences (or probabilities) returns an item at random according to the given probabilities.


>How does R250/521 compare with linear congruential and the Mersenne Twister engine?<

R250/521:
- is generates better rnd values than linear congruential, and is a bit faster.
- is faster than KISS.
- is much much faster than Mersenne Twister.
- needs few good rnd numbers to start, so they can be given by a Mersenne Twister (they may be even hard-coded).


>Anyhow, it would be great to include more generators in Phobos, so if you plan to contribute some please let me know.<

I think it's better to not overdo the number of generators, and put there only few of them, that the programmer can tell apart in a simple way.

I think 3 generators like R250/521 (that you can choose to use a set of free functions or as struct methods), KISS (two iterfaces), and Mersenne Twister (only the thread safe API) may cover most basic usages and some of nonbasic ones.

Then it's easy to help the programmer to tell them apart, you can sort them just according to their speed:
  fastRnd ==> R250/521
  rnd ==> KISS
  slowRnd ==> Mersenne Twister
(if you think that people will not use the third if you put "show" there, then you can call it preciseRND, but it's a longer name).

Later it can be added a way to generate huge random BigInts too.

Bye,
bearophile