performance - 独特的随机数算法

Question

我想要一个算法/函数，给定一个数字 N，在恒定时间内生成从 0 到 N - 1 的随机数。在第 N 次调用之后，该函数可以随心所欲地执行操作。此外，重要的是算法在请求时生成数字而不是使用混洗，因为我可能(并且在一般情况下不需要)不需要完整的数字列表。最好的方法是什么？

(可选阅读)我想到了一组哈希数字，并一次提取一个数字，但这需要先将所有元素(我通常不需要)插入哈希集中.. .这行不通...啊

提前感谢您的帮助。

Answer 1

修改Fisher–Yates shuffle通过用只存储已移动元素的映射替换数组。在 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) 个字。根据对数因子，这是最优的。