假设我有一个有序的频率列表，例如 [1, 1, 2]。我希望能够从这个列表中快速抽样，选择一个选项的概率与其值成正比。
The Alias method让我们用 O(n) 的构建时间和 O(1) 的查询时间来做这个采样。我对这个问题的版本很感兴趣，我们也支持更新或插入这个列表。
这里有一些想法:
- 一个增强的 BST 可以用 O(log(n)) 的所有操作来做到这一点
- 您可以使用分层数据结构，其中有 n/log(n) 个大小为 log(n) 的 block 。每个 block 都存储为一个增强的 BST，顶层数据结构是别名方法。选择一个 BST 需要 O(1)，在其中选择需要 O(log(log(n)))，所以你的查询时间是 O(log(log(n)))。每当发生更新时，您都需要完全重建顶层结构，这需要 O(n/log(n)) 时间。
有没有更快的解决方案？
最佳答案
论文"Dynamic Generation of Discrete Random Variates" by Matias, Vitter, and Ni描述了如何在恒定的预期更新和查询时间内执行此操作。这些技术一点都不简单!
关于algorithm - 动态加载骰子的数据结构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40622450/