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

[Commit Hook]

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

(Updated May 22, 2013, 5:19 p.m.)


Status
------

This change has been marked as submitted.


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/20130522/71ca92a0/attachment.htm>