今天瀏覽Spotify官方博客時被一篇介紹音樂隨機(jī)播放算法的博客吸引蛮拔，隨后對這個問題小小研究了一下吃粒。
隨機(jī)播放音樂坪稽，這個功能太普通以至于以前從未考慮過其背后實現(xiàn)邏輯匿刮。
Random還是shuffle
我們經(jīng)常使用的隨機(jī)播放功能县忌，在外國同行口中并不是叫Random播放掂榔，而是叫Shuffle继效，洗牌的意思。
為什么不是Random装获？來看兩個例子瑞信。
在Spotify成立之初，他們使用一種叫「Fisher-Yates shuffle」的算法去產(chǎn)生一個完全隨機(jī)（perfectly random ）的播放列表穴豫，這個算法據(jù)說非常簡單凡简，只需3行代碼搞定，不過它存在致命弱點精肃。
上圖中秤涩，每種顏色代表一位歌手，也就是說我的列表里有綠色歌手的4首歌司抱，紅色歌手的2首歌筐眷，黑色歌手的2首歌。
圖中上下兩行都是運行Fisher-Yates算法可能產(chǎn)生的播放列表习柠，請問這兩個列表出現(xiàn)的概率哪個更大呢浊竟？
答案是一樣大，完全隨機(jī)算法下津畸，每一首歌出現(xiàn)在每個位置的概率是一樣的振定。你可能認(rèn)為這怎么可能，前面已經(jīng)出現(xiàn)3次綠色歌手的歌了肉拓，下一次出現(xiàn)概率應(yīng)該很小了吧后频。錯了，算法是沒有記憶的暖途，除非你告訴它卑惜，下一首不允許播放綠色歌手的歌，否則它播放綠色歌手的歌的概率還是50%驻售。
再來看個例子露久，假設(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
可以看出，這個列表里前半段和后半段基本上沒有B出現(xiàn)迟几，尤其是前面連續(xù)4個A和3個B消请，這樣的結(jié)果是無法令人滿意的，一點均衡性都沒有类腮。
回頭再想臊泰，我們?yōu)槭裁匆S機(jī)播放？因為我們不知道要聽什么蚜枢，我們想要一個隨性的播放列表缸逃，我們不想專門聽某一位歌手的或某一張專輯的曲目针饥，我們不想按照平常循環(huán)的順序播放，我們想換換口味有點新意需频，所以我們把這個選擇權(quán)交給軟件本身去做丁眼，如果軟件接連給你播放同一個歌手或同一張專輯的曲目，那就違背我們隨機(jī)的目的了贺辰。所以好的隨機(jī)播放列表應(yīng)該做到均衡分布户盯，同一個流派嵌施、同一個歌手饲化、同一種專輯下的音樂彼此之間相距越遠(yuǎn)越好。
還是上面這個例子吗伤，好的播放列表應(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播放算法
那么如何生成上面這個均衡的播放列表呢吃靠？博主Martin Fiedler給了一個思路。
1）將列表中的歌曲按流派足淆、歌手巢块、專輯等邏輯范式分組，給這個組里的音樂設(shè)定一個隨機(jī)播放順序巧号；
2）接下來把每個分組的曲目通過合并算法組成一個完整的播放列表族奢。
很簡單吧，僅僅兩步而已丹鸿。接下來看看合并算法是怎么一回事越走。假設(shè)在第一步我們得到了下面的分組：
將每個分組擴(kuò)充到和最大分組相等的長度，比如給綠色分組填充8首「靜默」歌曲靠欢，讓該組長度等于12廊敌。填充的時候應(yīng)盡量讓組中的音樂均衡分布列表中。
每個分組都填充完畢后门怪，就開始合并新列表了骡澈，從每個分組的第1列按隨機(jī)順序取出歌曲放在新列表中。
再取出第2列按隨機(jī)順序取出歌曲放在新列表中掷空。
第3列肋殴。需要注意的是，假如第2次取出的是黃-紅-藍(lán)坦弟，第3次取出藍(lán)-黃-紅-綠疼电，那么就會有兩個藍(lán)色分組的歌曲接連出現(xiàn)的情況，這個時候需要把第3次拿出的歌曲首尾互換减拭，最后得出綠-黃-紅-藍(lán)的順序蔽豺。
這就是shuffle播放背后的大概邏輯了，難的不是合并算法拧粪，而是填充分組的算法修陡，個人感覺沧侥。
參考資料：
