----------------------------------------------------------- This is an automatically generated e-mail. To reply, visit: http://git.reviewboard.kde.org/r/110262/#review32982 -----------------------------------------------------------
This review has been submitted with commit 183e59b8e9fe938c209493aa7aa98382ccd08e71 by Frank Reininghaus to branch master. - Commit Hook 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 > >
