Geek Answers Handbook

Improving Shuffle Effectiveness

I am now using the following code to create a Shuffle extension:

public static class SiteItemExtensions
{
    public static void Shuffle<T>(this IList<T> list)
    {
        var rng = new Random();
        int n = list.Count;
        while (n > 1)
        {
            n--;
            int k = rng.Next(n + 1);
            T value = list[k];
            list[k] = list[n];
            list[n] = value;
        }
    }
}

I am looking for a way faster and more efficient way to do this. Right now, using the stopwatch class, it takes about 20 seconds to shuffle 100,000,000 items. Anyone have any ideas to make this faster?

+5
source share
2 answers

This emphasizes an aspect of modern computer design that is often ignored. This can be done more than 3 times faster by a stupid change:

            int k = 0; rng.Next(n + 1);  // silly change

, . , , - . , , , , , . . , , , , . , , , , , .

, , . . 100 000 1000 3 .

+4

.

, ( List<int>):

count      time (s)     slowdown
100000000  16.0429005   11.99215276436421
10000000   01.3377832   20.37312930505406
1000000    00.0656641   13.36837069158574
100000     00.0049119

10 ^ 6 10 ^ 7. 10 , 20 . , ( CPU) .

, ( ), IList<T> List<T> on []:

IList<T>:   16.0429005 s
List<T>:    14.3529349 s

Visual ++ 2010, std::random_shuffle std::vector<int> 100000000 ...

17.947 s

... , , , .

(. # ++ Release .)

+3

More articles:


All Articles