python - 如何优化这个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 秒就完成了，所以我停在那里，然后就开始了。

我进行了谷歌搜索，发现了关于这个问题的讨论；如果我看到的讨论是正确的，那么这个程序会打印正确的答案。

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() 的棘手问题并没有真正使它明显更快。我在没有预先计算平方的情况下尝试了它，它慢得多，慢到我不想等待确切的时间。