问题:生成一个从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()
1条答案
按热度按时间yquaqz181#
筛子本身需要指数级的时间来计算越来越多的素数,所以绘制筛子的纯运行时间应该会得到一条大致的直线。
在您的绘图副本中,它看起来实际上随着时间的推移变得更糟了,但是当我运行您的脚本时,它并不是完全笔直的,而是接近对数刻度上的直线。然而,在开始时有一点弯曲,就像您的结果一样。
这是有意义的,因为sieve缓存了以前的结果,但最初它从中获得的好处很少,而且设置缓存和增加缓存大小的开销很小,随着时间的推移,缓存大小会逐渐减小,更重要的是,实际调用sieve例程的开销很大。此外,这种类型的性能测量对系统上发生的任何其他事情都非常敏感。包括Python和IDE正在执行的任何操作
下面是您的代码,其中添加了一些代码,用于在不同的初始运行中循环,在每次运行前预热筛子的缓存--它非常清楚地显示了效果:
这里要吸取的教训是,您需要考虑开销,包括您自己的代码和使用的库,以及围绕它的整个系统:Python VM、IDE、工作站上运行的任何东西、运行它的操作系统、硬件。
上面的测试更好,但是如果你想得到很好的结果,运行整个过程十几次,然后平均出运行的结果。
结果:
第一次