> On May 1, 2013, 9:03 p.m., Parker Coates wrote:
> > 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;
> >
> >
> >
I had thought about that as well, this is the reason why I propose to push that
to master only, and not to KDE/4.10. Even though I think that a design which
relies on the order of the items in a randomized sequence might be questionable
in an application, it might make sense in unit tests. If the patch is pushed to
master only, it would give people some time to react if anything breaks. At
first sight, I did not notice anything in http://lxr.kde.org/ident?i=randomize
that looks dangerous though.
On the other hand, if people are worried that this change might break things,
then we could just deprecate the existing method and implement Fisher-Yates in
a new one (maybe KRandomSequence::shuffle ?). The disadvantage would be that
every application that uses the old method needs to be ported to the new one in
order to stop wasting CPU cycles and prevent freezes (like when you set up a
Plasma picture frame slideshow with many pictures).
- Frank
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
http://git.reviewboard.kde.org/r/110262/#review31855
-----------------------------------------------------------
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
>
>
