毕达哥拉斯三元组是宣称“ for
循环被认为是有害的”的一个很好的例子，因为
for循环引诱我们思考计数，这通常是任务中最不相关的部分。
（我将坚持使用伪代码来避免语言偏见，并且为了简化伪代码，我不会优化eg
x * 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立方系数。
继续检查
zafter
z * 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以1000
N的速度提高了100倍以上，而且在上是平方的，所以速度随增长而
N增加。
我经常遇到这种改进，以至于除了最琐碎的用途（例如遍历数组）以外，对“计数循环”都不信任。
更新： 显然我应该指出一些有关V4的事情，这些事情很容易忽略。
两者 的的
while
圈由的值控制z
（一个直接，其他间接地通过的平方z
）。内部while
实际上是在加速外部while
，而不是与外部正交。 重要的是要查看循环的作用，而不仅仅是计算有多少个循环。V4中的所有计算都是严格的整数算术运算。通过比较，与浮点数之间的转换以及浮点数的计算成本很高。
V4在恒定内存中运行，仅需要三个整数变量。没有要分配和初始化（并且可能导致内存不足错误）的数组或哈希表。
原来的问题让所有的
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 .. Nroots = map of i*i -> i for i in 1 .. Nfor 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源代码，以提供我选择的其他版本，以防万一我没有正确实现任何东西。
