生成独特的，有序的勾股三胞胎

Question

这是我编写的用于计算勾股三胞胎的程序。当我运行该程序时，由于使用if语句，它会将每组三胞胎打印两次。有什么办法可以让我的程序只打印一组新的三胞胎一次？谢谢。

import math

def main():
    for x in range (1, 1000):
        for y in range (1, 1000):
            for z in range(1, 1000):
                if x*x == y*y + z*z:
                    print y, z, x
                    print '-'*50

if __name__ == '__main__':
    main()

Answer 1

毕达哥拉斯三元组是宣称“ for 循环被认为是有害的”的一个很好的例子，因为for循环引诱我们思考计数，这通常是任务中最不相关的部分。

（我将坚持使用伪代码来避免语言偏见，并且为了简化伪代码，我不会优化egx * x和的多次计算y * y。）

版本1 ：

for x in 1..N {
    for y in 1..N {
        for z in 1..N {
            if x * x + y * y == z * z then {
                // use x, y, z
            }
        }
    }
}

是最糟糕的解决方案。它生成重复项，并遍历空间中无用的部分（例如，每当时z < y）。它的时间复杂度是三次N。

第2版 是第一个改进，来自要求x < y < z保留，例如：

for x in 1..N {
    for y in x+1..N {
        for z in y+1..N {
            if x * x + y * y == z * z then {
                // use x, y, z
            }
        }
    }
}

这样可以减少运行时间并消除重复的解决方案。但是，它仍然是三次方N。改进只是降低了N立方系数。

继续检查zafterz * z < x * x + y * y不再增加的值是没有意义的。这个事实激发了 Version 3的发展
，这是远离暴力迭代的第一步z：

for x in 1..N {
    for y in x+1..N {
        z = y + 1
        while z * z < x * x + y * y {
            z = z + 1
        }
        if z * z == x * x + y * y and z <= N then {
            // use x, y, z
        }
    }
}

对于N1000，这是约比第2版快5倍，但它 仍然 对立方N。

下一个见解是，x并且y是唯一的独立变量。z取决于它们的值，并且的上一个z值考虑的最后一个值是的下一个值的y良好 起始
搜索值y。这导致了 版本4 ：

for x in 1..N {
    y = x+1
    z = y+1
    while z <= N {
        while z * z < x * x + y * y {
            z = z + 1
        }
        if z * z == x * x + y * y and z <= N then {
            // use x, y, z
        }
        y = y + 1
    }
}

这允许y并z“扫动”上述值x一次。它不仅N以1000N的速度提高了100倍以上，而且在上是平方的，所以速度随增长而N增加。

我经常遇到这种改进，以至于除了最琐碎的用途（例如遍历数组）以外，对“计数循环”都不信任。

更新： 显然我应该指出一些有关V4的事情，这些事情很容易忽略。

1. 两者 的的while圈由的值控制z（一个直接，其他间接地通过的平方z）。内部while实际上是在加速外部while，而不是与外部正交。 重要的是要查看循环的作用，而不仅仅是计算有多少个循环。

2. V4中的所有计算都是严格的整数算术运算。通过比较，与浮点数之间的转换以及浮点数的计算成本很高。

3. V4在恒定内存中运行，仅需要三个整数变量。没有要分配和初始化（并且可能导致内存不足错误）的数组或哈希表。

4. 原来的问题让所有的x，y以及x改变在相同范围内。V1..V4遵循该模式。

下面是一组不太科学的计时（在我的较旧笔记本电脑上使用Eclipse下的Java在运行其他东西的情况下…），其中“使用x，y，z”是通过实例化具有三个值的Triple对象来实现的并将其放在ArrayList中。（对于这些运行，将N其设置为10,000，在每种情况下产生12,471个三元组。）

Version 4:           46 sec.
using square root:  134 sec.
array and map:      400 sec.

“数组和地图”算法 本质上是 ：

squares = array of i*i for i in 1 .. N
roots = map of i*i -> i for i in 1 .. N
for x in 1 .. N
    for y in x+1 .. N
        z = roots[squares[x] + squares[y]]
        if z exists use x, y, z

“使用平方根”算法 本质上是 ：

for x in 1 .. N
    for y in x+1 .. N
        z = (int) sqrt(x * x + y * y)
        if z * z == x * x + y * y then use x, y, z

V4的实际代码是：

public Collection<Triple> byBetterWhileLoop() {
    Collection<Triple> result = new ArrayList<Triple>(limit);
    for (int x = 1; x < limit; ++x) {
        int xx = x * x;
        int y = x + 1;
        int z = y + 1;
        while (z <= limit) {
            int zz = xx + y * y;
            while (z * z < zz) {++z;}
            if (z * z == zz && z <= limit) {
                result.add(new Triple(x, y, z));
            }
            ++y;
        }
    }
    return result;
}

注意，这x * x 是 在外部循环中计算的（尽管我没有去缓存z * z）；在其他变体中进行了类似的优化。

我会很高兴按要求提供Java源代码，以提供我选择的其他版本，以防万一我没有正确实现任何东西。