Пифагорейские тройки являются хорошим примером для утверждения, что «for циклы считаются вредными », потому что for циклы соблазняют нас задуматься о подсчете, часто самой несущественной части задачи.
(я собираюсь придерживаться псевдокода, чтобы избежать смещения языка и чтобы упростить псевдокод, я не буду оптимизировать множественные вычисления, например, 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 -куб.
Бессмысленно продолжать изучать растущие значения z после того, как z * z < x * x + y * y больше не удерживается. Этот факт мотивирует Версия 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
}
}
}
Для N из 1000 это примерно в 5 раз быстрее, чем в версии 2, но это все еще куб. При 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 только один раз. Он не только более чем в 100 раз быстрее для N из 1000, он также квадратичен для N, поэтому ускорение увеличивается с ростом N.
Я встречал такого рода улучшения достаточно часто, чтобы не доверять «счетным циклам» для любых, кроме самых тривиальных целей (например, обход массива).
Обновление: Очевидно, я должен был указать на некоторые вещи в V4, которые легко упустить из виду.
Оба из while циклов управляются значением z (один напрямую, другой косвенно через квадрат z). Внутреннее while фактически ускоряет внешнее while, а не ортогонально ему. Важно посмотреть, что делают циклы, а не просто подсчитать, сколько существует циклов.
Все вычисления в V4 являются строго целочисленной арифметикой. Преобразование в / из плавающей запятой, а также вычисления с плавающей запятой дорогостоящие в сравнении.
V4 работает в постоянной памяти, требуя только трех целочисленных переменных. Нет массивов или хеш-таблиц, которые можно было бы выделить и инициализировать (и, возможно, вызвать ошибку нехватки памяти).
Исходный вопрос позволял всем x, y и x варьироваться в одном и том же диапазоне. V1..V4 следовал этому образцу.
Ниже приведен не очень научный набор моментов времени (использующий Java под Eclipse на моем старом ноутбуке с запущенным другим ...), где «use x, y, z» было реализовано путем создания экземпляра объекта Triple с три значения и положить его в ArrayList. (Для этих прогонов N было установлено на 10000, что в каждом случае составляло 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 по запросу для других вариантов, которые я рассчитал, на случай, если я что-то неправильно реализовал.