MVT*_*VTC 6 python performance
我把这个解决方案写给Project Euler#5.
import time
start_time = time.time()
def ProjectEulerFive (m = 20):
a = m
start = 2
while (m % start) == 0:
start += 1
b = start
while b < m:
if ( a % b) != 0:
a += m
b = start
continue
else:
b += 1
return a
import sys
if (len(sys.argv)) > 2:
print "error: this function takes a max of 1 argument"
elif (len(sys.argv)) == 2:
print ProjectEulerFive(int(sys.argv[1]))
else:
print ProjectEulerFive();
print "took " + str(time.time() - start_time ) + " seconds"
占用我的系统约8.5秒.
然后我决定与其他人的解决方案进行比较.我在Python中发现了这个 Project Euler 5 - 我如何优化我的解决方案？.
我没有想到独特的素因子分解.
但无论如何,一个据称优化的非基于因子分解的解决方案在那里发布:
import time
start_time = time.time()
check_list = [11, 13, 14, 16, 17, 18, 19, 20]
def find_solution(step):
for num in xrange(step, 999999999, step):
if all(num % n == 0 for n in check_list):
return num
return None
if __name__ == '__main__':
solution = find_solution(20)
if solution is None:
print "No answer found"
else:
print "found an answer:", solution
print "took " + str(time.time() - start_time ) + " seconds"
占用我的系统约37秒
即使我不必要地检查3,4,5,6,7,8,9,10和12的可分性,我的代码也快4倍.
我是python的新手,无法看到效率低下的地方.
编辑:
我做了另一个测试.
import time
start_time = time.time()
def ProjectEulerFive (m = 20):
ls = [11, 13, 14, 15, 16, 17, 18, 19]
a = m
i = 0
while i < len(ls):
if ( a % ls[i]) != 0:
a += m
i = 0
continue
else:
i += 1
return a
print ProjectEulerFive();
print "took " + str(time.time() - start_time ) + " seconds"
占用我的系统6秒,但这个:
import time
start_time = time.time()
def ProjectEulerFive (m = 20):
a = m
start = 11
b = start
while b < m:
if ( a % b) != 0:
a += m
b = start
continue
else:
b += 1
return a
print ProjectEulerFive()
print "took " + str(time.time() - start_time ) + " seconds"
大约需要3.7秒
我看到虽然已经发布了更快的解决方案,但实际上没有人回答过这个问题.事实上,这是一个相当难以回答的问题!基本的解释是函数调用相对昂贵.但是,为了使这个结论具有说服力,我将不得不深入研究Python内部.做好准备!
首先,我要拆卸(你的第三个版本)ProjectEulerFive和find_solution"优化"解决方案,使用dis.dis.这里有很多,但需要快速扫描以确认您的代码根本不调用任何函数:
>>> dis.dis(ProjectEulerFive)
2 0 LOAD_FAST 0 (m)
3 STORE_FAST 1 (a)
3 6 LOAD_CONST 1 (11)
9 STORE_FAST 2 (start)
4 12 LOAD_FAST 2 (start)
15 STORE_FAST 3 (b)
5 18 SETUP_LOOP 64 (to 85)
>> 21 LOAD_FAST 3 (b)
24 LOAD_FAST 0 (m)
27 COMPARE_OP 0 (<)
30 POP_JUMP_IF_FALSE 84
6 33 LOAD_FAST 1 (a)
36 LOAD_FAST 3 (b)
39 BINARY_MODULO
40 LOAD_CONST 2 (0)
43 COMPARE_OP 3 (!=)
46 POP_JUMP_IF_FALSE 71
7 49 LOAD_FAST 1 (a)
52 LOAD_FAST 0 (m)
55 INPLACE_ADD
56 STORE_FAST 1 (a)
8 59 LOAD_FAST 2 (start)
62 STORE_FAST 3 (b)
9 65 JUMP_ABSOLUTE 21
68 JUMP_ABSOLUTE 21
11 >> 71 LOAD_FAST 3 (b)
74 LOAD_CONST 3 (1)
77 INPLACE_ADD
78 STORE_FAST 3 (b)
81 JUMP_ABSOLUTE 21
>> 84 POP_BLOCK
12 >> 85 LOAD_FAST 1 (a)
88 RETURN_VALUE
现在让我们来看看find_solution:
>>> dis.dis(find_solution)
2 0 SETUP_LOOP 58 (to 61)
3 LOAD_GLOBAL 0 (xrange)
6 LOAD_FAST 0 (step)
9 LOAD_CONST 1 (999999999)
12 LOAD_FAST 0 (step)
15 CALL_FUNCTION 3
18 GET_ITER
>> 19 FOR_ITER 38 (to 60)
22 STORE_DEREF 0 (num)
3 25 LOAD_GLOBAL 1 (all)
28 LOAD_CLOSURE 0 (num)
31 BUILD_TUPLE 1
34 LOAD_CONST 2 (<code object <genexpr> at
0x10027eeb0, file "<stdin>",
line 3>)
37 MAKE_CLOSURE 0
40 LOAD_GLOBAL 2 (check_list)
43 GET_ITER
44 CALL_FUNCTION 1
47 CALL_FUNCTION 1
50 POP_JUMP_IF_FALSE 19
4 53 LOAD_DEREF 0 (num)
56 RETURN_VALUE
57 JUMP_ABSOLUTE 19
>> 60 POP_BLOCK
5 >> 61 LOAD_CONST 0 (None)
64 RETURN_VALUE
很明显,(a)这个代码不那么复杂,但(b)它也称为三个不同的函数.第一个只是一个调用xrange,但其他两个调用出现在最外面的for循环中.第一个电话是打电话给all; 我怀疑,第二个next是调用生成器表达式的方法.但是功能是什么并不重要; 重要的是它们在循环中被调用.
现在,你可能会想"有什么大不了的？" 这里.这只是一个函数调用; 这里或那里几纳秒 - 对吗？但实际上,那些纳秒加起来了.由于最外层循环通过总232792560 / 20 == 11639628循环,所以任何开销都会乘以超过1,100万.使用%timeit命令的快速计时ipython表明,函数调用 - 全部 - 在我的机器上花费大约120纳秒:
>>> def no_call():
... pass
...
>>> def calling():
... no_call()
...
>>> %timeit no_call()
10000000 loops, best of 3: 107 ns per loop
>>> %timeit calling()
1000000 loops, best of 3: 235 ns per loop
因此,对于while循环中出现的每个函数调用,120 nanoseconds * 11000000 = 1.32 seconds花费的时间更多.如果我是正确的,第二个函数调用是对生成器表达式next方法的调用,那么该函数被调用甚至更多次,每次迭代通过genex一次 - 平均每个循环大概3-4次.
现在来测试这个假设.如果函数调用是问题,那么消除函数调用就是解决方案.让我们来看看...
def find_solution(step):
for num in xrange(step, 999999999, step):
for n in check_list:
if num % n != 0:
break
else:
return num
return None
这是一个版本find_solution几乎完全与原始使用for/else语法.唯一的函数调用是外部函数调用xrange,它不应该导致任何问题.现在,当我定时原版时,花了11秒钟:
found an answer: 232792560
took 11.2349967957 seconds
让我们看看这个新的改进版本管理的内容:
found an answer: 232792560
took 2.12648200989 seconds
这比ProjectEulerFive我机器上最快版本的性能要快:
232792560
took 2.40848493576 seconds
一切都有意义.
这应该不花时间:
def gcd(a, b):
if (b == 0): return a
else: return gcd(b, a%b)
def lcm(a, b):
return abs(a*b) / gcd(a, b)
def euler5(n):
if (n == 1): return 1
else: return lcm(n, euler5(n-1))
print euler5(20)