(I)python 中 Luhn 算法的意外表现

Question

我已经实现了两个 python 版本的 Luhn 算法的校验和部分。除了如何计算第二个求和之外，代码片段几乎相同。它与通常的实现不同，因为它计算总和，然后用校正因子更新总和（如 here 所示）。

def manual_loop(xs):
    differences = (0, 1, 2, 3, 4, -4, -3, -2, -1, 0)
    total = sum(xs) % 10
    for x in xs[len(xs)%2::2]:
        total += differences[x]
    return total % 10

def builtin_loop(xs):
    differences = (0, 1, 2, 3, 4, -4, -3, -2, -1, 0)
    total = sum(xs) % 10
    total += sum(differences[x] for x in xs[len(xs)%2::2])
    return total % 10

然后我在 Ipython 终端中对三个样本使用 timeit 对代码进行计时。

from random import randint
randoms5 = [randint(0, 9) for _ in range(10**5)]
randoms6 = [randint(0, 9) for _ in range(10**6)]
randoms7 = [randint(0, 9) for _ in range(10**7)]

结果如下：

>>> %timeit manual_loop(randoms5)
2.69 ms ± 17 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
>>> %timeit manual_loop(randoms6)
29.3 ms ± 535 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
>>> %timeit manual_loop(randoms7)
311 ms ± 1.52 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>> %timeit builtin_loop(randoms5)
3.31 ms ± 146 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
>>> %timeit builtin_loop(randoms6)
34.8 ms ± 1.31 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
>>> %timeit builtin_loop(randoms7)
337 ms ± 5.69 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

什么给了？我原以为 python 的内置总和会提供比自己进行循环更好的性能，尤其是对于这种大小的列表。

注意：我省略了其他变体，例如手动执行两个求和并交换使用内置求和的求和，因为它们给出的时间要差得多。

编辑：根据要求，我用固定的种子重新运行了测试。

import random
random.seed(42)
randoms5 = [random.randint(0, 9) for _ in range(10**5)]
randoms6 = [random.randint(0, 9) for _ in range(10**6)]
randoms7 = [random.randint(0, 9) for _ in range(10**7)]

randoms5 的结果更符合预期，但对于更大的测试仍然很奇怪。

>>> %timeit manual_loop(randoms5)
3.36 ms ± 346 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

>>> %timeit builtin_loop(randoms5)
3.23 ms ± 76.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

>>> %timeit manual_loop(randoms6)
31.2 ms ± 890 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

>>> %timeit builtin_loop(randoms6)
35.4 ms ± 2.27 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

>>> %timeit manual_loop(randoms7)
311 ms ± 5.43 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>> %timeit builtin_loop(randoms7)
341 ms ± 8.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Answer 1

您的 sum 调用无法避免解释循环。 sum 本身不被解释，但它在 上循环的生成器表达式是 被解释的。生成器表达式比常规 Python 循环具有更高的开销，因为所有的工作都是一遍又一遍地挂起和恢复生成器的堆栈帧。

(I)python 中 Luhn 算法的意外表现

Unexpected performance with Luhn's Algorithm in (I)python

python

python-3.x

performance

ipython

luhn