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

[Johan Montelius]

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.

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).

Hmm, tempted to giv it a go but have to pick up the kids.

  Johan



-- 
Associate Professor Johan Montelius
Royal Institute of Technology - KTH
School of Information and Communication Technology - ICT