Min-Maxing Readability

Let me introduce you to the following two important functions:

I don’t believe, of course, that this is the first time you may have encountered them. Nor that they are even half as complicated as the definitions above would suggest.

But although they appear rather awkward, what I wanted for those formulations to highlight is one particular way of interpreting the min and max functions as they are used in code. You may think it’s easy enough to read them quite literally (“get me the smallest/largest value”), and in many cases you are absolutely correct:

Often though, we don’t want to get the extreme value from a set, list, vector or other collection of unspecified size. Instead, we call the min/max functions on a few arguments that are known and “hard-coded” upfront. In many cases, this is mostly done to spare us from introducing a verbose if statement, or a more cryptic ternary operator (?:).

Or is it? I was recently surprised when discussing some very simple programming exercise on one of the IRC channels I frequent. Someone pointed out how my proposed solution is quite unusual with its (over)use of the max function. The task goes somewhere along these lines:

You are presented with a device that has n counters (c₀, …, c_n-1) and n+1 buttons (b₀, …, b_n). Every counter c_i is incremented whenever a corresponding button b_i is pressed. Additionally, pressing the extra button b_n sets all the counters to the maximum value displayed on any of them (e.g. [1, 4, 3] → [4, 4, 4]).
Find a way to compute the final state of all counters given a sequence of k buttons presses.

Just by reading the above description and implementing it in the most straightforward way, we can trivially arrive at an algorithm which solves the problem in O(nk) time. And since we need to go through the sequence of button presses at least once, the lower bound for complexity of any other solution is therefore O(k).

My version was a simple improvement over the obvious one, scoring O(n+k) at the cost of maintaining a negligible amount of extra data:

The noteworthy application of max function was responsible for updating one of those values:

If you look closely, you will notice how the first argument serves as a reference point, while only the second one is the actual ‘input’. What this invocation is saying is essentially “make max_state at least as big as it was before – and possibly bigger”.

Hardly a groundbreaking insight, eh? This approach, however, allows to rapidly parse even complicated applications of min and max. If you encounter, for example, an inlined version of a “clamping” function that is written in the following manner:

I’m pretty sure it will take you at least a few moments to grok what it’s doing. The max–min compound is puzzling, and the meaningful arguments (a and b) are disconnected from the function names. Had it had more nesting, you might even have needed to *gasp* count the parentheses.
But we know it’s all about trimming a number to the <a; b> interval. Why not express it in a way that readily highlights this fact?

max(a, ...) means “I want the result to be at least a“.
min(b, ...) means “I want the result to be at most b“.

Making both thresholds into first arguments to their respective functions is just one of those nice small things that very subtly, almost invisibly, will make your code easier to work with.

Maksimum, minimum

Programiś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 void minmax(const C& c, T* min, T* max)
{
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.