原则上来讲,同样的算法,如果分别在Python和C++上实现,那么Python的速度肯定比不上C++的。但是Python还被称为“胶水语言”,它允许我们把主要计算的部分用C或C++等高效的语言编写好,然后它作为“粘合剂”把两者粘合在一起。正因为如此,Python才有了各种各样的扩展库,这些库中有不少是用C语言编写的。因此,我们在编写Python程序的时候,如果可以用这些现成的库,速度会快很多。本文就是用Numpy来改进之前的《两百万前素数之和与前两百万素数之和》的计算。

算法本身是没有变的,只是用了Numpy来处理数组计算,代码如下:

小于200万的素数之和:

import time
import numpy as np
start=time.clock()

n=2000000
prime=np.arange(n+1,dtype=np.uint64) 
r=int(np.sqrt(n))

for j in range(2,r+1):
  if prime[j] != 0:
    prime[j*j:n+1:j]=0
print(np.int64(prime.sum()-1))

end=time.clock()
print("time:",end-start)

前200万个素数之和

import time
import numpy as np
start=time.clock()

n=34000000
prime=np.arange(n+1,dtype=np.uint64) 
r=int(np.sqrt(n))

for j in range(2,r+1):
  if prime[j] != 0:
    prime[j*j:n+1:j]=0
    
prime.sort()
z=np.where(prime==1)[0][0]
print(np.int64(prime[z+1:z+1+2000000].sum()))
end=time.clock()
 
print("time:",end-start)

这样改进之后,计算效率大大提高了,而且代码缩短了~。在我的电脑上测试(Win 8 + Python 3.4):

两百万前的素数之和:
142913828922
time: 0.13008331361399986

前两百万的素数之和:
31381137530481
time: 5.534884070836405

速度比之前的代码用PyPy执行还快!

关于“电脑病”

谈点外话。感觉自己患上电脑病了,呵呵~~下面是来自《别闹了费曼先生》里边的关于“电脑病”的介绍:

至于弗兰科呢,这个“程序”是他发明的,但这时候他却跟所有后来的电脑使用者一样,患上了电脑病。这是种很严重的病,甚至干扰到正常工作的进行了。电脑的麻烦,在于你会跟它“玩”。它们是那么的有趣——所有的按钮都在你掌握之中,你这样弄得到某个双数,那样弄就是单数。不久之后,只要你够聪明,能计算的东西便愈来愈多。

可是不久之后,我们的系统也崩溃下来了,因为弗兰科无法专心工作,更没用心督导其他人。计算系统运行得很慢很慢,他却坐在房间内,思索如何能让列表机自动算出角度的反正切值。好了,列表机开始动作,画出一行行的线,发出“嗖!嗖!嗖!”的声音,一边画一边计算积分值,然后把所有角度的反正切值列出来,一次完成。

这绝对是没用的事情,因为我们早已有反正切函数表了。但如果你用过计算机,你就会充分了解这种病——发现自己有多能干的喜悦。这是他第一次感染上这种病症,好笑的是,那套系统却刚好是这个可怜虫创造出来的!

感觉真患上这种病了~^_^


转载到请包括本文地址:http://kexue.fm/archives/2991/

如果您觉得本文还不错,欢迎点击下面的按钮对博主进行打赏。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!