Python效率/优化项目Euler #5示例

Question

我为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中的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秒

Answer 1

我看到，虽然有一个更快的解决办法，但没有人真正回答这个问题。事实上，这是一个很难回答的问题！基本的解释是函数调用相对昂贵。不过，为了使这一结论具有说服力，我必须深入研究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

一切又有意义了。

Answer 2

这不应该花多少时间：

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 3

不是对您的问题(因此是社区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

用法如下：

@print_time
def foo(x, y):
    time.sleep(1)
    return x + y

在实践中：

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