performance - 独特的随机数算法

Question

我想要一个算法/函数，给定一个数字 N，在恒定时间内生成从 0 到 N - 1 的随机数。在第 N 次调用之后，函数可以随心所欲。此外，算法在请求时生成数字而不是使用改组也很重要，因为我可能（并且在平均情况下）不需要完整的数字列表。最好的方法是什么？

（可选阅读）我想有一个数字哈希集，并一次提取一个数字，但这需要首先将所有元素（我通常不需要）插入哈希集中......这将不工作...啊

感谢您提前提供任何帮助。

Answer 1

通过将数组替换为仅存储已移动元素的地图来修改Fisher-Yates 洗牌。在 Python 中：

import random
class Shuffle:
    def __init__(self, n):
        self.d = {}
        self.n = n
    def generate(self):
        i = random.randrange(self.n)
        self.n -= 1
        di = self.d[i] if i in self.d else i  # idiomatically, self.d.get(i, i)
        dn = self.d[self.n] if self.n in self.d else self.n
        self.d[i] = dn
        self.d[self.n] = di
        return di

实际生成的每个元素的空间使用和摊销的预期运行时间是 O(1) 个字。根据日志因素，这是最佳的。