[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动[批处理精品]CMD命令50条不能说的秘密[在线下载]第三方命令行工具[在线帮助]VBScript / JScript 在线参考
返回列表 发帖

[原创代码] python分片应用~秒出一亿内素数

本帖最后由 happy886rr 于 2016-4-17 13:25 编辑

  在python中分片的扩展形式:str[I,J,K]意思是从I到J-1,每隔K个元素索引一次,如果K为负数,就是按从右往左索引。那么这个分片到底有什么作用呢?承接上一集“吹蜡烛”里的“打印出100万以内的所有素数“。

  当时使用的是for循环去吹蜡烛,外层for生成素数,内层for吹烛,感觉for循环嵌套的效率非常低,发现吹蜡烛这个事用分片就可以做,没必要使用for。于是,全部替换成分片操作,效率瞬间提升10倍。但是每个蜡烛如果都用普通数组表示也忒非内存了!无意中发现python教程中还有bytearray这种字节型数组,好家伙这不是要逆天了吗?一个字节8位,为了少写点代码,就不研究怎么用bit来表示蜡烛了,直接用了byte表示蜡烛,效率再次提升3倍,最后利用素数循环节(直接跳过前4轮)再提速0.4秒。实现0.8秒左右便可构建出一亿内的素数(当然不算打印时间),只比julia慢0.2秒。
  1. #---------------------Python Primes---------------------
  2. def primes(N):
  3. print("构建{0}内的素数...".format(N))
  4. L=[0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1]
  5. r=bytearray(L)*(N//210)+bytearray(L[0:N%210])
  6. r[1]=0;r[2]=r[3]=r[5]=r[7]=1
  7. for i in range(11,int(N**0.5),2):
  8. if r[i]:r[i*i::i*2]=bytearray([0])*((N-i*i)//(i*2)+1)
  9. input("是否开始打印?(回车)")
  10. for i,p in enumerate(r):
  11. if p:
  12. print(i,",",end="")
  13. #-------------------------------------------------------
  14. primes(10**8)
复制代码
  后来又想,吹蜡烛太费气力了,如果要打印出一亿以内的所有素数,那么我要吹灭数千万根蜡烛,还不如改吹蜡烛为点蜡烛,这个算法没有办法用分片实现,用C语言试了下,效率很满意,0.130秒出一亿内素数。可能由于python是脚本语言,同样的算法速度总是无法跟C比。

  以下是模块化后的版本,筛选一亿内素数速度接近0.6秒。
  1. #---------------------Count Time------------------------
  2. def Tim(X):
  3. import time
  4. def F(*a, **b):
  5. t=time.time()
  6. a=X(*a, **b)
  7. print("[{0}s @{1}]".format(time.time() - t, X.__name__))
  8. return a
  9. return F
  10. #---------------------Primes----------------------------
  11. @Tim
  12. def primes(N):
  13. print("构建{0}内的素数...".format(N))
  14. r=bytearray([1])*(N//2)
  15. for i in range(3,int(N**0.5)+1,2):
  16. if r[i//2]:r[i*i//2::i]=bytearray((N-i*i-1)//(i*2)+1)
  17. return r
  18. #---------------------Print Primes----------------------
  19. def printf(R):
  20. input("开始打印?(回车)")
  21. R[0]=0;print(2,",",end="")
  22. for i,p in enumerate(R):
  23. if p:
  24. print(i*2+1,",",end="")
  25. #---------------------Main------------------------------
  26. R=primes(10**8)
  27. printf(R)
复制代码
  将分片函数改造一下,变成身为Primest(K)函数,返回第K个素数。高性能的分片函数筛选器,寻找第K个素数,只需筛选K*24范围内的数。
  1. #---------------------Count Time------------------------
  2. def Tim(X):
  3. import time
  4. def F(*a, **b):
  5. t=time.time()
  6. a=X(*a, **b)
  7. print("[{0}s @{1}]".format(time.time()-t, X.__name__))
  8. return a
  9. return F
  10. #---------------------Primest---------------------------
  11. @Tim
  12. def Primest(K):
  13. N=K*24
  14. r=bytearray([1])*(N//3);r[0]=0;j=2
  15. for i in range(int(N**0.5)//3+1):
  16. if r[i]:
  17. I=3*i+1|1
  18. r[((I*I)//3)::2*I]=bytearray([0])*((N//6-(I*I)//6-1)//I+1)
  19. r[(I*I+4*I-2*I*(i&1))//3::2*I]=bytearray([0])*((N//6-(I*I+4*I-2*I*(i&1))//6-1)//I+1)
  20. for i,p in enumerate(r):
  21. if p:
  22. j+=1
  23. if j==K:
  24. print("* The {0}st prime number is :{1}".format(K,i*3+1|1))
  25. break
  26. #-------------------------------------------------------
  27. Primest(10001)      #调用Primest(K)函数,返回第K个素数
复制代码
  如此解欧拉计划第七题:求第一万零一个素数?可直接调用Primest(K)函数,0.001秒出答案。
1

评分人数

回复 18# 523066680


    老板娘可好?

TOP

回复 18# 523066680


浪费天分啦。
去学去写去用才有进步。安装python3代码存为xx.py 双击运行或右键用IDLE打开按F5运行

TOP

回复 15# codegay


    现在换啥语言都没心情了。沦为做生意 =_=

TOP

回复 16# CrLf


    powershell才是最好的语言。
去学去写去用才有进步。安装python3代码存为xx.py 双击运行或右键用IDLE打开按F5运行

TOP

回复 15# codegay


    艹,这到底是什么论坛

TOP

回复 13# 523066680


    不晚不晚。

不如投奔我大julia阵营?
去学去写去用才有进步。安装python3代码存为xx.py 双击运行或右键用IDLE打开按F5运行

TOP

WOW,多发点,多发点
等俺去学Python时这些代码可都是宝贵的资料啊

TOP

回复 5# happy886rr


     我现在肠子都悔青了,没有趁早换C艹

TOP

回复 11# happy886rr


    你可以搜索一下python time()  和clock()的区别。
我印象里看的一些文章是推荐用clock()
去学去写去用才有进步。安装python3代码存为xx.py 双击运行或右键用IDLE打开按F5运行

TOP

回复 10# codegay
统计时间是必须的,但是没julia的@time好用。

TOP

我去,你这进步好快,装饰器都会用了。
去学去写去用才有进步。安装python3代码存为xx.py 双击运行或右键用IDLE打开按F5运行

TOP

回复 8# codegay
codegay兄给的链接很详细,写python非常有趣,像是搭积木。

TOP

编码问题,因为我是用IDLE或者sublime的,空文件好像都会被存成UTF8。
所以没有这个问题了。
去学去写去用才有进步。安装python3代码存为xx.py 双击运行或右键用IDLE打开按F5运行

TOP

本帖最后由 codegay 于 2016-4-17 01:13 编辑

回复 3# happy886rr

那个不叫我的技巧。。。教程里可能也是有说到的,大约是我忘记了。我是在欧拉论坛里看别人的代码学会的。....

这个问题底下:https://segmentfault.com/q/1010000004929185

有人给出了Awesome Python Books 的链接: https://github.com/Junnplus/awes ... ter/README-ZH_CN.md


顺便也推荐给你。
去学去写去用才有进步。安装python3代码存为xx.py 双击运行或右键用IDLE打开按F5运行

TOP

返回列表