Probleme – Le maximum glissant, ou pourquoi une file à deux bouts

1. La solution naïve. Pour chacune des $n-k+1$ fenêtres, on parcourt ses $k$ cases : $\Theta (nk)$ opérations. Pour $n=200000$ et $k=1000$, cela fait $198801999$ comparaisons — le compte exact, mesuré, de $(n-k+1)(k-1)$.

2. La solution linéaire. On tient une file d'indices, dont on retire aux deux bouts, et qui vérifie deux propriétés :

• les indices y sont croissants, donc les positions aussi ;
• les valeurs correspondantes y sont strictement décroissantes.

/* Range dans out[i] le maximum de t[i .. i+k-1], pour 0 <= i <= n-k.
   Precondition : 1 <= k <= n. Complexite : Theta(n). */
void max_glissant(const int* t, int n, int k, int* out) {
    int* d = malloc((size_t) n * sizeof(int));   /* file d'INDICES, [g, dr[ */
    int g = 0, dr = 0;
    for (int i = 0; i < n; i = i + 1) {
        while (dr > g && d[g] <= i - k) { g = g + 1; }        /* sorti par la gauche */
        while (dr > g && t[d[dr-1]] <= t[i]) { dr = dr - 1; } /* domine par t[i] */
        d[dr] = i; dr = dr + 1;
        if (i >= k - 1) { out[i-k+1] = t[d[g]]; }
    }
    free(d);
}

3. La preuve.

Invariant. Après le traitement de l'indice $i$, la file contient exactement les indices $j$ vérifiant les deux conditions

$$i-k<j\le i\text{et}t[j^{\prime }]<t[j]\text{ pour tout }{j}^{\prime }\text{ tel que }j<j^{\prime }\le i.$$

La première dit que $j$ est encore dans la fenêtre ; la seconde, qu'aucun indice plus récent ne porte une valeur au moins aussi grande. Autrement dit, la file retient exactement les candidats qui peuvent encore devenir maximum d'une fenêtre à venir. Comme les indices y sont rangés dans l'ordre croissant, la seconde condition impose que les valeurs y soient strictement décroissantes.

Justification des deux retraits. Un indice sorti par la gauche est hors fenêtre : il ne reviendra jamais, on peut le jeter. Un indice $j$ tel que $t[j]\le t[i]$ avec $j<i$ ne peut plus jamais être maximum : toute fenêtre future qui contient $j$ contient aussi $i$, puisque $i>j$ et que les fenêtres sont des intervalles glissant vers la droite. On peut donc le jeter aussi. Ces deux justifications sont exactement les deux boucles while.

Le maximum est en tête. Les valeurs sont décroissantes le long de la file, donc la plus grande est celle de l'indice de gauche ; et cet indice est dans la fenêtre, par la première boucle.

Le coût. Chaque indice est déposé une seule fois et retiré au plus une fois — par la gauche ou par la droite, jamais les deux. Le nombre total d'opérations sur la file est donc au plus $2n$, quel que soit $k$. Les deux boucles while ont beau être imbriquées dans la boucle for, elles ne font pas de ce code un $\Theta (nk)$ : on ne majore pas un coût total en majorant chaque tour, on l'obtient en comptant le travail imputable à chaque élément. C'est le même raisonnement amorti que la file à deux piles.

4. La mesure.

n = 200 000, k = 1000
  naif              : 198 801 999 operations,  0,231 s
  file a deux bouts :     399 991 operations,  0,003 s     (majorant 2n = 400 000)
  memes resultats sur les 199 001 fenetres : oui

Le compte mesuré, $399991$, est bien inférieur au majorant $2n=400000$ — et lui est presque égal, ce qui montre que la borne n'est pas grossière.

Vérification à la main sur un petit cas : pour [1 3 -1 -3 5 3 6 7] et $k=3$, l'algorithme rend 3 3 5 5 6 7, ce que l'on retrouve en lisant les six fenêtres.

Ce que ce problème ajoute au chapitre. La pile et la file du cours ne retirent qu'à une extrémité ; on vient d'utiliser une structure qui retire aux deux, la file à deux bouts. Elle se réalise exactement comme la file circulaire — deux indices et un modulo — et n'est pas plus chère. Et le gain, ici, n'est pas une constante : $\Theta (nk)$ contre $\Theta (n)$, soit un facteur $500$ mesuré pour $k=1000$. Le choix de la structure a changé l'ordre de grandeur, ce qui est le propos même du chapitre chap:abstraction.