Python:具有内置库的更快的通用哈希函数

Question

我正在尝试仅使用基本库来实现通用哈希函数:

我遇到了问题，因为我无法在有效时间内运行它。我知道 % 很慢，所以我尝试了以下方法:

((a * x + b) % P) % n

divmod(divmod(a * x + b, P)[1], n)[1]

subeq = pow(a * x + b, 1, P)
hash = pow(subeq, 1, self.n)

所有这些功能对于我想要做的事情来说都太慢了。有没有一种更快的方法来仅使用我不知道的基本库进行 mod 除法？

编辑 详细来说，我将运行此函数大约 200000 次(或更多)，并且我需要在 4 秒内完成所有 200000 次运行。这些方法都不是那么简单(需要几分钟)

Answer 1

在纯 Python 代码中你不会做得比 ((a * x + b) % P) % m 更好； Python 解释器的开销将成为你最大的瓶颈；是的，如果您确保 m 是 2 的幂，则可以预先计算 mm1 = m - 1 并将计算更改为 ((a * x + b) % P) & mm1 ，用更便宜的位掩码操作替换更昂贵的余数操作，但除非 P 很大(最少数百位)，否则解释器开销可能会超过余数和位掩码之间的差异。

如果您确实需要性能，并且您正在使用的类型适合 C 级原始类型，那么您可能会受益于编写将所有值转换为 size_t 的 Python C 扩展， Py_hash_t 、 uint64_t 或任何适合您问题的内容，并将数学作为一组批量转换为 C 类型、C 级数学，然后一次转换回 Python int ，保存一堆字节代码和中间值(立即扔掉) )。

如果值太大而无法适应 C 原语，则可以选择 GMP 类型(查看 mpz_import 和 mpz_export，以实现从 PyLong 到 mpz_t 的高效转换，然后再返回)，但看到大量节省的可能性会下降；一般来说，GMP 的数学运算速度更快，并且可以就地改变数字，而不是创建和销毁大量临时数字，但即使使用 mpz_import 和 mpz_export ，Python 和 GMP 类型之间的转换成本也可能会消耗掉大部分节省的成本。