标题: [原创代码] python分片应用~秒出一亿内素数 [打印本页]
作者: happy886rr 时间: 2016-4-16 13:27 标题: 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倍，最后利用素数循环节（直接跳过前４轮）再提速0.4秒。实现0.8秒左右便可构建出一亿内的素数（当然不算打印时间），只比julia慢0.2秒。- #---------------------Python Primes---------------------
- def primes(N):
- print("构建{0}内的素数...".format(N))
- 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]
- r=bytearray(L)*(N//210)+bytearray(L[0:N%210])
- r[1]=0;r[2]=r[3]=r[5]=r[7]=1
- for i in range(11,int(N**0.5),2):
- if r[i]:r[i*i::i*2]=bytearray([0])*((N-i*i)//(i*2)+1)
- input("是否开始打印？（回车）")
- for i,p in enumerate(r):
- if p:
- print(i,",",end="")
- #-------------------------------------------------------
- primes(10**8)
后来又想，吹蜡烛太费气力了，如果要打印出一亿以内的所有素数，那么我要吹灭数千万根蜡烛，还不如改吹蜡烛为点蜡烛，这个算法没有办法用分片实现，用Ｃ语言试了下，效率很满意，0.130秒出一亿内素数。可能由于python是脚本语言，同样的算法速度总是无法跟C比。
以下是模块化后的版本，筛选一亿内素数速度接近0.6秒。- #---------------------Count Time------------------------
- def Tim(X):
- import time
- def F(*a, **b):
- t=time.time()
- a=X(*a, **b)
- print("[{0}s @{1}]".format(time.time() - t, X.__name__))
- return a
- return F
- #---------------------Primes----------------------------
- @Tim
- def primes(N):
- print("构建{0}内的素数...".format(N))
- r=bytearray([1])*(N//2)
- for i in range(3,int(N**0.5)+1,2):
- if r[i//2]:r[i*i//2::i]=bytearray((N-i*i-1)//(i*2)+1)
- return r
- #---------------------Print Primes----------------------
- def printf(R):
- input("开始打印？（回车）")
- R[0]=0;print(2,",",end="")
- for i,p in enumerate(R):
- if p:
- print(i*2+1,",",end="")
- #---------------------Main------------------------------
-
- R=primes(10**8)
- printf(R)
将分片函数改造一下，变成身为Primest(K)函数，返回第K个素数。高性能的分片函数筛选器，寻找第K个素数，只需筛选K*24范围内的数。- #---------------------Count Time------------------------
- def Tim(X):
- import time
- def F(*a, **b):
- t=time.time()
- a=X(*a, **b)
- print("[{0}s @{1}]".format(time.time()-t, X.__name__))
- return a
- return F
- #---------------------Primest---------------------------
- @Tim
- def Primest(K):
- N=K*24
- r=bytearray([1])*(N//3);r[0]=0;j=2
- for i in range(int(N**0.5)//3+1):
- if r[i]:
- I=3*i+1|1
- r[((I*I)//3)::2*I]=bytearray([0])*((N//6-(I*I)//6-1)//I+1)
- 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)
- for i,p in enumerate(r):
- if p:
- j+=1
- if j==K:
- print("* The {0}st prime number is ：{1}".format(K,i*3+1|1))
- break
- #-------------------------------------------------------
-
- Primest(10001) #调用Primest(K)函数，返回第K个素数
如此解欧拉计划第七题：求第一万零一个素数？可直接调用Primest(K)函数，0.001秒出答案。
作者: codegay 时间: 2016-4-16 15:01
可以括号把list写成几行.- 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])
作者: happy886rr 时间: 2016-4-16 17:09
回复 2# codegay
codegay兄的技巧不错，但是我发现py不能存为ansi编码，每次都得另存utf8,。
作者: 523066680 时间: 2016-4-16 17:35
本帖最后由 523066680 于 2016-4-16 17:49 编辑
回复 3# happy886rr
因为你里面写了中文嘛
查了一下，要保存为gbk文本而不提示"Non-ASCII character"的话，在行首加入
#coding:gbk
或者
#encoding:gbk
参考链接
Python的中文问题解决办法
作者: happy886rr 时间: 2016-4-16 18:53
回复 4# 523066680
谢谢。你的bat显示技巧很赞，还有那些游动粒子，虽然bat只提供了echoset/p=。
作者: ivor 时间: 2016-4-16 20:12
主要是Python的 for 遍历循环拖累了速度
作者: codegay 时间: 2016-4-16 22:28
本帖最后由 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
顺便也推荐给你。
作者: codegay 时间: 2016-4-16 22:31
编码问题，因为我是用IDLE或者sublime的，空文件好像都会被存成UTF8。
所以没有这个问题了。
作者: happy886rr 时间: 2016-4-17 00:26
回复 8# codegay
codegay兄给的链接很详细，写python非常有趣，像是搭积木。
作者: codegay 时间: 2016-4-17 01:15
我去，你这进步好快，装饰器都会用了。
作者: happy886rr 时间: 2016-4-17 12:51
回复 10# codegay
统计时间是必须的，但是没julia的@time好用。
作者: codegay 时间: 2016-4-17 13:28
回复 11# happy886rr
你可以搜索一下python time() 和clock()的区别。
我印象里看的一些文章是推荐用clock()
作者: 523066680 时间: 2016-4-17 20:35
回复 5# happy886rr
我现在肠子都悔青了，没有趁早换C艹
作者: bailong360 时间: 2016-4-17 22:17
WOW,多发点,多发点
等俺去学Python时这些代码可都是宝贵的资料啊
作者: codegay 时间: 2016-4-17 22:38
回复 13# 523066680
不晚不晚。
不如投奔我大julia阵营？
作者: CrLf 时间: 2016-4-17 23:06
回复 15# codegay
艹，这到底是什么论坛
作者: codegay 时间: 2016-4-17 23:08
回复 16# CrLf
powershell才是最好的语言。
作者: 523066680 时间: 2016-4-18 10:13
回复 15# codegay
现在换啥语言都没心情了。沦为做生意 =_=
作者: codegay 时间: 2016-4-18 10:22
回复 18# 523066680
浪费天分啦。
作者: CrLf 时间: 2016-4-18 13:19
回复 18# 523066680
老板娘可好？
| 欢迎光临 批处理之家 (http://bbs.bathome.net/) |
Powered by Discuz! 7.2 |