4

「Celestial Jukebox」のシャッフルをどのように実装しますか?

より正確には、各時刻 t で、0..n(t) の間の一様乱数を返します。これにより、シーケンス全体で繰り返しがなく、n() が時間とともに増加します。

具体的な例として、カタログ内の任意の曲を 0 ベースのインデックス番号で再生できる定額音楽サービスを想定します。インデックス番号の範囲を広げる新しい曲が頻繁に追加されます。目標は、毎回新しい曲を再生することです (カタログに重複がないことを前提としています)。

理想的なソリューションは、既存のハードウェアで実行可能です。8 MB の DRAM に 600 万曲のリストをどのように詰め込むのでしょうか? 同様に、曲数が多いと、O(n) 選択のタイミングが悪化します。

-- LCG ジェネレーターの場合、0..N 0で部分的に消耗した LCG を指定すると、0..N 1 (N1 > N0) で消耗したシーケンスを繰り返さない別の LCG に変換できます。
-- 特定の曲がすでに再生されているかどうかを確認することは、急速に手に負えなくなっているようですが、これが唯一の方法かもしれません。これに効率的なデータ構造はありますか？

4

5 に答える 5

3

そのような繰り返しのないランダムな選択を行うのが好きな方法は、リストを作成することです. の間[0-N)でアイテムをランダムに選択するたびに、そのリストから削除します. あなたの場合、新しいアイテムがカタログに追加されると、まだ選択されていないリストにも追加されます。最後まで再生したら、すべての曲をリストに再読み込みします。

編集：

v3の提案を考慮に入れると、これは基本的に初期化ステップO(1)後の時間で実行できます。O(N)繰り返さないランダム選択を保証します。

要約は次のとおりです。

  1. 初期アイテムをリストに追加する
  2. インデックスiをランダムに選択 (のセットから[0,N))
  3. インデックスのアイテムを削除i
  4. の穴を項目に置き換えi (Nthまたは null の場合は null i == Nth)、デクリメントします。N
  5. 新しいアイテムの場合は、リストの最後に追加し、必要に応じてインクリメントNします
  6. すべての曲を再生できるようになったら (6M の曲があるかどうかは疑問です)、すべての曲をリストに追加し、泡立て、すすぎ、繰り返します。

かなり大きなセットを処理しようとしているので、DB の使用をお勧めします。基本的に 2 つのフィールドを持つ単純なテーブル:idと " pointer" (ここで、" pointer" は、再生する曲を示します。これは、実行方法に応じて、GUID、ファイル名などになります)。インデックスをオンにするidと、アプリケーションの実行間の永続性により、非常に適切なパフォーマンスが得られるはずです。

8MB制限の編集：

うーん、これは少し難しくなります... 8 MB では、32 ビット キーを使用して最大 ~2M のエントリを保存できます。

したがって、次の 2M エントリを事前に選択することをお勧めします。ユーザーが生涯で 200 万曲を再生した場合、くそっ！それらを事前に選択するには、上記のアルゴリズムを使用して pre-init ステップを実行します。私が行う 1 つの変更は、新しい曲を追加するときにサイコロを振って、その曲をランダムにミックスに追加するかどうかを確認することです。はいの場合は、ランダムなインデックスを選択して、新しい曲のインデックスに置き換えます。

于 2009-05-13T20:05:20.583 に答える
1

600 万曲に対して 8MB という制限があるため、各曲の 32 ビット整数を 1 つでも格納する余地がないことは明らかです。リストをディスクに保存する準備ができている場合を除きます (その場合は、以下を参照してください)。

新しいアイテムをすぐにシャッフルに追加するという要件を削除する準備ができている場合は、現在の曲のセットに対して LCG を生成し、それが使い果たされたら、それ以降に追加された曲のみに対して新しい LCG を生成できます。始めた。新しい曲がなくなるまで、すすいで繰り返します。また、保存せずに任意の範囲で推測不可能な順列を生成するこのかなりクールなアルゴリズムを使用することもできます。

600 万曲の 8MB RAM の要件を緩和する準備ができている場合、またはディスクに移動する準備ができている場合 (たとえば、メモリ マッピングによって)、最初に 1..n からシーケンスを生成し、fisher- でシャッフルすることができます。新しい曲が追加されるたびに、これまでに再生されていないセクションからランダムな要素を選択し、そこに新しい ID を挿入し、元の ID をリストの最後に追加します。

計算効率をあまり気にしない場合は、すべての曲のビットマップを保存し、まだ再生していない曲が見つかるまで、ID を均一に無作為に繰り返し選択することができます。これには、最後の曲を見つけるのに (平均で) 600 万回の試行が必要ですが、最新の CPU では依然として非常に高速です。

于 2009-05-13T23:08:52.470 に答える
0

setErich のソリューションはおそらく特定のユース ケースに適していますが、Python の a やhashset<int>C++の aなどのハッシュベースの構造を使用すると、曲が既に再生されているかどうかを確認するのが非常に高速です (償却された O(1)) 。

于 2009-05-13T20:12:30.930 に答える
0

配列内でリンクされたリストを使用できます。最初のプレイリストを作成するには、次のようなものを含む配列を使用します。

 struct playlistNode{
  songLocator* song;
  playlistNode  *next;
};
struct playlistNode arr[N];

また、「ヘッド」および「フリーリスト」ポインタも保持します。

2 つのパスで
入力します。
2. すべてのインデックスをランダムに繰り返し、nextポインタを埋めます。

再生された曲の削除は O(1):

head=cur->next;
cur->song=NULL;
freelist->next = freelist;
cur->next=freelist;
freelist=cur;

新しい曲の挿入も O(1) です。配列インデックスをランダムに選択し、新しいノードにパッチを適用します。

node = freelist;
freelist=freelist->next;
do {
i=rand(N);   
} while (!arr[i].song);  //make sure you didn't hit a played node
node->next = arr[i].next;
arr[i].next=node;
于 2009-05-13T21:10:55.797 に答える
0

単純に 1 から n までの数列を生成し、Fisher-Yates shuffle を使用してシャッフルすることができます。そうすれば、n に関係なく、シーケンスが繰り返されないことを保証できます。

于 2009-05-13T20:23:24.190 に答える