为了提前总结这个问题,我正在寻找一个适合在蒙特卡洛模拟中生成伪随机数的好的散列函数。这意味着它应该相当快(因此排除了 md5 之类的东西),但具有足以用于数值应用的统计数据。
原因是有时,在编写模拟代码时,我觉得需要生成一个函数,以伪随机的方式将一组对象映射到 0 和 1 之间的浮点数。这样的函数可能总是将 Numpy 数组映射[1.0, 2.0, 3.0]
到 0.11214,但在不同的模拟运行中,可能会生成不同的函数,它总是映射[1.0, 2.0, 3.0]
到 0.92546。输入集可能不包含数组,但如果包含,那么重要的是不要忽略顺序,即[1.0, 2.0, 3.0]
应该[1.0, 3.0, 2.0]
返回不同的结果。
似乎有一些不同的技术术语可以生成这样的随机函数:根据实现的细节,它可以称为通用散列或伪随机函数族。当然,实现这一点的一种方法是使用良好的散列函数。可以使用“salting”生成不同的伪随机函数,即在运行散列算法之前为每个对象添加一个固定字符串。更改此前缀会给出不同的伪随机函数。
诸如 md5 之类的安全散列算法将具有出色的统计数据,但在蒙特卡洛模拟中太慢而无法实用。当然,存在许多可能适合使用的“快速散列”算法(即非安全散列算法)。然而,问题是我无法找到对任何此类算法在数值计算适用性方面的良好分析。
这很重要,因为大多数快速散列算法都是为在文件系统中使用而设计的。通常,描述散列函数的论文会根据它们在此类应用程序中的性能来评估它们。但是,对此的要求与数值模拟的要求有很大不同。我不是专家,但本质区别在于,对于文件系统,我们非常关心避免冲突,而对于数值算法,我们最关心输出分布的均匀性和函数输出的统计独立性,即使给定函数的输入密切相关。
这些目标相互关联(安全散列算法在这三个目标上都得分很高),但它们并不相同。作为一个简单的例子来说明这一点,使用 Python 的内置哈希算法模 1000,映射"aaa"
到340、343、342、337、336"aab"
和339。这些数据中没有冲突,但结果是显然既不是均匀分布的,也不是独立的。"aac"
"aad"
"aae"
"aaf"
因此,我正在寻找有关在蒙特卡洛模拟中使用哪种散列算法的任何建议,以便在速度和适合数字的统计数据之间取得良好的折衷。在理想的世界中,也会有一个带有 Python 绑定的现有 C 实现;如果像 Numpy 数组这样的对象可以直接散列,而不是首先必须将它们转换为字符串,那也是理想的。理想情况下,我想要一个我可以信任的现成解决方案,就像我信任 Numpy 的随机数生成器一样。但是,如果有必要,我不介意自己实现它 - 重要的是找到一个已经过正式评估的算法,它适用于数值应用程序,而不是用于文件系统。