Review Request 110262: KRandomSequence::randomize: use the Fisher-Yates Algorithm to achieve O(N) complexity

[Parker Coates]

-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
http://git.reviewboard.kde.org/r/110262/#review31855
-----------------------------------------------------------


Since KRandomSequence is a class for generating a predictable random sequence, is it not possible that this change would break applications that relied on the code below producing a consistent result between kdelibs releases?

QList list = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
KRandomSequence pseudoRand( 123545 );
pseudoRand.randomize( list );
return list;




- Parker Coates


On May 1, 2013, 8:34 p.m., Frank Reininghaus wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> http://git.reviewboard.kde.org/r/110262/
> -----------------------------------------------------------
> 
> (Updated May 1, 2013, 8:34 p.m.)
> 
> 
> Review request for kdelibs.
> 
> 
> Description
> -------
> 
> The current algorithm that is used to shuffle lists is rather inefficient. It works by removing the first item of the list repeatedly and inserting it at a random position in a new list, which is finally used to replace the original list. Unfortunately, this results in O(N^2) run time complexity because inserting into a list, which is done N itmes, is O(N).
> 
> I propose to replace this algorithm by the Fisher-Yates algorithm, which works by swapping items N - 1 times. One could modify the entire thing further, like providing randomization also for other containers and not only QList, but that would probably be frameworks material. 
> 
> 
> Diffs
> -----
> 
>   kdecore/util/krandomsequence.h 46949b4 
> 
> Diff: http://git.reviewboard.kde.org/r/110262/diff/
> 
> 
> Testing
> -------
> 
> I wrote a small benchmark: http://paste.kde.org/735914/
> 
> I got the following results with the existing algorithm:
> 
> RESULT : Benchmark::randomSequenceBenchmark():"n=0":
>      0.000015 msecs per iteration (total: 66, iterations: 4194304)
> RESULT : Benchmark::randomSequenceBenchmark():"n=1":
>      0.000192 msecs per iteration (total: 101, iterations: 524288)
> RESULT : Benchmark::randomSequenceBenchmark():"n=3":
>      0.00070 msecs per iteration (total: 93, iterations: 131072)
> RESULT : Benchmark::randomSequenceBenchmark():"n=10":
>      0.0025 msecs per iteration (total: 83, iterations: 32768)
> RESULT : Benchmark::randomSequenceBenchmark():"n=30":
>      0.0070 msecs per iteration (total: 58, iterations: 8192)
> RESULT : Benchmark::randomSequenceBenchmark():"n=100":
>      0.023 msecs per iteration (total: 97, iterations: 4096)
> RESULT : Benchmark::randomSequenceBenchmark():"n=300":
>      0.077 msecs per iteration (total: 79, iterations: 1024)
> RESULT : Benchmark::randomSequenceBenchmark():"n=1000":
>      0.35 msecs per iteration (total: 90, iterations: 256)
> RESULT : Benchmark::randomSequenceBenchmark():"n=3000":
>      1.8 msecs per iteration (total: 58, iterations: 32)
> RESULT : Benchmark::randomSequenceBenchmark():"n=10000":
>      18 msecs per iteration (total: 72, iterations: 4)
> RESULT : Benchmark::randomSequenceBenchmark():"n=30000":
>      283 msecs per iteration (total: 283, iterations: 1)
> RESULT : Benchmark::randomSequenceBenchmark():"n=100000":
>      3,823 msecs per iteration (total: 3,823, iterations: 1)
> 
> Here are the numbers for the proposed new algorithm:
> 
> RESULT : Benchmark::randomSequenceBenchmark():"n=0":
>      0.000015 msecs per iteration (total: 65, iterations: 4194304)
> RESULT : Benchmark::randomSequenceBenchmark():"n=1":
>      0.000015 msecs per iteration (total: 65, iterations: 4194304)
> RESULT : Benchmark::randomSequenceBenchmark():"n=3":
>      0.00018 msecs per iteration (total: 98, iterations: 524288)
> RESULT : Benchmark::randomSequenceBenchmark():"n=10":
>      0.00079 msecs per iteration (total: 52, iterations: 65536)
> RESULT : Benchmark::randomSequenceBenchmark():"n=30":
>      0.0025 msecs per iteration (total: 83, iterations: 32768)
> RESULT : Benchmark::randomSequenceBenchmark():"n=100":
>      0.0084 msecs per iteration (total: 69, iterations: 8192)
> RESULT : Benchmark::randomSequenceBenchmark():"n=300":
>      0.025 msecs per iteration (total: 52, iterations: 2048)
> RESULT : Benchmark::randomSequenceBenchmark():"n=1000":
>      0.085 msecs per iteration (total: 88, iterations: 1024)
> RESULT : Benchmark::randomSequenceBenchmark():"n=3000":
>      0.25 msecs per iteration (total: 66, iterations: 256)
> RESULT : Benchmark::randomSequenceBenchmark():"n=10000":
>      0.85 msecs per iteration (total: 55, iterations: 64)
> RESULT : Benchmark::randomSequenceBenchmark():"n=30000":
>      2.6 msecs per iteration (total: 86, iterations: 32)
> RESULT : Benchmark::randomSequenceBenchmark():"n=100000":
>      10 msecs per iteration (total: 81, iterations: 8)
> 
> 
> Thanks,
> 
> Frank Reininghaus
> 
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.kde.org/pipermail/kde-core-devel/attachments/20130501/ffaf29dd/attachment.htm>