今天瀏覽Spotify官方博客時(shí)被一篇介紹音樂隨機(jī)播放算法的博客吸引，隨后對(duì)這個(gè)問題小小研究了一下。
隨機(jī)播放音樂，這個(gè)功能太普通以至于以前從未考慮過其背后實(shí)現(xiàn)邏輯。
Random還是shuffle
我們經(jīng)常使用的隨機(jī)播放功能，在外國同行口中并不是叫Random播放，而是叫Shuffle，洗牌的意思。
為什么不是Random？來看兩個(gè)例子。
在Spotify成立之初，他們使用一種叫「Fisher-Yates shuffle」的算法去產(chǎn)生一個(gè)完全隨機(jī)（perfectly random ）的播放列表，這個(gè)算法據(jù)說非常簡(jiǎn)單，只需3行代碼搞定，不過它存在致命弱點(diǎn)。
上圖中，每種顏色代表一位歌手，也就是說我的列表里有綠色歌手的4首歌，紅色歌手的2首歌，黑色歌手的2首歌。
圖中上下兩行都是運(yùn)行Fisher-Yates算法可能產(chǎn)生的播放列表，請(qǐng)問這兩個(gè)列表出現(xiàn)的概率哪個(gè)更大呢？
答案是一樣大，完全隨機(jī)算法下，每一首歌出現(xiàn)在每個(gè)位置的概率是一樣的。你可能認(rèn)為這怎么可能，前面已經(jīng)出現(xiàn)3次綠色歌手的歌了，下一次出現(xiàn)概率應(yīng)該很小了吧。錯(cuò)了，算法是沒有記憶的，除非你告訴它，下一首不允許播放綠色歌手的歌，否則它播放綠色歌手的歌的概率還是50%。
再來看個(gè)例子，假設(shè)你播放列表里有10首搖滾樂（A），11首鄉(xiāng)村樂（B），11首爵士樂（C），下面是我自己用Python的random函數(shù)生成的序列：
A A A A C C C B C B B A C B C B B B B A B C B A C A C C A A C B
可以看出，這個(gè)列表里前半段和后半段基本上沒有B出現(xiàn)，尤其是前面連續(xù)4個(gè)A和3個(gè)B，這樣的結(jié)果是無法令人滿意的，一點(diǎn)均衡性都沒有。
回頭再想，我們?yōu)槭裁匆S機(jī)播放？因?yàn)槲覀儾恢酪犑裁?，我們想要一個(gè)隨性的播放列表，我們不想專門聽某一位歌手的或某一張專輯的曲目，我們不想按照平常循環(huán)的順序播放，我們想換換口味有點(diǎn)新意，所以我們把這個(gè)選擇權(quán)交給軟件本身去做，如果軟件接連給你播放同一個(gè)歌手或同一張專輯的曲目，那就違背我們隨機(jī)的目的了。所以好的隨機(jī)播放列表應(yīng)該做到均衡分布，同一個(gè)流派、同一個(gè)歌手、同一種專輯下的音樂彼此之間相距越遠(yuǎn)越好。
還是上面這個(gè)例子，好的播放列表應(yīng)該是下面這樣的：
A B C B C A B A C B A C B C A B C A C B A B C A C B A C B C A B
shuffle播放算法
那么如何生成上面這個(gè)均衡的播放列表呢？博主Martin Fiedler給了一個(gè)思路。
1）將列表中的歌曲按流派、歌手、專輯等邏輯范式分組，給這個(gè)組里的音樂設(shè)定一個(gè)隨機(jī)播放順序；
2）接下來把每個(gè)分組的曲目通過合并算法組成一個(gè)完整的播放列表。
很簡(jiǎn)單吧，僅僅兩步而已。接下來看看合并算法是怎么一回事。假設(shè)在第一步我們得到了下面的分組：
將每個(gè)分組擴(kuò)充到和最大分組相等的長(zhǎng)度，比如給綠色分組填充8首「靜默」歌曲，讓該組長(zhǎng)度等于12。填充的時(shí)候應(yīng)盡量讓組中的音樂均衡分布列表中。
每個(gè)分組都填充完畢后，就開始合并新列表了，從每個(gè)分組的第1列按隨機(jī)順序取出歌曲放在新列表中。
再取出第2列按隨機(jī)順序取出歌曲放在新列表中。
第3列。需要注意的是，假如第2次取出的是黃-紅-藍(lán)，第3次取出藍(lán)-黃-紅-綠，那么就會(huì)有兩個(gè)藍(lán)色分組的歌曲接連出現(xiàn)的情況，這個(gè)時(shí)候需要把第3次拿出的歌曲首尾互換，最后得出綠-黃-紅-藍(lán)的順序。
這就是shuffle播放背后的大概邏輯了，難的不是合并算法，而是填充分組的算法，個(gè)人感覺。
參考資料：
