Maksimum, minimum
2010-09-30 18:52Programiści grafiki czasu rzeczywistego wiedzą, że gdy w obliczeniach potrzebne są wartości sinusa i cosinusa dla tego samego kąta, należy obliczać je razem. (O ile oczywiście ich nie tablicujemy). To, o czym chciałbym napisać dzisiaj, jest kwestią bardzo podobną, ale możliwą do stosowania w sytuacji spotykanej przez właściwie każdego programistę.
Chodzi o znajdowanie największego i najmniejszego elementu w dowolnej kolekcji. Uzyskanie każdej z tych wartości osobno jest proste niczym Hello world, nawet jeśli nasz język nie ma od tego żadnej wbudowanej funkcji (są jeszcze takie?). Okazuje się jednak, że oddzielne szukanie minimum i maksimum jest nieefektywne. Jeśli bowiem potrzebujemy obu wartości, to należy szukać ich jednocześnie.
Jak? Całkiem prosto. Przechodząc po zawartości pojemnika, trzeba zajmować się naraz nie jednym, lecz dwoma elementami. Zaczynamy jednak od porównania ich ze sobą, a dopiero potem z aktualnym maksimum (większy z dwóch) i aktualnym minimum (mniejszy). Implementacja tego pomysłu dla pojemników STL może wyglądać na przykład tak:
template
{
typename C::size_type s = c.size();
if (s == 0) return;
if (s == 1) { *min = *max = c[0]; return; }
// inicjalizacja wartości początkowych min i max
T m, M;
typename C::size_type i;
if (s & 1u) { m = M = c[0]; i = 1; }
else
{
if (c[0] <= c[1]) { m = c[0]; M = c[1]; }
else { m = c[1]; M = c[0]; }
i = 2;
}
T x, y; /* x >= y */
for ( ; i < s; i += 2)
{
if (c[i] <= c[i + 1]) { y = c[i]; x = c[i + 1]; }
else { x = c[i]; y = c[i + 1]; }
if (x > M) M = x; if (y < m) m = y;
}
*min = m; *max = M;
}[/cpp]
Ponieważ liczba elementów może być nieparzysta lub parzysta, konieczna jest odpowiednia inicjalizacja. W pierwszym przypadku bierzemy pierwszy element jako początkowe maksimum i minimum, zaś w drugim dokonujemy porównania dwóch pierwszych elementów. Resztę kolekcji możemy już przetwarzać dwójkami.
Zysk wydajnościowy z takiego podejścia to teoretycznie około 25%. Wynika to z faktu, iż na dwa elementy "zużywamy" tutaj tylko trzy porównania, czyli o jedno mniej niż dla oddzielnych wywołań min i max. W praktyce osiągi te psuje bardziej czasochłonny start funkcji, więc opłaca się ją stosować głównie dla większych zbiorów elementów.
-
Sebas86:
September 30th, 2010 o 19:40Przyrost nie wynosi 25% z tego względu, że dostęp do pamięci i pętla także ma swój koszt. Przy bardzo dużych tablicach może okazać się, że przyspieszenie będzie dwukrotne.
-
Void:
October 1st, 2010 o 14:12Fajne podejscie, ale zamiast kolekcji proponuje wykorzystac iteratory (wskazniki)
(na szybko wykodzilem cos takiego)template
pairminmax(Iter begin, Iter end)
{
pairres = make_pair(begin, begin);
Iter it = begin;
if(distance(begin, end) % 2)
it++;
pairlocalRes;
for(;it != end;it += 2) {
localRes = make_pair(it, it+1);
if(*localRes.first > *localRes.second)
swap(localRes.first, localRes.second);
if(*localRes.first < *res.second) res.second = localRes.second; } return res; } [/cpp]
-
Xion:
October 1st, 2010 o 16:41@Void: Zdecydowanie coś mi śmierdzi w drugim ifie – nie powinno być raczej (*localRes.first < *res.first) res.first = localRes.first? A wtedy brakuje też aktualizowania res.second, czyli maksimum.
A inna sprawa jest taka, że distance() na iteratorach może potencjalnie całkiem długo działać :)
-
Void:
October 1st, 2010 o 18:05@Xion: Dokładnie.
Html źle mi potraktował kod po przeklejeniu do formularza. Jeśli możesz to popraw :)
Na początku przydał by się też warunek na begin == end
distance dla iteratorów o dostępie swobodnym działa w czasie stałym, a tylko w tego typu iteratorach można skakać co drugi element :)
Recent posts
