的Python：更快的通用散列函数与内置的库

我想只有基础库来实现通用的散列函数：的Python：更快的通用散列函数与内置的库

我有，因为我无法在有效时间运行这个问题。我知道％很慢所以我已经尝试了以下内容：

((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次（或更多）的此功能，并且我需要所有200000次运行在4秒内完成。这些方法都不是在那个球场中（需要几分钟）

来源

2017-09-29 Stanley Cup Phil

你测量了什么样的表现，你需要什么？ –

请参阅我的编辑 –

如何使用numpy？你可以创建一个x的向量（如果需要的话也可以是a或b），并且一次运行几个10000（或更多）的计算作为向量算术。 –

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

如果你真的需要的性能，而你与将适合C水平基本类型工作的类型，你可以从写一个Python C扩展所有的值uint64_t转换为size_t，Py_hash_t，受益，或任何适合你的问题，并作为一组批量转换为C类型，C级数学，然后单一转换回Python，节省一堆字节码和中间值（即时抛出）。

如果值太大，不适合用C原语，GMP类型是一个选项（看mpz_import和mpz_export高效转换从PyLong到mpz_t和背面），但看到大储蓄的可能性下降;一般来说，GMP的数学运算速度更快，并且可以对数字进行变异，而不是创建和销毁大量的临时数据，但即使使用mpz_import和mpz_export，Python和GMP类型之间的转换成本也可能会节省大部分成本。

来源

2017-09-29 03:09:52 ShadowRanger

的Python：更快的通用散列函数与内置的库

回答

相关问题