python 增加列表大小的计时操作-意外行为

jvlzgdj9  于 2022-11-28  发布在  Python
关注(0)|答案(1)|浏览(143)

问题:生成一个从1到N的素数的Python列表需要多长时间?绘制一个时间与N的关系图。
我用SymPy生成了素数列表,我期望时间单调增加,但为什么会有下降呢?

import numpy as np
import matplotlib.pyplot as plt
from time import perf_counter as timer
from sympy import sieve

T = []
tic=timer()

N= np.logspace(1,8,30)
for Nup in N:
    tic = timer()
    A=list(sieve.primerange(1,Nup))
    toc = timer()
    T.append(toc-tic)
    
plt.loglog(N,T,'x-')
plt.grid()
plt.show()

Time taken to generate primes up to N

yquaqz18

yquaqz181#

筛子本身需要指数级的时间来计算越来越多的素数,所以绘制筛子的纯运行时间应该会得到一条大致的直线。
在您的绘图副本中,它看起来实际上随着时间的推移变得更糟了,但是当我运行您的脚本时,它并不是完全笔直的,而是接近对数刻度上的直线。然而,在开始时有一点弯曲,就像您的结果一样。
这是有意义的,因为sieve缓存了以前的结果,但最初它从中获得的好处很少,而且设置缓存和增加缓存大小的开销很小,随着时间的推移,缓存大小会逐渐减小,更重要的是,实际调用sieve例程的开销很大。此外,这种类型的性能测量对系统上发生的任何其他事情都非常敏感。包括Python和IDE正在执行的任何操作
下面是您的代码,其中添加了一些代码,用于在不同的初始运行中循环,在每次运行前预热筛子的缓存--它非常清楚地显示了效果:

import numpy as np
import matplotlib.pyplot as plt
from time import perf_counter as timer, sleep
from sympy import sieve

for warmup_step in range(0, 5):
    warmup = 100 ** warmup_step
    sieve._reset()  # this resets the internal cache of the sieve
    _ = list(sieve.primerange(1, warmup))  # warming the sieve's cache

    _ = timer()  # avoid initial delays from other elements of the code
    sleep(3)
    print('Start')

    times = []
    tic = timer()

    numbers = np.logspace(1, 8, 30)
    for n in numbers:
        tic = timer()
        _ = list(sieve.primerange(1, n))
        toc = timer()
        times.append(toc - tic)
        print(toc, n)  # provide some visual feedback of speed

    plt.loglog(numbers, times, 'x-')
    plt.title(f'Warmup: {warmup}')
    plt.ylim(1e-6, 1e+1)  # fix the y-axis, so the charts are easily comparable
    plt.grid()
    plt.show()

这里要吸取的教训是,您需要考虑开销,包括您自己的代码和使用的库,以及围绕它的整个系统:Python VM、IDE、工作站上运行的任何东西、运行它的操作系统、硬件。
上面的测试更好,但是如果你想得到很好的结果,运行整个过程十几次,然后平均出运行的结果。
结果:
第一次

相关问题