Spotify: 曲をシャッフルするのは単純にランダムではいけない

http://labs.spotify.com/2014/02/28/how-to-shuffle-songs/

1 comment | 3 points | by WazanovaNews 3年弱前 edited


Jshiike 3年弱前 edited | ▲upvoteする | link

SpotifyのLukáš Poláčekがプレイリストをシャッフルするロジックを改善した取り組みを紹介しています。

以前のロジック

ランダムアルゴリズムには、Fisher-Yates shuffleを利用。

順次再生する曲を選ぶロジック同士には依存関係がなく、完全にランダムに選択される。よって、同じアーティストの別の曲が次に再生されることも可能性としてはある。

これはギャンブラーの誤謬と呼ばれる現象。例えば、コイントスで表が連続してでると、次は裏が出ると思いがちであるが、常に確率は1/2である。従前の結果が次の結果に影響を与えると考えてしまう。よって、「曲がシャッフルされて、まずアーティストAの歌が再生されたら、次に再生されるのはアーティストA以外のものになる可能性が高くなるだろう。」という予想は、確率計算上は誤っている。(けど、Spotifyユーザのサービスに対する期待としては正しい。)

新しいロジック

Martin FiedlerのThe art of shuffling musicはこの問題を解決しているが、アルゴリズムが複雑で実行時間が遅くなってしまう。

考え方はディザーに似ている。例えば、この画像をピクセルごとに白もしくは黒だけを使って表現するかたち変える。ランダムサンプリングを用いて、ある特定のピクセルが80%シェードのグレー色であれば、80%の確率で黒が適用され、20%の確率で白が適用されるとする。そうすると結果は、この画像のように、黒色がクラスター状に固まって、かつ空白のスペースも目立ってしまう。しかし、Floyd-Steinbergディザリングアルゴリズムを使うと、この画像のようにうまく白黒画像に変換できる。

このアルゴリズムが黒色のクラスターをうまく分散させることを、曲のシャッフルに応用してみることにした。プレイリストの中で、それぞれのアーティストの複数の楽曲が均等に分散するようにセットし、全アーティスト分をまとめてみると、この図のように、ユーザが期待する「ランダム」な表示ができた。

例えば、4曲もっているアーティストは、プレイリストの中で、各曲が25%の距離で仮配置され、他のアーティストの曲がセットされる位置との絡みで、後ほど場所が若干調整される。1曲のみのアーティストは、プレイリスト全体の中でランダムに配置される場所が決められる。

このアルゴリズムは数行で書くことができ、実行も早い。デスクトップの本番環境にはリリース済で、他のクライアントにも順次展開される。


Scaling Agile @ Spotify を読み直す(その1)


#spotify

Back