生成独特的，有序的勾股三胞胎 [英] Generating unique, ordered Pythagorean triplets

问题描述

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

This is a program I wrote to calculate Pythagorean triplets. When I run the program it prints each set of triplets twice because of the if statement. Is there any way I can tell the program to only print a new set of triplets once? Thanks.

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()  

推荐答案

毕达哥拉斯三元组是声称" for认为有害的循环"的一个很好的例子，因为for循环使我们陷入思考关于计数，通常是一项任务中最不相关的部分.

Pythagorean Triples make a good example for claiming "for loops considered harmful", because for loops seduce us into thinking about counting, often the most irrelevant part of a task.

(我将坚持使用伪代码以避免语言偏见，并且为了简化伪代码，我不会优化x * x和y * y的多次计算.)

(I'm going to stick with pseudo-code to avoid language biases, and to keep the pseudo-code streamlined, I'll not optimize away multiple calculations of e.g. x * x and 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上是立方的.

is the worst solution. It generates duplicates, and traverses parts of the space that aren't useful (e.g. whenever z < y). Its time complexity is cubic on N.

第二版是第一个改进，来自要求保持x < y < z的状态，例如:

Version 2, the first improvement, comes from requiring x < y < z to hold, as in:

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 -cubed的系数.

which reduces run time and eliminates duplicated solutions. However, it is still cubic on N; the improvement is just a reduction of the co-efficient of N-cubed.

在z * z < x * x + y * y不再成立之后继续检查z的增加的值是没有意义的.这一事实激发了第3版，这是通过z进行暴力迭代的第一步:

It is pointless to continue examining increasing values of z after z * z < x * x + y * y no longer holds. That fact motivates Version 3, the first step away from brute-force iteration over 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
        }
    }
}

对于N为1000，这比版本2快5倍，但在N上为静止立方.

For N of 1000, this is about 5 times faster than Version 2, but it is still cubic on N.

下一个见解是x和y是唯一的独立变量； z取决于它们的值，对于前一个y值考虑的最后一个z值对于下一个y值来说是一个很好的 starting 搜索值.这导致版本4 :

The next insight is that x and y are the only independent variables; z depends on their values, and the last z value considered for the previous value of y is a good starting search value for the next value of y. That leads to Version 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的1000，它不仅速度快100倍以上，而且在N上是二次方，因此，随着N的增长，速度也随之提高.

which allows y and z to "sweep" the values above x only once. Not only is it over 100 times faster for N of 1000, it is quadratic on N, so the speedup increases as N grows.

我经常遇到这种改进，以至于对除最琐碎的用途(例如遍历数组)以外的任何用途的计数循环"都不信任.

I've encountered this kind of improvement often enough to be mistrustful of "counting loops" for any but the most trivial uses (e.g. traversing an array).

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

Update: Apparently I should have pointed out a few things about V4 that are easy to overlook.

1. while循环中的两个都由z的值控制(一个直接，另一个通过z的平方间接地控制).内部while实际上是在加快外部while的速度，而不是与之正交. 重要的是要查看循环的作用，而不仅仅是计算循环数.

1. Both of the while loops are controlled by the value of z (one directly, the other indirectly through the square of z). The inner while is actually speeding up the outer while, rather than being orthogonal to it. It's important to look at what the loops are doing, not merely to count how many loops there are.

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

All of the calculations in V4 are strictly integer arithmetic. Conversion to/from floating-point, as well as floating-point calculations, are costly by comparison.

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

V4 runs in constant memory, requiring only three integer variables. There are no arrays or hash tables to allocate and initialize (and, potentially, to cause an out-of-memory error).

原始问题允许所有x，y和x在同一范围内变化. V1..V4遵循这种模式.

The original question allowed all of x, y, and x to vary over the same range. V1..V4 followed that pattern.

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

Below is a not-very-scientific set of timings (using Java under Eclipse on my older laptop with other stuff running...), where the "use x, y, z" was implemented by instantiating a Triple object with the three values and putting it in an ArrayList. (For these runs, N was set to 10,000, which produced 12,471 triples in each case.)

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

数组和地图"算法本质上是 :

The "array and map" algorithm is essentially:

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

使用平方根"算法实质上是 :

The "using square root" algorithm is essentially:

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)；在其他变体中也进行了类似的优化.

Note that x * x is calculated in the outer loop (although I didn't bother to cache z * z); similar optimizations are done in the other variations.

如果我误用了任何东西，我将很高兴按要求提供Java源代码，以提供我选择的其他版本.

I'll be glad to provide the Java source code on request for the other variations I timed, in case I've mis-implemented anything.

这篇关于生成独特的，有序的勾股三胞胎的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！