Knuth高效洗牌算法的示例分析

今天在做一個(gè)游戲需求的時(shí)候碰到一個(gè)問(wèn)題，問(wèn)題很簡(jiǎn)單，給定75個(gè)球，編號(hào)1-75，需要保證初始化的時(shí)候位置是隨機(jī)的。

顯然，我們可以初始化一個(gè)數(shù)組A，把75個(gè)數(shù)放進(jìn)去，然后做一個(gè)shuffle函數(shù)隨機(jī)交換其中的元素，這樣就是隨機(jī)的。

我準(zhǔn)備這樣做一個(gè)shuffle，但同時(shí)也想看看golang里面是否有這樣的接口直接得到結(jié)果，看了下還真有，這個(gè)函數(shù)是rand.Perm(n)，這個(gè)函數(shù)會(huì)返回一個(gè)數(shù)組，比如我傳入75，會(huì)返回一個(gè)0-74的隨機(jī)數(shù)組。

arr := rand.Perm(75)

好奇心驅(qū)使我一探究竟，golang會(huì)用什么樣的方式實(shí)現(xiàn)Perm函數(shù)呢？

打開golang的源代碼，在rand.go文件中找到這個(gè)函數(shù)：

 

實(shí)現(xiàn)很簡(jiǎn)單，然而初一看有點(diǎn)懵，因?yàn)闆](méi)有用到shuffle，而是一次遍歷就把事情給解決了，到底是怎么回事？

仔細(xì)分析發(fā)現(xiàn)，這個(gè)算法非常精巧，每次遍歷都是將當(dāng)前的數(shù)i和已經(jīng)在數(shù)組中的隨機(jī)一個(gè)數(shù)m[j]進(jìn)行交換，最終達(dá)到了公平隨機(jī)整個(gè)數(shù)組的作用。雖然只有短短3行代碼，卻讓人有種震撼的感覺(jué)。

頓時(shí)覺(jué)得golang很NB，確實(shí)很高效。

上面這段代碼寫了4行的注釋，大概意思是說(shuō)不能省去0那一次，看起來(lái)沒(méi)啥用處，但是為了照顧r隨機(jī)器中的隨機(jī)序列，還是要加上，不然可能會(huì)造成負(fù)作用，這里面和隨機(jī)種子以及此后隨機(jī)的序列有關(guān)，為了對(duì)隨機(jī)序列不產(chǎn)生影響保證公平性，不能省略0。

網(wǎng)上搜索了一下高效洗牌算法，又發(fā)現(xiàn)python里面也有這樣的函數(shù)，這樣寫的：

for(int i = N - 1; i >= 0 ; i -- )
    swap(arr[i], arr[rand(0, i)])         // rand(0, i) 生成 [0, i] 之間的隨機(jī)整數(shù)

而這個(gè)算法的出處竟然來(lái)自于TAOCP！算法就是大名鼎鼎的 Knuth-Shuffle，即 Knuth 洗牌算法。

看似簡(jiǎn)單的問(wèn)題，竟然又扯出Knuth，大意了。

能把一件小事情做到極致的人，可以稱之為藝術(shù)家。Knuth名副其實(shí)。

最后以 Knuth 的一句話共勉：

A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better.