Wierszami czy kolumnami? cz I.

Zaczniemy od czegoś bardzo prostego. Sztuczkę tą powinni znać wszyscy programiści. Przyjrzyjmy się poniższemu programowi, dynamicznie liczącemu wartość pewnej tablicy.

const int N = 10000;
static int t[N][N];

for (int i = 1; i < N; i++)
  for (int j = 1; j < N; j++)
    t[i][j] = max(t[i-1][j], t[i][j-1], t[i-1][j-1]);

Poniżej prezentuję ten sam program, z przestawionymi dwoma pętlami. Wyniki obu programów są takie same. Dla wyniku w tym przypadku nie ma bowiem znaczenia która pętla jest zewnętrzna a która wewnętrzna

const int N = 10000;
static int t[N][N];

for (int j = 1; j < N; j++)
  for (int i = 1; i < N; i++)
    t[i][j] = max(t[i-1][j], t[i][j-1], t[i-1][j-1]);

Policzmy jednak czasy działania obu programów (jak zwykle w tym miejscu polecam własne eksperymenty w domu). Wynik być może niektórych zaskoczy. Pierwszy program działa 3-4 razy szybciej. Oto przykładowe czasy działania algorytmów na moim sprzęcie:

Algorytm pierwszy - 0:26.26
Algorytm drugi - 1:13.37

Mojemu znajomemu po drobnej modyfikacji kodu udało się uzyskać następujące czasy:

Algorytm pierwszy - 0:01.23
Algorytm drugi - 0:09.67

Czyli pierwszy program działał 8 razy szybciej niż drugi.
Oba programy wykonują jednakową liczbę operacji i liczą dokładnie to samo (tylko w innej kolejności). Zatem dlaczego pierwszy z nich działa o wiele szybciej? Napiszę o tym w następnej notce.