2006馬上就要過去了,blog也長草了。貼上一點代碼,意思一下
前段時間在C#裡需要用到random shuffle功能,一時沒找到合適的代碼,就按自己的理解寫了一段,所得到結果也能滿足自己的需要。值得注意的一點是隨機數生成器的選擇。直接以Random做為隨機數生成器因為時鐘精度問題,在一個小的時間段內會得到同樣的偽隨機數序列,你shuffle後會得到同一個結果。.Net提供了RNGCryptoServiceProvider可以避免這種情況,下面是幾種用法的示例
1 ///
2 /// RandomShuffle
3 /// WuErPing 2006/12/07
4 ///
5 public sealed class RandomShuffle
6 {
7 private RandomShuffle() { }
8
9 // pseudo-random number generator, using a time-dependent default seed value.
10 static public List
11 {
12 List
13 for (int i = 0; i < size; i)
14 {
15 list.Insert(i, i);
16 }
17 System.Random random = new Random();
18 for (int i = 0; i < list.Count; i)
19 {
20 int var = random.Next(0, list.Count);
21 int temp = list[i];
22 list[i] = list[var];
23 list[var] = temp;
24 }
25
26 return list;
27 }
28
29 // using a RNGCryptoServiceProvider().GetHashCode() seed value
30 static public List
31 {
32 List
33 for (int i = 0; i < size; i)
34 {
35 list.Insert(i, i);
36 }
37 System.Random random = new Random(new RNGCryptoServiceProvider().GetHashCode());
38 for (int i = 0; i < list.Count; i)
39 {
40 int var = random.Next(0, list.Count);
41 int temp = list[i];
42 list[i] = list[var];
43 list[var] = temp;
44 }
45
46 return list;
47 }
48
49 // Cryptographic random number generators create cryptographically strong random values
50 static public List
51 {
52 List
53 for (int i = 0; i < size; i)
54 {
55 list.Insert(i, i);
56 }
57 byte[] randomBytes = new Byte;
58 RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
59 for (int i = 0; i < list.Count; i)
60 {
61 rng.GetNonZeroBytes(randomBytes);
62 int randomSeed = (randomBytes[0] << 24) | (randomBytes << 16) | (randomBytes << 8) | randomBytes;
63 int var = randomSeed % list.Count;
64 //var = System.Math.Abs(var);
65 if (var < 0) var *= -1;
66 int temp = list[i];
67 list[i] = list[var];
68 list[var] = temp;
69 }
70 return list;
71 }
72 }
注:如果要深究random shuffle算法,可以看標准C++的random_shuffle的實現。根據SGI的文檔http://www.sgi.com/tech/stl/random_shuffle.Html,算法來自
This algorithm is described in section 3.4.2 of Knuth (D. E. Knuth, The Art of Computer Programming. Volume 2: Seminumerical Algorithms, second edition. Addison-Wesley, 1981). Knuth credits Moses and Oakford (1963) and Durstenfeld (1964).
附:vc8的random_shuffle的實現
1 // TEMPLATE FUNCTION random_shuffle
2 template 3 class _Diff> inline 4 void _Random_shuffle(_RanIt _First, _RanIt _Last, _Diff *) 5 { // shuffle [_First, _Last) 6 _DEBUG_RANGE(_First, _Last); 7 const int _RANDOM_BITS = 15; // minimum random bits from rand() 8 const int _RANDOM_MAX = (1U << _RANDOM_BITS) - 1; 9 10 _RanIt _Next = _First; 11 for (unsigned long _Index = 2; _Next != _Last; _Index) 12 { // assume unsigned long big enough for _Diff count 13 unsigned long _Rm = _RANDOM_MAX; 14 unsigned long _Rn = ::rand() & _RANDOM_MAX; 15 for (; _Rm < _Index && _Rm != ~0UL; 16 _Rm = _Rm << _RANDOM_BITS | _RANDOM_MAX) 17 _Rn = _Rn << _RANDOM_BITS 18 | (::rand() & _RANDOM_MAX); // build random value 19 20 std::iter_swap(_Next, _First _Diff(_Rn % _Index)); // swap a pair 21 } 22 } 23