Millores d'eficiència

Per què?

Hi ha dues maneres d’arribar a un algorisme eficient: tenir una idea brillant des del principi, o bé escriure primer una solució correcta i senzilla i després millorar-la traient-ne els càlculs innecessaris. La segona és la més fiable, i és la que veuràs aquí.

Les eines són les mateixes immersions del disseny recursiu, però amb un objectiu diferent: no per poder fer la recursió, sinó per fer-la més ràpida.

Com es detecta un càlcul repetit

Mira la teva solució i pregunta’t:

• Es crida dues vegades la mateixa funció amb els mateixos paràmetres? (fib(n-1) i fib(n-2), que a dins torna a cridar fib(n-2)…)
• Dins d’una funció recursiva, es crida una altra funció que recorre el mateix que la recursió? (alcada dins d’equilibrat.)
• Dins d’un bucle, hi ha un altre bucle que recalcula una cosa que es podria anar actualitzant? (Sumar tots els elements de la dreta per a cada posició.)

Si la resposta és sí, hi ha marge per millorar.

Immersió per resultats

La idea: que la funció recursiva retorni més coses de les que demana el problema, perquè qui la crida les aprofiti i no les hagi de calcular.

Arbre equilibrat

Un arbre és equilibrat si, a cada node, les alçades dels dos fills difereixen com a molt en 1. La solució directa (la del capítol anterior) crida alcada a cada node i costa $\Theta(n^2)$ en el cas pitjor.

Però per saber si un subarbre és equilibrat, la recursió ja recorre tot el subarbre. Podria calcular-ne l’alçada al mateix temps i retornar-la:

// Pre: cert. Post: retorna si a és equilibrat; h és l'alçada de a.
bool equilibrat(const BinTree<int>& a, int& h) {
    if (a.empty()) {
        h = 0;
        return true;
    }
    int he, hd;
    bool ee = equilibrat(a.left(), he);
    bool ed = equilibrat(a.right(), hd);
    h = 1 + max(he, hd);
    return ee and ed and he - hd >= -1 and he - hd <= 1;
}

Ara cada node fa una feina constant a més de les seves dues crides: $\Theta(n)$.

La postcondició de la immersió és més forta que la de la funció original: diu més coses (també l’alçada). La funció original s’obté ignorant el resultat extra:

bool equilibrat(const BinTree<int>& a) {
    int h;
    return equilibrat(a, h);
}

Fibonacci

La funció de Fibonacci directa fa dues crides, fib(n-1) i fib(n-2), i és exponencial. Però si fib(n-1) retornés també fib(n-2), n’hi hauria prou amb una crida:

// Pre: n >= 1. Post: f = fib(n), g = fib(n-1).
void fib2(int n, long long& f, long long& g) {
    if (n == 1) {
        f = 1;
        g = 0;
    }
    else {
        long long f1, g1;
        fib2(n - 1, f1, g1);  // HI: f1 = fib(n-1), g1 = fib(n-2)
        f = f1 + g1;
        g = f1;
    }
}

Una crida per cada valor de $n$: $T(n) = T(n-1) + \Theta(1)$, és a dir, $\Theta(n)$. De $1{,}6^n$ a $n$.

La funció escala del tema anterior és la mateixa: escala(n) = fib(n+1). Per tant, fib2(n + 1, f, g) et dona la versió $\Theta(n)$.

Immersió per dades

L’altra direcció: passar a la crida recursiva informació que ja s’ha calculat, perquè no l’hagi de tornar a calcular. És el reforçament de la precondició del disseny recursiu.

Amb Fibonacci, en lloc de baixar fins a 1 i calcular en tornar, es pot anar pujant des del principi, portant els dos últims valors:

// Pre: 1 <= i <= n, a = fib(i-1), b = fib(i). Post: retorna fib(n).
long long fib_dades(int n, int i, long long a, long long b) {
    if (i == n) return b;
    return fib_dades(n, i + 1, b, a + b);
}
// fib(n) = fib_dades(n, 1, 0, 1), per a n >= 1

També és $\Theta(n)$, i és recursiva final: es pot passar a un bucle de manera mecànica (amb $a$ i $b$ com a variables).

Una immersió per dades també serveix quan els nodes d’un arbre necessiten informació dels seus avantpassats: la suma del camí des de l’arrel, la profunditat, el màxim que hi ha per sobre… En lloc de recalcular-la per a cada node, es passa cap avall com a paràmetre.

Millores en programes iteratius

Als bucles la idea és la mateixa: no recalculis el que pots anar actualitzant.

Sumes acumulades

Vols comptar quantes posicions d’un vector tenen un valor igual a la suma de tots els elements de la seva dreta. Directament:

