skoo's notes

努力记录一些自己觉得有趣的东西...
28 September 2013
by skoo

那些非常简单的,却又能真正的解决实际问题的算法往往才是最经典的。直观感受,洗牌算法运用最多的应该是在游戏开发中,其实并不一定,洗牌其实就是排序算法的反向操作,目的就是将原本可能存在的一定顺序给打乱,变成一种非期望的顺序,所以应用场景应该还是蛮广泛的。简单的打乱一组次序应该是一件很容易的事情,但一个正确的洗牌算法除了能够打乱次序外,还具备等概率性,也就是说任何一个元素被打乱到任何一个位置的概率是相等的。

其实,我平时的编程中好像很少碰到洗牌的时候。最近在Go语言的实现中看到一个有趣的洗牌场景,这里记录一下和大家分享。

select {
case 条件1:
	。。。
case 条件2:
	。。。
case 条件3:
	。。。
case 条件4:
	。。。
case 条件5:
	。。。
}

如果你了解Go语言的话,应该知道上面的select语句会随机的选择一个可以执行的case条件。这里是如何实现随机选择的呢???

有人说,“这个很简单啊,利用随机数在这5个条件中随机选择一个就可以了,只要随机数发生器实现得好就行了”。 这个方法看上去似乎可以工作,但这5个条件并不是都可以执行的,可以理解为有的条件并不是true。select的目的是在为true的条件中随机选择一个,并不是在所有条件中进行随机选择。

既然是在可执行的条件中随机选择一个来执行,那么我们再加一个步骤,“首先遍历这里的所有case条件,把可执行的条件给标记出来,然后再在标记出来的可执行条件中利用随机数来随机选择一个”。嘿,这方法可以真正解决问题了,行得通的样子。其实,在Go runtime里,使用这个方法去做,挺麻烦的,主要的问题是判断条件是否可执行,因为并不存在一个判断的过程,而是直接去执行,执行了就ok了,不能够执行就算了,所以针对条件是一个试图去执行的探测,之前并没有一个可判断的标准。

Go语言的实现,在解决这个问题的时候,就利用了洗牌,本文也就是介绍洗牌算法用于这种场景。因为在试图执行每个case条件之前,并不知道哪些条件可执行,所以Go的实现者就先把所有的条件利用洗牌给重新排序一遍,然后再从头到尾依次试图执行每个条件,碰到一个可执行条件后,就忽略后面的条件了。这样子一来,就做到了在所有可执行条件中,随机选择一个可执行的条件。这种场景利用洗牌来实现,明显是非常的合适和优雅的。

常用的洗牌算法蛮多的,比如:经典的Fisher-Yates,伪代码如下:

To shuffle an array a of n elements (indices 0..n-1):
  	for i from n − 1 downto 1 do
   j ← random integer with 0 ≤ j ≤ i
   exchange a[j] and a[i]

本文提到的Go采用的洗牌算法和Fisher-Yates非常像,甚至我觉得它就是Fisher-Yates,只是和这个伪代码有一小点不同之处。

for(i=1; i<sel->ncase; i++) {
    o = sel->pollorder[i];
    j = runtime·fastrand1()%(i+1);
    sel->pollorder[i] = sel->pollorder[j];
    sel->pollorder[j] = o;
}

可以看出这两个洗牌算法非常相似,但又有一点不同。因此,我决定对Go的洗牌算法进行统计测试,测试方法参考:如何测试洗牌程序。我的测试是执行10000次洗牌,测试代码:https://gist.github.com/skoo87/6724116#file-go_shuffle-go

结果数据:

	 0     1     2 	   3 	 4     5     6     7     8     9    (位置)
	     
1 ->   951  1010   980  1016  1036  1007  1048   951  1020   981
5 ->   940  1041  1028  1057   997  1038   979   991   923  1006
3 ->  1041   976  1000   994   962  1009   970   979  1026  1043
9 ->  1013   964  1021   957   971   983  1034  1052  1016   989
7 ->  1053  1009  1031   960  1012   998   970  1022   993   952
6 ->  1012   963   984   980  1011  1000  1034   950  1041  1025
2 ->   986   992   994   975   993  1025  1023   994  1025   993
8 ->  1001   986  1006   992   996   952   996  1043  1003  1025
0 ->   980  1041  1003  1043   979  1003   981   995   961  1014
4 ->  1023  1018   953  1026  1043   985   965  1023   992   972	
(被洗对象)

从测试结果数据来看,每个对象出现在每个位置的次数相差不大,还是很靠谱的。

可以看出这分数据是一个二维表的形式,其实,我很想将这份数据给绘制成图表,最理想的图就是构造一个二维坐标,每个对象出现的位置就画一个点,那么最后形成的图看上去各个地方的密度都差不多的时候就说明洗牌算法比较靠谱。不知道有什么好用的工具可以直观的可视化这种形式的数据,如果你知道,麻烦告诉我一下。

今天天气不怎么好,宅家里码字比较开心,因为不觉得是在浪费美好的时间,哈哈。