如何优化基于itertools生成任意n元毕达哥拉斯组的函数？

原实现的问题分析 #

你最初用itertools.product的实现会遍历所有1-99的三元组合（共970299次），其中包含大量重复无效的组合（比如(4,3,5)和(3,4,5)都会被遍历），导致效率极低。添加max(a_0,a_1) < a_2确实能提前过滤掉斜边小于直角边的无效情况，减少部分计算量，但提升有限。而itertools.combinations只生成无序不重复的二元组（共4851次），避免了重复遍历，所以性能提升明显。

最大化优化的几种方案 #

方案1：基于欧几里得公式生成（效率最优）

利用数论中的欧几里得公式直接生成本原三元组，再扩展到非本原三元组，完全避免暴力遍历，是性能最高的方案。

公式逻辑：

• 取整数m > n > 0，且m和n互质、一奇一偶
• 本原三元组为：a = m² - n²，b = 2mn，c = m² + n²
• 对本原三元组乘以任意正整数k，得到所有非本原三元组

代码实现：

import math

def generate_pythagorean_triples(limit):
    triples = set()
    max_m = int(math.sqrt(limit)) + 1
    for m in range(2, max_m):
        for n in range(1, m):
            # 确保m、n互质且奇偶性不同
            if math.gcd(m, n) == 1 and (m - n) % 2 == 1:
                a = m**2 - n**2
                b = 2 * m * n
                c = m**2 + n**2
                if c > limit:
                    continue
                # 添加本原三元组（排序避免重复）
                triples.add(tuple(sorted((a, b, c))))
                # 生成倍数扩展的非本原三元组
                k = 2
                while k * c <= limit:
                    triples.add(tuple(sorted((k*a, k*b, k*c))))
                    k += 1
    return sorted(triples)

这个方法的时间复杂度远低于暴力法，当limit越大时，性能优势越显著。

方案2：优化暴力遍历法（次优选择）

如果偏好暴力思路，可进一步缩小遍历范围，配合整数平方根判断提升效率：

import itertools
import math

def generate_triples_optimized(limit):
    triples = []
    # 遍历a < b的组合，避免重复
    for a, b in itertools.combinations(range(1, limit), 2):
        c_sq = a**2 + b**2
        # 用isqrt获取整数平方根（Python3.8+）
        c = math.isqrt(c_sq)
        # 验证平方相等且c不超过上限
        if c**2 == c_sq and c <= limit:
            triples.append((a, b, c))
    return triples

这里通过combinations减少遍历次数，用math.isqrt替代普通平方根计算（更高效且避免浮点误差），同时提前判断c <= limit，进一步减少无效计算。

性能对比 #

• 欧几里得公式法：生成100以内的三元组仅需遍历数十次m和n，性能碾压暴力法
• 优化后的暴力法：遍历次数仅为原product实现的0.5%左右，比原combinations实现也有小幅提升

内容的提问来源于stack exchange，提问作者TechYharon