python - "Deterministic"伪随机数生成

Question

我处于一种情况，我需要生成一个非常大的(~10^16 个元素)具有特定随机稀疏模式的随机矩阵。显然存储所有这些元素是完全不可行的。在任何给定时间只需要少数元素，因此可以按需绘制它们 - 但是，一旦存储了一个元素，以后可能会需要它，使用相同的值很重要。即，不能丢弃元素并随机重绘 - 一旦绘制了随机元素，就需要将其保存。

根据问题本身，可能有一些聪明的方法可以解决这个问题，我不会讨论。然而，一位同事说，应该可以通过使用伪随机数生成器根据需要确定性地生成这些随机数，种子由矩阵中的索引给出，即使用 i + N*j 作为元素(i, j) 矩阵的大小为 N*N。这不会调用 rand() 函数，而是使用带有特定参数的底层伪随机函数来确定性地生成先前绘制的随机值。这样就不需要保存任何数字，并且可以根据需要确定性地重新绘制它们。

我对 PRG 的理解是，对于随机出现的数字序列，您必须修复种子。上面的方法有意义吗？在我看来，这就像反复重新播种 PRG 并只取第一个元素。

Answer 1

不是一个精确的答案，但有一些尝试。

散列函数似乎是实现您的目标的一种简单而有效的方法。

Here有一些关于整数到整数哈希函数的好主意。

从这篇文章我尝试:

from numba import uint64, njit 
import pylab as pl

@njit(uint64(uint64,uint64))    
def hash64(i,j) :
    x= i + (j << 32)
    x = (x ^ (x >> 30)) * (0xbf58476d1ce4e5b9);
    x = (x ^ (x >> 27)) * (0x94d049bb133111eb);
    x = x ^ (x >> 31);
    return x;  

n=1000    
im=[[hash64(i,j) for i in range(n)] for j in range(n)]
pl.subplot(121)
pl.imshow(im)
pl.colorbar()
pl.subplot(122)
pl.hist(np.array(im).ravel(),bins=100)
pl.show()  

这个 numba hash64 函数在大约 200 ns 内计算出哈希码。

这个图(即使它什么也没展示)表明这个函数可能是一个很好的候选者。

相比之下，python 哈希函数(hash((i,j)) on tuple)没有通过测试:

这里是 Knuth 生成器:

还有一些基准:

In [61]: %timeit hash64(0,1)
215 ns ± 9.11 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [62]: %timeit np.random.seed(0+1<<30);a=np.random.randint(2**30)
4.18 µs ± 126 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [63]:%timeit  hash((0,1))
102 ns ± 19.5 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)