python – Eratosthenes的筛子速度差异
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python – Eratosthenes的筛子速度差异，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2085字，纯文字阅读大概需要3分钟。
内容图文
为什么第一个比第二个快得多？我知道存储素数为1和0更简单,但速度增加是荒谬的.最后,它仍然会列出200万个项目的长度,如何在1s中编译可以远程实现？
def prime_sieve(limit):
primes = [1 for x in xrange(limit)]
primes[0] = 0
primes[1] = 0
imax = int(math.sqrt(limit) + 1)
i = 2
while (i < imax):
j = i + i
while j < limit:
primes[j] = 0
j += i
while True:
i += 1
if primes[i] == 1:
break
return primes
s = prime_sieve(2000000)
print(sum(i for i in xrange(len(s)) if s[i] == 1))
-----------------------------------------------------------
def sieve(max):
primes = range(2, max+1)
for i in primes:
j = 2
while i * j <= primes[-1]:
if i * j in primes:
primes.remove(i*j)
j += 1
return primes
count = 0
for x in sieve(2000000):
count += x
print count
解决方法:
因为当你删除东西时,你不能再使用direct addressing了.直接寻址是Eratosthenes速度筛选的关键(类似于integer sorting的速度优势,而不是基于比较的排序).
在第一个代码中,primes [j] = 0是O(1)操作.但在第二个中,primes.remove(i * j)是O(n)操作(根据this).
你也开始枚举i的倍数为2 * i而不是i ^ 2.与上述相比,它不是一个问题.
要正确比较算法速度,请始终比较empirical orders of growth.这是the results：
# First code:
# --i+i-- # --i*i--
# N n time-space ~ n^ # N n time-space ~ n^
# 10k 1229 0.02s-7.9M #
# 2mln 148933 1.13s-7.9M # 2mln 148933 1.12s-7.9M
# 4mln 283146 2.30s-7.9M n^1.11 # 4mln 283146 2.25s-7.9M n^1.09
# 8mln 539777 4.58s-7.9M n^1.07 # 8mln 539777 4.38s-7.9M n^1.03
# 16mln 1031130 9.12s-7.9M n^1.06 # 16mln 1031130 8.82s-7.9M n^1.08
# Second code:
# --j=2-- # --j=i--
# 5k 669 0.35s-7.9M # 5k 669 0.28s-7.9M
# 10k 1229 1.37s-7.9M n^2.24 # 10k 1229 1.16s-7.9M n^2.34
# 20k 2262 5.21s-7.9M n^2.19 # 20k 2262 4.66s-7.9M n^2.28
# 30k 3245 11.76s-7.9M n^2.26 # 30k 3245 11.24s-7.9M n^2.44
N是上限,n是它下面的素数.指数当然是近似的,它们的增量不是衡量的,但它们确实给了我们一般的图景.二次(或更差)算法肯定与线性算法有很大不同.
内容总结
以上是互联网集市为您收集整理的python – Eratosthenes的筛子速度差异全部内容，希望文章能够帮你解决python – Eratosthenes的筛子速度差异所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。