随笔 - 224  文章 - 41  trackbacks - 0
<2010年10月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

享受编程

常用链接

留言簿(11)

随笔分类(159)

随笔档案(224)

文章分类(2)

文章档案(4)

经典c++博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜

原文地址:http://www.cnblogs.com/huaping-audio/archive/2008/09/09/1287985.html

shuffle算法,我把他叫做洗牌算法,它的目标正好与各种的sort算法相反,即把一个有序(或者无序)的一系列元素打乱,以满足需求。

举个两例子,大家都知道扑克牌,我们每次都需要在摸牌之前把牌洗掉,用来让每个人摸到每张牌的概率尽量相等,增加游戏的随机性和乐趣;还有音频播放器,有一些人不喜欢顺序播放,而喜欢使用随机播放(其实随机播放分为两种,random和shuffle,后文会介绍到),比如iPod Shuffle的卖点之一就是“你永远不知道你将要听到的下一首歌曲是什么”。至少,如果要模拟扑克牌游戏,或者做音频播放器,都要使用shuffle算法,而二者的shuffle算法却有一些区别,一个是一次性的洗牌,另一个则是每次取一首歌。那么怎么实现他们呢?

扑克牌的shuffle算法:

下面为了方便和容易读懂,我都用扑克牌来作例子:桌上有n张牌,并且对桌子上的牌进行标号,从0直到n-1。我们的目的是洗这些牌。

一个比较容易想到的方法是,桌子上有n张扑克牌,我第i次从桌子上等概率随机取一张扑克牌,作为洗牌后牌堆的第i张扑克牌,那么这个算法实现起来应该是这样的:

伪代码:
for i <- 0 to n - 1
do d <- Random mod (n - i)
   shuffle[i] <- deck[d]
   deck[d] <- deck[n - i]

其中,deck是洗牌前的序列(0~n-1),shuffle是洗牌后的序列(0~n-1),第i次(从0开始数)在剩下的n-i张牌里等概率的取一张牌,把它放到shuffle里。而deck[d] = deck[n - i]这句达到的效果是删除取过的牌。

这个方法的时间复杂度是O(n),已经可以接受了,但这个方法还不够好,因为我们需要两个长度为n数组。其实可以很容易得得到下面的方法,解决空间的问题:
伪代码:
for i <- 0 to n - 1
do d <- Random mod (n - i)
   swap(deck[d], deck[n - i])

这样,这个算法的道理就有些像选择排序了,第i次(从0开始数)确定第n-i个元素的原位置,并且交换两个位置上的元素。它的复杂读仍然是O(n),而只需要1个额外的空间来储存交换用的临时变量。
这个方法已经是一个比较好的解决方法了(自己认为),如果你还能写出更好的shuffle算法,请告诉我。

我相信对洗牌这种东西有了解的人都不会用这样的方法来洗牌:另外对每张牌做一个标记,即是否抽过这张牌:然后第i次在n张牌里随机抽一个,如果这张牌曾经被抽过,那么把它放回去,重复抽取,直到抽到一张没被抽过的牌,将这张牌标记为抽取过的牌,然后在纸上的第i个地方记下这张牌。在计算机里这样实现:

伪代码:
for i <- 0 to n - 1
do d <- Random mod n
   while did[d] = 1
   do d = Random mod n
   did[d] <- 1
   shuffle[i] <- deck[d]


看了描述,你一定就会觉得这种方法实在是遭透了,不仅麻烦,而且会有一个陷阱,那就是在某次取牌的时候,也许会运气差永远也取不到没有被取过的那张牌,导致程序运行的不确定性。然而,在初学者当中,却有不少是用这种方法实现的shuffle的。个人认为,在设计算法的时候,越简单、越接近生活的模型,就越容易设计出好的算法,而且算法的描述也更接近实际生活。因此,设计算法的时候,如果能往平时生活的方面想, 总是事半功倍的。

附上我自己实现的一个类qsort的shuffle算法

// element_Size is the size of each element
 
void swap(void const *element1, void const *element2, size_t element_Size)
{
    char *temp = new char,
         *elem1, *elem2;
    elem1 = (char *)element1;
    elem2 = (char *)element2;
    for(int i = 0; i < element_Size; i++, elem1++, elem2++){
        *temp = *elem1;
        *elem1 = *elem2;
        *elem2 = *temp;
    }
    delete temp;
}
 
// array_Size is the size of array,
// element_Size is the size of each element in array
 
void shuffle(void const *array, size_t array_Size, size_t element_Size)
{
    void *element1, *element2;
    srand(time(0));
    for(int i = 0; i < array_Size / element_Size; i++){
        element1 = (char *)array + i * element_Size;
        element2 = (char *)array + rand(i * element_Size,
            array_Size - element_Size, element_Size);
        swap(element1, element2, element_Size);
    }
}

 

播放器的shuffle算法:

前面说过播放器的随机播放有两种,一种叫Random,一种叫Shuffle(我自己理解的......),下面解释这两种方法的不同。

