algorithm - 在天体自动点唱机上实现随机播放

Question

如何为“Celestial Jukebox”实现随机播放？

更准确地说，在每个时间 t，返回一个介于 0..n(t) 之间的均匀随机数，使得整个序列中没有重复，n() 随着时间的推移而增加。

对于具体示例，假设有一个固定费率音乐服务，它允许通过从 0 开始的索引号播放目录中的任何歌曲。每隔一段时间，就会添加新歌曲，从而增加索引编号的范围。目标是每次播放一首新歌(假设目录中没有重复歌曲)。

一个理想的解决方案在现有硬件上是可行的——我如何将 600 万首歌曲的列表塞进 8MB 的 DRAM 中？同样，高歌曲数会加剧 O(n) 选择时间。

-- 对于 LCG 生成器，给定 0..N₀ 上部分耗尽的 LCG，能否将其转换为 0..N₁ 上的不同 LCG (其中 N1 > N0)，即不重复已用完的序列。
- 检查一首特定歌曲是否已经播放似乎迅速失控，尽管这可能是唯一的方法？是否有有效的数据结构？

Answer 1

我喜欢做那种非重复随机选择的方式是有一个列表，每次我在[0-N)之间随机选择一个项目，我删除它从那个名单。在您的情况下，随着新项目被添加到目录中，它也将被添加到 not-yet-selected 列表中。结束后，只需将所有歌曲重新加载回列表即可。

编辑:

如果您考虑 v3 的建议，这可以在 O(N) 初始化步骤之后基本上在 O(1) 时间内完成。保证不重复随机选择。

回顾一下:

1. 将初始项目添加到列表
2. 随机选择索引 i(来自 [0,N) 的集合)
3. 删除索引 i 处的项目
4. 将 i 处的空洞替换为 Nth 项(如果 i == Nth 则为 null)并递减 N
5. 对于新项目，只需追加到列表末尾并根据需要增加 N
6. 如果您曾经播放过所有歌曲(我怀疑您是否有 600 万首歌曲)，请将所有歌曲添加回列表，起泡、冲​​洗并重复。

由于您正在尝试处理相当大的集合，因此我建议使用数据库。一个简单的表格，基本上有两个字段:id 和“pointer”(其中“pointer”告诉您要播放的歌曲可能是一个 GUID、文件名等，这取决于你想怎么做)。在 id 上有一个索引，您应该在应用程序运行之间获得非常好的性能和持久性。

编辑 8MB 限制:

嗯，这确实让它变得有点困难......在 8 MB 中，您可以使用 32 位 key 存储最多 ~2M 条目。

所以我建议预先选择接下来的 2M 条目。如果用户一生播放 2M 歌曲，该死!要预先选择它们，请使用上述算法执行预初始化步骤。我要做的一个改变是，当你添加新歌时，掷骰子看看你是否想随机将这首歌添加到混音中。如果是，则选择一个随机索引并将其替换为新歌曲的索引。