Python效率/优化项目Euler#5 examp

Question

我为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秒。在

然后我决定与其他人的解决方案进行比较。我找到这个了 Project Euler 5 in Python - How can I optimize my solution?。在

我没有想到唯一素数因式分解。在

但不管怎样，一个被认为是优化的基于非质数分解的解决方案张贴在那里：

^{pr2}$

用我的系统大约37秒

我的代码大约快4倍，即使我不必要地检查3,4,5,6,7,8,9,10和12的整除性。在

我是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秒

Answer 1

这不需要花费时间：

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)

Answer 2

我看到，虽然已经发布了一个更快的解决方案，但实际上没有人回答这个问题。事实上，这是一个很难回答的问题！基本的解释是函数调用相对昂贵。为了使这个结论具有说服力，我将不得不深入研究Python的内部结构。准备好了！在

首先，我将使用^{}从“优化”解决方案中反汇编（您的第三个版本）ProjectEulerFive和{}。这里有很多，但是快速扫描是确认代码根本不调用函数所需的全部内容：

>>> 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：

^{pr2}$

很快我们就明白了：（a）这段代码复杂得多，但（b）它还调用了三个不同的函数。第一个调用仅仅是对xrange的单个调用，但其他两个调用出现在最外层的for循环中。第一个调用是对all的调用；我怀疑第二个调用是正在调用的生成器表达式的next方法。但是函数是什么并不重要，重要的是它们在循环中被调用。在

现在，你可能会想“有什么大不了的？”在这里。这只是一个函数调用；这里或那里几纳秒——对吗？但事实上，这些纳秒加起来。由于最外层的循环总共经过232792560 / 20 == 11639628个循环，因此任何开销都会乘以超过1100万个的。在ipython中使用%timeit命令的快速计时显示，在我的机器上，一个函数调用（全部是它本身）大约要花费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

一切又有意义了。在

Answer 3

不是您问题的答案（因此有了community wiki），但下面是一个有用的计时函数修饰符：

from functools import wraps
import time

def print_time(f):
    @wraps(f)
    def wrapper(*args, **kwargs):
        t0 = time.time()
        result = f(*args, **kwargs)
        print "{0} took {1}s".format(f.__name__, time.time() - t0)
        return result
    return wrapper

用法如下：

^{pr2}$

在实践中：

>>> foo(1, 2)
foo took 1.0s
3