学过概率的人都该知道有放回的抽取的概念。袋中有n个不同的小球,每次抽取一个小球,然后放回,每一次取的时候概率都是相同的。这正是播放器random算法的原理,这种算法实现起来很简单,一首歌结束以后,只需要随机选取下一首歌就行了。
但是这样做有一些缺点:1,有一定的概率使得连续选取的两首歌是同一首歌,我相信并不是所有人都希望在shuffle模式下连续听同一首歌吧,当然也有解决办法,那就是增加层循环判断,如果选上同一首歌,则重新选,而这样又会重蹈那个很烂的洗牌算法的覆辙。2,当听完一首歌的时候,觉得还想再听一遍,怎么办?按下“上一首”,你会发现这时听到的歌曲已经不是刚才那一首想听歌曲了,因为这种方法只知道当前的状态,而不知道过去的播放状态。怎么办?一种办法是增加一个队列叫做“刚才播放列表”,把播放过的歌曲按照顺序储存在列表里。3,有一定概率在很长的一段时间内,播放器不停的在重复播放两首歌曲A和B或者类似情况,就像这样:...-A-B-A-B-A-B-...。这种情况也是很讨厌的,可是如何避免呢?我能想到的办法是增加判断,看这首歌是不是在列表的最后几项里,如果在就不选这首......

但是这些概率都小的可怜,对于一个播放器的random函数来说,能够考虑到以上的几点,已经能够做到足够random和人性化了。只要能够合理的选择参数,考虑到一些特殊情况(比如极小的播放列表),以及考虑用户的心理,就能做出一个比较好的random函数。

下面讲我设计的播放器shuffle算法,shuffle算法能够很大程度上避免random算法的缺陷,在空间时间上都很节约,而且能够达到比较理想的随机化效果。它的大体思路是这样的:

我们使用一个隐含的shuffle播放列表(一个循环队列)来储存歌曲的顺序,并用一个指针表示正在播放的歌曲(记作"^"),比如当前的播放列表是这样的:

ABCDEFGHIJKLMN
             ^

即现在有14首歌,将要播放位置1的歌曲(正在播放位置14的歌曲),我们认为队列头和尾是相连的,即N后面的元素是A,那么这样够成了一个循环队列。
在播放之前,我们在前7(7=14*0.5,这个比例可以随便选,当然越大随机性越大,但能后退的次数越少)个位置中,随机取一个一首歌,把它和将要播放的那个位置的歌曲交换。假设我们选的是E,则队列变成这样:

EBCDAFGHIJKLMN
^

然后播放E。E播放完了以后(或者选择下一首时),重复刚才的动作,即在BCDAFGH中随机选一个,交换,比如选到H,则队列变成:
EHCDAFGBIJKLMN
 ^

然后播放H。这样,一个shuffle算法初步完成了。

比如某一时刻播放器的状态是这样:
EHCDAFGBIJKLMN
          ^

则我们在LMNEHCD中选择一个,比如选择到H,那么交换并播放,成为:
ELCDAFGBIJKHMN
           ^

但是如果用户选择上一首怎么办呢?我们可以再记录一个指针指向最新shuffle选择出来的那首歌曲(记作"*"),没有选择过前一首的时候,它与播放指针指向同一个位置。当选择前一首的时候,仅移动指针^,而不移动*,比如上一个例子播放的时候按下前一首以后,成为:

ELCDAFGBIJKHMN
          ^*

这时候播放的K正好是刚才播放的那一首,当然这达到了我的目的,即可以选到刚才播放的曲目,当然如果再一次选择上一首,就会变成:

ELCDAFGBIJKHMN
         ^ *

这时候如果按下一首,应该判断^指向的是不是和*指向的相同,如果相同,就按照最早介绍的shuffle算法进行随机选取,不相同就简单的移动^,即成为:

ELCDAFGBIJKHMN
          ^*

伪代码:
function keypress(key)
   if key = NEXT
      if p1 = p2
      do p1 <- p1 + 1
         p2 <- p2 + 1
         k = Random mod (length / 2)
         swap(p1, (p1 + k) mod length)
         play(p2)
      else
      do p2 <- (p2 + 1) mod length
         play(p2)
   if key = PREV
      do p2 <- (p2 + length - 1) mod length
         play(p2)

这个播放器的shuffle算法比较简单实用,而且节约内存开销(这对mp3 walkman之类的东西是十分重要的),当然也有个小缺点,就是当^前移多次回到*以后,再按下一首,则会重新开始shuffle,但是歌曲数目很多的情况下,这个缺点并不是那么重要。
这个算法在刚开始听的时候,并不是很随机,可是随着听的次数的增多,队列会越来越乱,达到一个shuffle的效果。
当然,也可以在第一次对这个列表播放之前,使用扑克牌的shuffle算法(见本文第一部分)进行一次shuffle,这样,刚开始播放的时候列表就是随机的。
通过原理我们可以看到,对于刚听过的那首歌来说,不经过length / 2次,是不会再一次听到的,因此很大程度上避免了random算法的缺陷。这个length / 2的参数可以按照具体情况选择,可以是常数,也可以是随机数,也可以是和长度有关的一个数。 

posted on 2010-10-11 17:25 漂漂 阅读(1037) 评论(0)  编辑 收藏 引用 所属分类: 算法

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理