开发者

Shuffle List<T> [duplicate]

This question already has answers here: 开发者_如何学编程 Closed 10 years ago.

Possible Duplicate:

Randomize a List<T> in C#

I have a list which contains many thousands of FilePath's to locations of audio files, and was wondering which would be the most efficient way to "shuffle" a List?

Any help is greatly appreciated :)

Thank you


Fisher-Yates Shuffle or as it is also known as, Knuth shuffle.


Here is a simple (yet effective) implementation of the Fischer-Yates/Knuth shuffle:

Random rnd = new Random();
for (int i = files.Length; i > 1; i--) {
  int pos = rnd.Next(i);
  var x = files[i - 1];
  files[i - 1] = files[pos];
  files[pos] = x;
}

Or a slight variation:

Random rnd = new Random();
for (int i = 1; i < files.Length; i++) {
  int pos = rnd.Next(i + 1);
  var x = files[i];
  files[i] = files[pos];
  files[pos] = x;
}

As this is an O(n) operation, it's the most efficient way of shuffling a list. As all items in the list has to have chance to be moved, it's not possible to shuffle a list more efficiently than O(n).

I made a small performance test by shuffling a million items a thousand times each using this method and the currently accepted answer (LINQ OrderBy), and this is about 15 times (!) faster.


myList.OrderBy(Guid.NewGuid())


I added Jon Skeet's solution from this question to my Extensions library. I implemented methods that both take an external random number generator and create one using a default implementation (Random).

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