[erlang-questions] Speedy unsort:shuffle/1,2 ?

[Björn-Egil Dahlberg]

On 2010-05-26 17:14, Johan Montelius wrote:
> On Wed, 26 May 2010 14:41:19 +0200, Björn-Egil Dahlberg
> <egil@REDACTED> wrote:
>
>> My suggestion is included in this mail, but my question is: does anyone
>> have a faster, more generic and less memory consuming shuffle function?
>
> I haven't done any test but I would think the execution time will be
> very much depending on the number of random:uniform/1 calls that you do.
> As it is now you make a lot of calls but do not utilize the entropy. A
> don't think a call to random:uniform(2) is much cheaper than
> random:uniform(8098809898) nor do I know how well random:uniform is
> implemented.

You are of course completely right. There is a lot of unnecessary calls 
to random:uniform/1. One can always redefine the constraints for the 
fun. Instead of returning a number, return a binary. The fun is there to 
provide the user with a alternative random-function to the shuffle 
function, mainly for creating pseudo-random shuffles. shuffle/1 uses 
random:uniform/1 as default.

> Here is an idea:
>
> generate a SHA-512 binary, use the binary bit by bit to divide the list
> into two lists, if you run out of bits, generate a new pattern. Return
> the remaining bit pattern and the two lists (this is similar to split in
> qsort). Recursively apply to the first list and then the second list and
> if we do it right we can avoid doing the last append (me think).

+1, I like this idea. Easy to hook in crypto:rand_bytes/1 also.

// Björn-Egil