为尾随0位的模实现更快的divmod（）
shift-divmod的Python项目详细描述
| Info: | This is the README file for ShiftDivMod. |
|---|---|
| Author: | Shlomi Fish <shlomif@cpan.org> |
| Copyright: | © 2020, Shlomi Fish. |
| Date: | 2020-09-20 |
| Version: | 0.4.3 |
目的
这个发行版实现了更快的divmod（）（和.mod()）操作 对于有大量尾随0位的模（其中div/mod基 对于整数n，可以被2 ** n整除。在
它应该产生与内置的divmod（）函数相同的结果 正分子（它对负分子的行为目前是 未测试和未定义）。在
还提供了到C和gmplib（=GNU多精度）的端口： https://github.com/shlomif/shift_divmod/tree/master/gmp-shift_divmod
安装
pip3安装shift_divmod
使用
from shift_divmod import ShiftDivMod base = 997 shift = 1200 modder = ShiftDivMod(base, shift) # Alternative constructor which may require more # work and eventualy calls the default constructor modder = ShiftDivMod.from_int(base << shift) x = 10 ** 500 # Same as divmod(x, (base << shift)) print( modder.divmod(x) )
注释
从中派生出此分布的代码被建议为 内置cpython3潜在改进的概念证明 此处的操作：https://bugs.python.org/issue41487。但是，更改cpython3 就这样被拒绝了。在
libdivide（https://github.com/ridiculousfish/libdivide）提供了一个 不同的，但也很有趣的优化划分的方法。在
基准：
在我的系统上，我在运行后得到了这些结果 python3 code/examples/shift_divmod_example.py bench（已重新格式化 为清楚起见）：
^{pr2}$可以注意到，基于shift_divmod的版本比 它比只完成1000次迭代中的25次的内置nops快得多 在被打断之前。注意，对于这个用例，使用GMP的模幂 似乎更快。在
对于C和gmplib版本：
- mpz_mod运行基准测试大约需要160秒。在
- shift_divmod运行基准测试大约需要35秒。在
- pypy3在25秒内运行纯Python代码（！）。在
秘方：
代码利用了bitwise operations 速度很快，这段代码中出现了神奇的效果（为了清晰起见，添加了一些注释）：
# Precalculating the object's field so that:
# self.shift : a non-negative integer signifying the bit shift
# self.base : a non-negative integer which is shifted to
# form the modulu
# self.n = self.base << self.shift
# self.mask = ((1 << self.shift) - 1)
def divmod(self, inp):
"""calculate divmod(inp, self.n)"""
if inp < self.n:
return 0, inp
div, mod = divmod((inp >> self.shift), self.base)
return div, ((mod << self.shift) | (inp & self.mask))
（或等效但更官僚的C和gmplib代码。）
版权
版权所有©2020，Shlomi Fish。 版权所有。在
以源代码和二进制形式重新分发和使用，有无 允许修改，前提是下列条件 会议：
- 源代码的再分配必须保留上述版权 注意，此条件列表和以下免责声明。在
- 二进制形式的再分配必须复制上述版权 注意，此条件列表和以下免责声明 分发时提供的文件和/或其他材料。在
- 既没有这个软件的作者的名字也没有 软件可能被用来宣传这个软件 从本软件衍生而来的产品，未经事先书面说明 同意。在
本软件由版权所有人和贡献者提供 “原样”和任何明示或暗示的保证，包括但不 仅限于对适销性和适用性的默示保证 一个特殊的目的被否认。在任何情况下，版权 所有人或出资人对任何直接的、间接的、偶然的， 特殊、惩戒性或后果性损害（包括但不包括 仅限于采购替代货物或服务；丧失使用， 数据或利润；或业务中断） 责任理论，无论是合同、严格责任还是侵权 （包括疏忽或其他原因）在使用过程中产生的 即使被告知有这种损坏的可能性。在
- 项目
标签：
欢迎加入QQ群-->： 979659372
