在过去的几天里，我一直致力于改进 python 函数的运行时间，这需要多次使用余数函数 (%)。我的主要测试用例是超过 80,000 个元素的 numpy 数组(单调递增)，有 10000 次迭代，尽管我也尝试过各种其他大小。

最终我达到了余数函数成为主要瓶颈的地步，并尝试了各种解决方案。这是我在运行以下代码时发现的行为:

import numpy as np
import time

a = np.random.rand(80000)
a = np.cumsum(a)
d = 3
start_time1 = time.time()
for i in range(10000):
    b = a % d
    d += 0.001
end_time1 = time.time()
d = 3
start_time2 = time.time()
for i in range(10000):
    b = a - (d * np.floor(a / d))
    d += 0.001
end_time2 = time.time()
print((end_time1 - start_time1) / 10000)
print((end_time2 - start_time2) / 10000)

输出是:

0.0031344462633132934
0.00022937238216400147

将数组大小增加到 800,000 时:

0.014903099656105041
0.010498356819152833

(对于这篇文章，我只为实际输出运行了一次代码，同时试图理解我一直得到这些结果的问题。)

虽然这解决了我的运行时问题 - 我很难理解为什么。我错过了什么吗？我能想到的唯一区别是额外函数调用的开销，但第一种情况非常极端(1.5 倍的运行时间也不够好)，如果是这种情况，我会认为存在np.remainder 函数毫无意义。

编辑: 我尝试使用非 numpy 循环测试相同的代码:

import numpy as np
import time


def pythonic_remainder(array, d):
    b = np.zeros(len(array))
    for i in range(len(array)):
        b[i] = array[i] % d

def split_pythonic_remainder(array, d):
    b = np.zeros(len(array))
    for i in range(len(array)):
        b[i] = array[i] - (d * np.floor(array[i] / d))

def split_remainder(a, d):
    return a - (d * np.floor(a / d))

def divide(array, iterations, action):
    d = 3
    for i in range(iterations):
        b = action(array, d)
        d += 0.001

a = np.random.rand(80000)
a = np.cumsum(a)
start_time = time.time()
divide(a, 10000, split_remainder)
print((time.time() - start_time) / 10000)

start_time = time.time()
divide(a, 10000, np.remainder)
print((time.time() - start_time) / 10000)
start_time = time.time()
divide(a, 10000, pythonic_remainder)
print((time.time() - start_time) / 10000)

start_time = time.time()
divide(a, 10000, split_pythonic_remainder)
print((time.time() - start_time) / 10000)

我得到的结果是:

0.0003770533800125122
0.003932329940795899
0.018835473942756652
0.10940513386726379

我觉得有趣的是，在非 numpy 的情况下，情况正好相反。

最佳答案

我最好的假设是您的 NumPy 安装在 % 计算中使用了未优化的 fmod。原因如下。

首先，我无法在 NumPy 1.15.1 的普通 pip 安装版本上重现您的结果。我只得到大约 10% 的性能差异(asdf.py 包含您的计时代码):

$ python3.6 asdf.py
0.0006543657302856445
0.0006025806903839111

我可以从克隆复制 v1.15.1 的手动构建 (python3.6 setup.py build_ext --inplace -j 4) 的主要性能差异不过，NumPy Git 存储库的:

$ python3.6 asdf.py
0.00242799973487854
0.0006397026300430298

这表明我的 pip-installed 构建的 % 比我的手动构建或您已安装的优化更好。

看看引擎盖下，看看 implementation 很诱人NumPy 中的浮点 % 并将减速归咎于 unnecessary floordiv calculation (npy_divmod@c@ 计算 // 和 %):

NPY_NO_EXPORT void
@TYPE@_remainder(char **args, npy_intp *dimensions, npy_intp *steps, void *NPY_UNUSED(func))
{
    BINARY_LOOP {
        const @type@ in1 = *(@type@ *)ip1;
        const @type@ in2 = *(@type@ *)ip2;
        npy_divmod@c@(in1, in2, (@type@ *)op1);
    }
}

但在我的实验中，移除 floordiv 并没有带来任何好处。编译器优化出来看起来很容易，所以它可能被优化掉了，或者它可能只是运行时的一小部分。

我们只关注 npy_divmod@c@ 中的一行，而不是 floordiv，fmod 调用:

mod = npy_fmod@c@(a, b);

这是在特殊情况处理和调整结果以匹配右侧操作数的符号之前的初始余数计算。如果我们在我的手动构建中比较 % 和 numpy.fmod 的性能:

>>> import timeit
>>> import numpy
>>> a = numpy.arange(1, 8000, dtype=float)
>>> timeit.timeit('a % 3', globals=globals(), number=1000)
0.3510419335216284
>>> timeit.timeit('numpy.fmod(a, 3)', globals=globals(), number=1000)
0.33593094255775213
>>> timeit.timeit('a - 3*numpy.floor(a/3)', globals=globals(), number=1000)
0.07980139832943678

我们看到 fmod 似乎负责几乎整个 % 的运行时。

我没有反汇编生成的二进制文件，也没有在指令级调试器中单步执行它以查看究竟执行了什么，当然，我无权访问您的机器或您的NumPy 的副本。尽管如此，从上述证据来看，fmod 似乎很可能是罪魁祸首。

关于python - numpy 数组上的余数函数 (%) 运行时间远长于手动余数计算，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52242832/