6

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

4

5 回答 5

6

我看到虽然已经发布了一个更快的解决方案，但实际上没有人回答这个问题。事实上，这是一个相当难以回答的问题！基本的解释是函数调用相对昂贵。不过，为了使这个结论具有说服力，我必须对 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循环，因此任何开销都会乘以超过 1100 万个。使用 in 中的%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唯一的函数调用是外部函数 to xrange，它不应该引起任何问题。现在，当我对原始版本计时时，花了 11 秒：

found an answer: 232792560
took 11.2349967957 seconds

让我们看看这个新的改进版本管理什么：

found an answer: 232792560
took 2.12648200989 seconds

ProjectEulerFive这比我机器上最快版本的性能还要快：

232792560
took 2.40848493576 seconds

一切都变得有意义了。

于 2012-07-15T14:59:42.567 回答
5

这应该不会花费任何时间：

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)
于 2012-07-14T21:48:30.123 回答
4

不是您的问题的答案（因此是社区 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
于 2012-07-14T20:41:59.340 回答
0

你可以使用素数来解决这个问题。在 0.0004 秒内求解 n=20，在 0.0011 内求解 n=50。

from math import sqrt
import time
num = int(input("Number: "))
start_time = time.clock()

def is_prime(n):
    if(n == 2 or n == 3):
        return True
    elif(n < 2 or n % 2 == 0):
        return False
    for i in range(3, int(sqrt(n))+1, 2):
        if(n % i == 0):
            return False
    return True

def decompose(n):
    if(n == 1 or n == 0):
        return [n]
    l = []
    residue = n
    while(residue != 1):
        for i in range(1, residue+1):
            if(residue%i==0 and is_prime(i)):
                l.append(i)
                residue //= i
                break
    return l

l = []
for i in range(1, num):
    d = decompose(i)
    for n in d:
        if(l.count(n) < d.count(n)):
            l += [n]*(d.count(n)-l.count(n))
result = 1
for i in l:
    result*=i
print(result)

print("time: ", time.clock()-start_time)
于 2018-07-30T18:10:14.620 回答
0

这是我的实现

我理解原因，但希望能对它背后的数学有所启发

如果我写下所有不大于最大可除数的素数，则替换包含小于我的限制的素数除数的因子子集。

from functools import reduce

def divisible_by_all_up_to(limit):
    def is_prime(num):
        if num == 2 or num == 3:
            return True
        if num % 2 == 0 or num < 2:
            return False
        for i in range(3, num):
            if num % i == 0:
                return False
        return True
    primes = [i for i in range(limit) if is_prime(i) == True]
    mult = []
    for index, value in enumerate(primes):
        while value * value < limit:
            value = value * value
        mult += [value]
    return mult

ans = divisible_by_all_up_to(20)

resp = reduce(lambda x, y: x*y, ans)
于 2019-08-12T16:17:42.520 回答