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

[Pascal Chapier]

Hello,

I have tried a solution which is quite efficient, and I got good results in distribution. But I have trouble with the performance results,
particularly the 2 last values in the table bellow (is there a known bug in erlang:statistics function?). My intent was to evaluate the
relationship between length and shuffle time.
I did a new test, and got extravagant results again, but for other list length - the time for 1 list cannot be 4293323265µs since the program did
the 14 * 1000 loops of test/0 in less than 6 hours -. My configuration is R13B04 on windows XP.

The risk of this method is to get two identical numbers in the tupple_list. I can't evaluate the impact on randomless,
in this case, keysort simply left the elements in original order.

The quality of the method depends on the random:uniform function, maybe some other function could be faster and/or better.

Here is the code I used:

shuffle(P) ->
    Max = length(P)*10000,
    {_,R}= lists:unzip(lists:keysort(1,[{random:uniform(Max),X} || X <- P])),
    R.

test() ->
    test:perfshuffle(shuffle,125,1000),
    test:perfshuffle(shuffle,250,1000),
    test:perfshuffle(shuffle,500,1000),
    test:perfshuffle(shuffle,1000,1000),
    test:perfshuffle(shuffle,2000,1000),
    test:perfshuffle(shuffle,4000,1000),
    test:perfshuffle(shuffle,8000,1000),
    test:perfshuffle(shuffle,16000,1000),
    test:perfshuffle(shuffle,32000,1000),
    test:perfshuffle(shuffle,64000,1000),
    test:perfshuffle(shuffle,128000,1000),
    test:perfshuffle(shuffle,256000,1000),
    test:perfshuffle(shuffle,512000,1000),
    test:perfshuffle(shuffle,1024000,1000),
    test:testshuffle(shuffle,10,1000000).


testshuffle() ->
    io:format("Usage: testshuffle(ShuffleFunctionName,SizOfList,NumberOfTrial)~n").

testshuffle(F,L,T) ->
    S = lists:seq(0,L),
    Nul = [X-X || X <- S],
    {Res,Car} = testshuffle(F,Nul,Nul,S,L,T),
    Moy = [X/T || X <- Res],
    Sig = [math:sqrt(X/T) || X <- Car],
    Tm = L/2,
    Td = math:sqrt((L*(L+2))/12),
    io:format("Theoritical results: average = ~p, deviation = ~p~n",
              [Tm,Td]),
    io:format("Average   :~p~n",[Moy]),
    io:format("Deviation :~p~n",[Sig]).

testshuffle(_,Am,Ac,_S,_L,0) ->
    {Am,Ac};
testshuffle(F,Am,Ac,S,L,I) ->
    Ns = ?MODULE:F(S),
    Am1 = [X+Y || {X,Y} <- lists:zip(Am,Ns)],
    Ac1 = [X+math:pow(Y-L/2,2) || {X,Y} <- lists:zip(Ac,Ns)],
    testshuffle(F,Am1,Ac1,S,L,I-1).

perfshuffle() ->
    io:format("Usage: perfshuffle(ShuffleFunctionName,SizOfList,NumberOfTrial)~n").
    
perfshuffle(F,L,T) ->
    S = lists:seq(0,L),
    statistics(runtime),
    statistics(wall_clock),
    perfshuffle1(F,S,T),
    {_, Time1} = statistics(runtime),
    {_, Time2} = statistics(wall_clock),
    T1 = 1000 * Time1/T,
    T2 = 1000 * Time2/T,
    io:format("Average Shuffle Time for a list of ~p elements~nRuntime   -> ~p~nWallclock -> ~p~n",
                [L,T1,T2]).

perfshuffle1(_F,_S,0) ->
    ok;
perfshuffle1(F,S,N) ->
    _ = ?MODULE:F(S),
    perfshuffle1(F,S,N-1).
    
And the results (performance in µs):    
    

Average Shuffle Time for a list of 125 elements
Runtime   -> 281.0
Wallclock -> 281.0
Average Shuffle Time for a list of 250 elements
Runtime   -> 422.0
Wallclock -> 422.0
Average Shuffle Time for a list of 500 elements
Runtime   -> 891.0
Wallclock -> 906.0
Average Shuffle Time for a list of 1000 elements
Runtime   -> 2109.0
Wallclock -> 2110.0
Average Shuffle Time for a list of 2000 elements
Runtime   -> 4328.0
Wallclock -> 4328.0
Average Shuffle Time for a list of 4000 elements
Runtime   -> 8438.0
Wallclock -> 8515.0
Average Shuffle Time for a list of 8000 elements
Runtime   -> 16828.0
Wallclock -> 17172.0
Average Shuffle Time for a list of 16000 elements
Runtime   -> 38234.0
Wallclock -> 40141.0
Average Shuffle Time for a list of 32000 elements
Runtime   -> 85750.0
Wallclock -> 90125.0
Average Shuffle Time for a list of 64000 elements
Runtime   -> 183688.0
Wallclock -> 192891.0
Average Shuffle Time for a list of 128000 elements
Runtime   -> 442297.0
Wallclock -> 4.735e5
Average Shuffle Time for a list of 256000 elements
Runtime   -> 990390.0
Wallclock -> 1058078.0
Average Shuffle Time for a list of 512000 elements
Runtime   -> 4293323265.0
Wallclock -> 2907109.0
Average Shuffle Time for a list of 1024000 elements
Runtime   -> 1630126.0
Wallclock -> 6554031.0
Theoritical results: average = 5.0, deviation = 3.1622776601683795
Average   :[4.996671,4.996889,4.997597,5.003431,5.000648,4.997709,5.005808,
            4.999759,4.996688,5.003346,5.001454]
Deviation :[3.164504542578506,3.161651941627984,3.1614915783534836,
            3.1614669063585024,3.162072737936305,3.1621861109049227,
            3.160950173602868,3.165070457351621,3.1611447293662467,
            3.160723651317843,3.1637879195673024]

Pascal
 		 	   		  
_________________________________________________________________
Hotmail : Simple et Efficace qui vous facilite la vie… Découvrez la NOW génération !
http://www.windowslive.fr/hotmail/nowgeneration/