use*_*ame 5 python algorithm optimization primes profiling
我有两种在Python中查找素数的算法.每个的内循环似乎执行相同的次数,并且同样简单.但是,其中一个需要10倍于另一个.我的问题是:
为什么？这是一些可以优化掉的Python的怪癖(如何？),还是我错过了其他的东西？
我要解决的问题主要来自http://www.spoj.pl/problems/PRIME1/.在我的情况下,我有N = 10**9,delta = 10**5,我想找到N-delta和delta之间的所有素数.我还有smallprimes一个预先制作的所有素数小于或等于N的平方根的列表.第一个算法非常简单:
def range_f1(lo, hi, smallprimes):
"""Finds all primes p with lo <= p <= hi.
smallprimes is the sorted list of all primes up to (at least) square root of hi.
hi & lo might be large, but hi-lo+1 miust fit into a long."""
primes =[]
for i in xrange(hi-lo+1):
n = lo + i
isprime = True
for p in smallprimes:
if n % p == 0:
isprime = False
break
if isprime:
primes.append(n)
return primes
通话range_f1(N-delta,N,smallprimes)需要很长时间(约10秒).内环称为195170次.我还有一个这个算法的版本,用一个列表理解来替换循环(这是我实际用于分析的那个;看到问题的结尾)但是这并不快.
第二个版本是(一个丑陋的实施)Eratosthenes的筛子:
def range_sieve(lo, hi, smallprimes):
"""Parameters as before"""
# So ugly! But SO FAST!! How??
delta = hi-lo+1
iamprime = [True] * delta # iamprime[i] says whether lo + i is prime
if lo<= 1:
iamprime[1 - lo] = False
def sillyfun(): # For profiling & speed comparison
pass
for p in smallprimes:
rem = lo % p
if rem == 0:
iamprime[0] = False
for i in xrange(p - rem, delta, p):
iamprime[i] = False
sillyfun()
if p >= lo and p <= hi:
iamprime[p - lo] = True
return [p + lo for (p, ami) in enumerate(iamprime) if ami]
这大约快10倍,不到2秒.但是,内循环(sillyfun())被称为259982次,比最后一种情况要多.我无法解释为什么这很快.
我想也许原因可能是因为第一个算法的内部循环包含模运算,而第二个算法只有一个赋值.但是,以下似乎暗示赋值不比模运算快:
>>> from timeit import timeit
>>> timeit("10**9 % 2341234")
0.23445186469234613
>>> timeit("a[5000]=False", "a = [True] * 10000")
0.47924750212666822
这是我实际使用的第一个算法的(不太可读)版本:
def range_f2(lo, hi, smallprimes):
primes =[]
for i in xrange(hi-lo+1):
n = lo + i
try:
(1 for p in smallprimes if n % p ==0).next()
except StopIteration:
primes.append(n)
return primes
以下是为range_f2()调用探查器的结果(注意评估生成表达式的时间):
>>> from cProfile import run as prof
>>> prof("range_f2(N-delta,N,sp)")
200005 function calls in 13.866 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 13.866 13.866 <string>:1(<module>)
195170 12.632 0.000 12.632 0.000 prime1.py:101(<genexpr>)
1 1.224 1.224 13.865 13.865 prime1.py:90(range_f2)
4832 0.009 0.000 0.009 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
以下是range_sieve()的分析器结果:
>>> prof("range_sieve(N-delta,N,sp)")
259985 function calls in 1.370 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.003 0.003 1.370 1.370 <string>:1(<module>)
1 0.877 0.877 1.367 1.367 prime1.py:39(range_sieve)
259982 0.490 0.000 0.490 0.000 prime1.py:51(sillyfun)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
最后,这里是他完整的代码,生成小素数列表(以非常愚蠢的方式),以便您可以检查您得到的结果:http://pastebin.com/7sfN4mG4
更新按流行需求,第一块代码的分析数据.没有关于内循环执行次数的数据,但似乎很清楚它与第三次相同.
>>> prof("range_f1(N-delta,N,sp)")
4835 function calls in 14.184 CPU seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 14.184 14.184 <string>:1(<module>)
1 14.162 14.162 14.183 14.183 prime1.py:69(range_f1)
4832 0.021 0.000 0.021 0.000 {method 'append' of 'list' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
区别在于算法上的区别。在第一个版本中，试除法，您针对所有小素数测试每个候选者 - 当小素数超过时您不会停止，这candidate ** 0.5对于小素数是否有一个良好的上限并不重要range(10**9 - 10**5 ,10**9)，但如果小素数的长度范围相对于上限要大得多。对于复合材料来说，这不会产生太多成本，因为它们中的大多数至少有一个小的质因数。但对于素数，你必须一直到N**0.5。该区间内大约10**5/log(10**9)有素数，每个素数都被大约素数试除10**4.5/log(10**4.5)，这样就可以1.47*10**7对素数进行试除。
另一方面，使用筛子时，您只能划掉复合材料，每个复合材料都会被划掉与其素数因子相同的次数，而素数根本不会被划掉（因此素数是免费的）。的素因数的数量n以（的倍数）为界log(n)（这是一个粗略的上限，通常大大高估），因此给出了（乘以一个小常数）交叉的上限10**5*log(10**9)，大约为2*10**6。除此之外，交叉可能比除法工作量少（不知道Python，它是针对C数组的）。所以你用筛子做的工作就更少了。
10**9-10**5编辑：收集了to的实际数字10**9。
Ticks: 259987
4832
Divisions: 20353799
4832
筛子仅进行 259987 次交叉，您会发现上面的粗略上限被高估了很大一个因素。试除法需要超过2000万次除法，其中16433632次用于素数（x/log x低估了素数的数量，x = 10**4.5大约10%），3435183次用于该范围内最小素因子大于的3297个数字n**(1/3)。