for (int i = 0; i < n; ++i) {
    int s = 0;
    for (int j = i + 1; j < n; ++j) s += v[j];   // suma de la dreta, de nou cada vegada
    if (v[i] == s) ++compte;
}

$\Theta(n^2)$. Però la suma de la dreta de $i$ és la de $i + 1$ més $v[i+1]$: es pot anar actualitzant si es recorre el vector des del final.

// Pre: cert. Post: retorna quantes posicions i compleixen v[i] = suma de v[i+1..].
int iguals_suma_dreta(const vector<int>& v) {
    int compte = 0;
    int s = 0;  // suma de v[i+1..]
    int i = int(v.size()) - 1;
    // Inv: -1 <= i < v.size(), s = suma de v[i+1..], compte = posicions de v[i+1..] que compleixen
    while (i >= 0) {
        if (v[i] == s) ++compte;
        s += v[i];
        --i;
    }
    return compte;
}

$\Theta(n)$. Fixa’t que la millora apareix a l’invariant: hi hem afegit «$s$ = suma de $v[i+1..]$», una dada que el bucle manté i que estalvia el bucle de dins.

Rècords

Vols comptar quantes posicions d’un vector són un rècord: tenen un valor més gran que tots els de la seva esquerra. Directament, per a cada $i$ calcularies el màxim de $v[0..i-1]$ amb un bucle: $\Theta(n^2)$. Però el màxim de l’esquerra de $i+1$ és el de $i$ comparat amb $v[i]$: es pot anar actualitzant.

// Pre: cert. Post: retorna quantes posicions i tenen v[i] més gran que tots els de v[0..i-1].
int records(const vector<int>& v) {
    int n = int(v.size());
    if (n == 0) return 0;
    int compte = 1;     // v[0] sempre és un rècord
    int maxim = v[0];
    int i = 1;
    // Inv: 1 <= i <= n, maxim = màxim de v[0..i-1], compte = rècords de v[0..i-1]
    while (i < n) {
        if (v[i] > maxim) {
            ++compte;
            maxim = v[i];
        }
        ++i;
    }
    return compte;
}

$\Theta(n)$. Amb $[3, 1, 4, 1, 5, 9, 2, 6]$ en dona 4 (el 3, el 4, el 5 i el 9).

Errors habituals

Exercicis

// Pre: cert. Post: retorna quants nodes de a tenen un valor igual a la mida del seu subarbre;
//      m és la mida de a.
int iguals_mida(const BinTree<int>& a, int& m) {
    if (a.empty()) {
        m = 0;
        return 0;
    }
    int me, md;
    int n = iguals_mida(a.left(), me) + iguals_mida(a.right(), md);
    m = 1 + me + md;
    if (a.value() == m) ++n;
    return n;
}

// Pre: cert. Post: retorna el nombre de nodes del camí més llarg entre dos nodes de a;
//      h és l'alçada de a.
int diametre(const BinTree<int>& a, int& h) {
    if (a.empty()) {
        h = 0;
        return 0;
    }
    int he, hd;
    int de = diametre(a.left(), he);
    int dd = diametre(a.right(), hd);
    h = 1 + max(he, hd);
    return max(he + hd + 1, max(de, dd));
}

// Pre: s és la suma dels valors del camí des de l'arrel original fins al pare de a.
// Post: retorna quants nodes de a tenen un valor igual a la suma dels seus avantpassats.
int iguals_avantpassats(const BinTree<int>& a, int s) {
    if (a.empty()) return 0;
    int n = iguals_avantpassats(a.left(), s + a.value()) + iguals_avantpassats(a.right(), s + a.value());
    if (a.value() == s) ++n;
    return n;
}

// Pre: cert. Post: retorna la primera posició i tal que suma de v[0..i] = suma de v[i+1..], o -1.
int punt_equilibri(const vector<int>& v) {
    int total = 0;
    for (int x : v) total += x;
    int esq = 0;
    int i = 0;
    int r = -1;
    // Inv: 0 <= i <= v.size(), esq = suma de v[0..i-1], cap j < i és un punt d'equilibri;
    //      si r != -1, r = i i i és un punt d'equilibri
    while (i < int(v.size()) and r == -1) {
        if (esq + v[i] == total - esq - v[i]) r = i;
        else {
            esq += v[i];
            ++i;
        }
    }
    return r;
}

// Pre: n >= 0. Post: retorna fib(n).
long long fib_iter(int n) {
    if (n == 0) return 0;
    long long a = 0, b = 1;
    int i = 1;
    // Inv: 1 <= i <= n, a = fib(i-1), b = fib(i)
    while (i != n) {
        long long c = a + b;
        a = b;
        b = c;
        ++i;
    }
    return b;
}