Skip to main content
 首页 » 编程设计

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

2024年12月31日7JeffreyZhao

我已经实现了 Luhn 算法的校验和部分的两个 Python 版本。除了如何计算第二个求和之外,代码片段几乎相同。它与通常的实现不同,因为它计算总和,然后使用校正因子更新总和(如 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 的内置 sum 会提供比自己进行循环更好的性能,尤其是对于这种大小的列表。

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


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

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)] 

随机数5的结果更符合预期,但对于更大的测试仍然很奇怪。

>>> %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) 

请您参考如下方法:

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