类似于为什么在Python3中使用True比使用1慢,但我正在使用pypy3并且没有使用sum函数。
def sieve_num(n):
nums = [0] * n
for i in range(2, n):
if i * i >= n: break
if nums[i] == 0:
for j in range(i*i, n, i):
nums[j] = 1
return [i for i in range(2, n) if nums[i] == 0]
def sieve_bool(n):
nums = [False] * n
for i in range(2, n):
if i * i >= n: break
if nums[i] == False:
for j in range(i*i, n, i):
nums[j] = True
return [i for i in range(2, n) if nums[i] == False]
sieve_num(10**8)
耗时 2.55 秒,而 sieve_bool(10**8)
耗时 4.45 秒,这是一个明显的差异。
我怀疑 [0]*n
比 [False]*n
更小,并且更适合放入缓存中,但是在 PyPy 中不支持使用 sys.getsizeof
和 vmprof 行剖析。我能获得的唯一信息是,sieve_num
的 <listcomp>
花费了 116 毫秒(总执行时间的 19%)而 sieve_bool
的 <listcomp>
花费了 450 毫秒(总执行时间的 40%)。
使用 Python 3.6.9 实现的 PyPy 7.3.1 在搭载有 Intel i7-7700HQ 和 24 GB RAM 的 Ubuntu 20.04 上运行。在 Python 3.8.10 下,sieve_bool
只比较慢一点。
if not num[i]
这样的写法仍然会影响性能。 - qwr