如何优化这个Python脚本？

Question

对于具有周长p的整数直角三角形，存在许多解（a，b，c），对于所有这些解，a + b + c == p和毕达哥拉斯定理也适用。我正在编写一个Python脚本来计算可能的解决方案的最大数量为一个三角形< = 1000的三角形。

我的脚本是正确的，但它需要永远运行。我相信即使使用我的i7处理器也需要30多分钟，所以我需要优化它。有人能帮我吗？ （这是一个关于项目欧拉的问题，如果你想知道）

def solutions(p): 
    result = [] 

    for a in range(1, p + 1): 
     for b in range(1, p - a + 1): 
      for c in range(1, p - a - b + 1): 
       if a + b + c == p and a < b and b < c: 
        d = a ** 2 
        e = b ** 2 
        f = c ** 2 

        if (d + e == f) or (e + f == d) or (f + d == e): 
         result.append((a, b, c)) 
    return len(result) 


max_p = 0 
max_solutions = 0 

for p in range(3, 1001): 
    print("Processing %d" % p) 
    s = solutions(p) 

    if s > max_solutions: 
     max_solutions = s 
     max_p = p 

print("%d has %d solutions" % (max_p, max_solutions)) 

Answer 1

这是我对你的程序的重写。

首先，我预先计算所有的平方值。这不仅避免了乘法，而且意味着Python不会为所有方形值不断创建和垃圾收集对象。

接下来，我摆脱了三角形第三面的循环。一旦你选择了a和b的值，只有一个可能的值符合标准a + b + c == 1000，所以这只是测试一个。这将问题从大约O（n^3）转变为大约O（n^2），这是一个巨大的改进。

然后我试着运行它。在我四岁的计算机上，它在大约46秒内完成，所以我停在那里，然后你走了。

我做了一次Google搜索，发现了这个问题的讨论;如果我看到的讨论是正确的，那么这个程序打印出正确的答案。

upper_bound = 1000 

sqr = [i**2 for i in range(upper_bound+1)] 

def solutions(p): 
    result = [] 

    for a in range(1, p - 1): 
     for b in range(1, p - a): 
      c = p - (a + b) 
      if a < b < c: 
       d = sqr[a] 
       e = sqr[b] 
       f = sqr[c] 

       if (d + e == f) or (e + f == d) or (f + d == e): 
        result.append((a, b, c)) 
    return len(result) 


max_p = 0 
max_solutions = 0 

for p in range(3, upper_bound+1): 
    print("Processing %d" % p) 
    s = solutions(p) 

    if s > max_solutions: 
     max_solutions = s 
     max_p = p 

print("%d has %d solutions" % (max_p, max_solutions)) 

编辑：这是一个稍微快一点的版本，我正在玩。它在评论中包含@gnibbler的建议。

upper_bound = 1000 

sqr = [i**2 for i in range(upper_bound+1)] 

def solution(p): 
    count = 0 
    for a in range(1, p - 1): 
     for b in range(a, p - a): 
      c = p - (a + b) 
      d = sqr[a] 
      e = sqr[b] 
      f = sqr[c] 

      if (d + e == f): 
       count += 1 
    return count 

c, p = max((solution(p), p) for p in range(3, upper_bound+1)) 
print("%d has %d solutions" % (p, c)) 

在我的电脑这个版本需要31秒而不是46

棘手的业务使用max()并没有真正让它明显加快。我试了一下，没有预先计算正方形，它非常慢，很慢，我不想等待一个确切的时间。

Answer 2

一个更好的：

def solution(n): 
    count = 0 
    for c in range(n // 3 + 1, n // 2): 
     for a in range(1, n // 3): 
      b = n - a - c 
      if b <= 0: 
       continue 
      if a >= b: 
       continue 
      if a * a + b * b != c * c: 
       continue 
      count += 1 
    return count 

Answer 3

明白了。它只是依靠设置^ 2 + B^2 = C^2，然后代入p - 一个 - B = C

1 from math import pow 
    2 
    3 def see_if_right_triangle(p): 
     solutions = 0 
    4  # Accepts the perimeter as input 
    5  for a in range(1, p): 
    6   for b in range(1, p): 
    7    if 2*p*b + 2*p*a - pow(p, 2) == 2*a*b: 
    8    solutions += 1 
     print "The perimeter {p} has {sol} number of solutions".format(p=p, sol=solutions) 
10       
11 
12 for p in range(3, 1001): 
13  see_if_right_triangle(p) 

我认为这是可以优化更多...特别是如果你想出一些数学以缩小你将接受的范围和b

Answer 4

这不是你的代码优化，但我自己的代码（我用这个问题）。我开始做一些代数使程序非​​常容易，而不必重复1000^3倍（1-1000为a，然后1-1000为b为a每一个值，并为1-1000为c的b每个值

# Project Euler 9 
''' 
Algebra behind Final Method: 
a + b + c = 1000 | a^2 + b^2 = c^2 
c = 1000 - (a + b) # Solving for C 
a^2 + b^2 = (1000 - (a + b))^2 # Substituting value for C 
a^2 + b^2 = 1000000 - 2000a - 2000b + (a + b)^2 # simplifying 
a^2 + b^2 = 1000000 - 2000a - 2000b + a^2 + b^2 + 2ab # simplifying again 
0 = 1000000 - 2000a - 2000b + 2ab # new formula 
2000a - 2ab = 1000000 - 2000b # isolating A 
1000a - ab = 500000 - 1000b # divide by 2 to simplify 
a(1000 - b) = 500000 - 1000b # factor out A 
a = (500000 - 1000b)/(1000 - b) # solve for A 
''' 
def pE9(): 
    from math import sqrt 
    a, b, c = 1, 1, 1 
    while True: 
     b += 1 
     a = (500000 - 1000 * b)/(1000 - b) 
     c = sqrt(a**2 + b**2) 
     if a + b + c == 1000 and a**2 + b**2 == c**2: 
     break 
    print int(a * b * c) 

from timeit import timeit 
print timeit(pE9, number = 1) 

使用number = 1所以只测试一次运行。

输出：

>>> 
# Answer hidden 
0.0142664994414