----------------------------------------------------------- This is an automatically generated e-mail. To reply, visit: http://git.reviewboard.kde.org/r/110262/ -----------------------------------------------------------
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
