如何優化這個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