Semana 2 — Recurrencias y mergesort

Objetivos

Plantear la recurrencia del costo de un algoritmo recursivo.
Resolver recurrencias con árboles de recursión y con el teorema maestro.
Demostrar que mergesort es correcto.
Extender un algoritmo conocido para que calcule algo más: contar inversiones.

Sesión A — Recurrencias y teorema maestro

Lectura: Apuntes, semana 2.

Apoyo: Erickson, secs. 1.6 (The Pattern) y 1.7 (Recursion Trees). CLRS, capítulo Divide-and-Conquer, 4.ª edición.

Temas:

El patrón de divide y vencerás: dividir, resolver cada parte y combinar.
Del código a la recurrencia: T(n) = a·T(n/b) + f(n).
Árbol de recursión: trabajo por nivel, número de niveles y cuál manda.
Los tres casos: pesan más las hojas, todos los niveles por igual o pesa más la raíz. El teorema maestro.
Cuándo no aplica la versión de tres casos. T(n) = 2·T(n/2) + n log n queda entre dos casos: el árbol de recursión da Θ(n log² n), y una versión más general del teorema, como la de CLRS, también la cubre. T(n) = 2·T(n/2) + n / log n queda fuera incluso de esa, y el árbol da Θ(n log log n).
Comprobar una solución por inducción, y por qué hay que probar la constante exacta: T(n) ≤ cn no se sigue de T(n) ≤ cn + n.
Error común: ignorar el costo de copiar en cada llamada, como un std::vector pasado por valor.

Sesión B — Mergesort demostrado · Contar inversiones

Lectura: Apuntes, semana 2.

Apoyo: Erickson, sec. 1.4 (Mergesort). CLRS, capítulo Getting Started, 4.ª edición.

Temas:

Mergesort, ya conocido: invariante de la mezcla e inducción sobre n.
Inversiones: cuántos pares están en el orden contrario. Mide cuánto se parecen dos rankings.
Fuerza bruta en Θ(n²). Inversiones dentro de cada mitad y entre las dos.
Contar durante la mezcla: cuando un elemento de la derecha pasa primero, salta a todos los que quedan a la izquierda.
La respuesta puede llegar a n(n−1)/2: no cabe en int.
Error común: contar 1 en vez de todos los que quedan en la mitad izquierda.

Laboratorio — Comparar rankings

Con dos rankings de los mismos elementos, reducir el problema a contar inversiones en un solo arreglo.
Escribir primero la versión Θ(n²), y comprobar que el juez la acepta en los casos pequeños y da TLE en el grande.
Escribir la versión con mergesort y pasar todos los casos.
Medir con n y 2n, y comparar las razones con lo que predice la recurrencia.

Preguntas de repaso

Resuelvan con el teorema maestro: T(n) = 8T(n/2) + n², T(n) = 2T(n/2) + n, T(n) = 3T(n/2) + n, T(n) = T(n/2) + 1.
Dibujen el árbol de recursión de T(n) = 2T(n/2) + n log n. ¿Cuál es la solución?
Una búsqueda binaria recursiva recibe los índices lo y hi, y pasa todo el std::vector por valor en cada llamada. ¿Cuál es su recurrencia y su costo?
¿Cuántas inversiones tiene el arreglo 3, 1, 4, 2? ¿Cuál es el máximo para n elementos, y en qué arreglo se da?
Escriban la invariante de la mezcla de mergesort.

Código de la semana

Compilar y probar dentro del contenedor del curso con make y make test.

Ejemplos (16)Pruebas (1)Laboratorio (3)Compilación (1)

Ejemplos

Los programas que usan los apuntes y la clase.

brute_bench.cppDescargar

// Mide la fuerza bruta de las inversiones con n y 2n. Se compila con -O2 y sin sanitizers.
// Cada fila es el menor de 3 tiempos. Los tiempos dependen de la máquina.
#include <chrono>
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>

#include "inversions_brute.h"

int main() {
    std::mt19937 rng(2);
    std::cout << "n       inversiones  tiempo ms  razón\n" << std::fixed;
    double previous = 0;
    for (std::size_t n : {10000u, 20000u, 40000u, 80000u, 160000u}) {
        std::vector<int> a(n);
        for (int& x : a) {
            x = static_cast<int>(rng() >> 1);
        }
        double best = 1e18;
        long long inversions = 0;
        for (int run = 0; run < 3; run++) {
            auto start = std::chrono::steady_clock::now();
            inversions = count_inversions_brute(a);
            auto end = std::chrono::steady_clock::now();
            best = std::min(best, std::chrono::duration<double, std::milli>(end - start).count());
        }
        std::cout << std::left << std::setw(8) << n << std::setw(13) << inversions << std::right << std::setw(9)
                  << std::setprecision(1) << best;
        if (previous > 0) {
            std::cout << std::setw(7) << std::setprecision(2) << best / previous;
        }
        std::cout << '\n';
        previous = best;
    }
}

comparison_count.hDescargar

// Cuenta las comparaciones entre elementos que hace mergesort.
#pragma once

#include <bit>
#include <cstddef>
#include <vector>

inline void counting_sort_range(std::vector<int>& a, std::vector<int>& buffer, std::size_t lo, std::size_t hi,
                                long long& comparisons) {
    if (hi - lo <= 1) {
        return;
    }
    std::size_t mid = lo + (hi - lo) / 2;
    counting_sort_range(a, buffer, lo, mid, comparisons);
    counting_sort_range(a, buffer, mid, hi, comparisons);
    std::size_t i = lo;
    std::size_t j = mid;
    for (std::size_t k = lo; k < hi; k++) {
        bool take_left;
        if (j == hi) {
            take_left = true;
        } else if (i == mid) {
            take_left = false;
        } else {
            comparisons++;
            take_left = a[i] <= a[j];
        }
        buffer[k] = take_left ? a[i++] : a[j++];
    }
    for (std::size_t k = lo; k < hi; k++) {
        a[k] = buffer[k];
    }
}

// Ordena una copia de a y devuelve cuántas comparaciones hizo.
inline long long count_comparisons(std::vector<int> a) {
    std::vector<int> buffer(a.size());
    long long comparisons = 0;
    counting_sort_range(a, buffer, 0, a.size(), comparisons);
    return comparisons;
}

// La recurrencia del peor caso: C(1) = 0 y C(n) = C(piso(n/2)) + C(techo(n/2)) + n - 1.
inline long long worst_case_recurrence(std::size_t n) {
    if (n <= 1) {
        return 0;
    }
    return worst_case_recurrence(n / 2) + worst_case_recurrence(n - n / 2) + static_cast<long long>(n) - 1;
}

// Su forma cerrada, con L = techo(log n): C(n) = n L - 2^L + 1.
inline long long worst_case_formula(std::size_t n) {
    std::size_t power = std::bit_ceil(n);
    long long ceil_log = std::countr_zero(power);
    return static_cast<long long>(n) * ceil_log - static_cast<long long>(power) + 1;
}

// Una entrada que obliga a n - 1 comparaciones en cada mezcla. Se reparte el resultado ordenado
// de forma alternada, para que la mezcla saque un elemento de cada lado hasta el final.
inline std::vector<int> worst_case_input(const std::vector<int>& sorted) {
    if (sorted.size() <= 1) {
        return sorted;
    }
    std::vector<int> left;
    std::vector<int> right;
    for (std::size_t i = 0; i < sorted.size(); i++) {
        // La mitad derecha tiene techo(n/2) elementos: se queda con las posiciones pares.
        (i % 2 == 0 ? right : left).push_back(sorted[i]);
    }
    std::vector<int> result = worst_case_input(left);
    std::vector<int> tail = worst_case_input(right);
    result.insert(result.end(), tail.begin(), tail.end());
    return result;
}

comparisons.cppDescargar

// Cuenta las comparaciones de mergesort con varias entradas.
#include <iostream>
#include <numeric>
#include <random>
#include <string>
#include <vector>

#include "comparison_count.h"

static std::string pad(long long value, std::size_t width) {
    std::string text = std::to_string(value);
    return text + std::string(width > text.size() ? width - text.size() : 1, ' ');
}

int main() {
    std::mt19937 rng(2);
    std::cout << "n        ordenado  invertido al azar  peor      fórmula\n";
    for (std::size_t n : {16u, 17u, 1000u, 1024u, 65536u, 1000000u}) {
        std::vector<int> sorted(n);
        std::iota(sorted.begin(), sorted.end(), 0);
        std::vector<int> reversed(sorted.rbegin(), sorted.rend());
        std::vector<int> shuffled = sorted;
        for (std::size_t i = n - 1; i > 0; i--) {
            std::swap(shuffled[i], shuffled[rng() % (i + 1)]);
        }
        std::cout << pad(static_cast<long long>(n), 9) << pad(count_comparisons(sorted), 10)
                  << pad(count_comparisons(reversed), 10) << pad(count_comparisons(shuffled), 9)
                  << pad(count_comparisons(worst_case_input(sorted)), 10) << worst_case_formula(n) << '\n';
    }
}

copy_bench.cppDescargar

// Mide mergesort con el auxiliar por referencia y por valor. Se compila con -O2 y sin sanitizers.
// Cada fila es el menor de 3 tiempos. Los tiempos dependen de la máquina.
#include <chrono>
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>

#include "copy_cost.h"

template <typename Sort>
static double measure_ms(const std::vector<int>& input, Sort sort) {
    double best = 1e18;
    for (int run = 0; run < 3; run++) {
        std::vector<int> a = input;
        auto start = std::chrono::steady_clock::now();
        sort(a);
        auto end = std::chrono::steady_clock::now();
        best = std::min(best, std::chrono::duration<double, std::milli>(end - start).count());
    }
    return best;
}

int main() {
    std::mt19937 rng(2);
    std::cout << "n       referencia ms  razón  por valor ms  razón\n" << std::fixed;
    double previous_good = 0;
    double previous_bad = 0;
    for (std::size_t n : {2000u, 4000u, 8000u, 16000u, 32000u}) {
        std::vector<int> input(n);
        for (int& x : input) {
            x = static_cast<int>(rng() >> 1);
        }
        double good = measure_ms(input, [](std::vector<int>& a) { merge_sort(a); });
        double bad = measure_ms(input, [](std::vector<int>& a) {
            std::vector<int> buffer(a.size());
            sort_range_buffer_by_value(a, buffer, 0, a.size());
        });
        std::cout << std::left << std::setw(8) << n << std::right << std::setprecision(2) << std::setw(13) << good;
        if (previous_good > 0) {
            std::cout << std::setw(7) << good / previous_good;
        } else {
            std::cout << std::setw(7) << "";
        }
        std::cout << std::setw(14) << bad;
        if (previous_bad > 0) {
            std::cout << std::setw(7) << bad / previous_bad;
        }
        std::cout << '\n';
        previous_good = good;
        previous_bad = bad;
    }
}

copy_cost.hDescargar

// Búsqueda binaria y mergesort que copian de más, con un elemento que cuenta sus copias.
#pragma once

#include <cstddef>
#include <vector>

#include "merge_sort.h"

// Cada vez que se construye por copia, por ejemplo al copiar un std::vector, suma 1 al contador.
struct Counted {
    int value = 0;
    long long* copies = nullptr;

    Counted() = default;
    Counted(int v, long long* counter) : value(v), copies(counter) {}
    Counted(const Counted& other) : value(other.value), copies(other.copies) {
        if (copies != nullptr) {
            (*copies)++;
        }
    }
    Counted& operator=(const Counted& other) = default;

    bool operator<=(const Counted& other) const { return value <= other.value; }
};

inline std::vector<Counted> counted_range(int n, long long* counter) {
    std::vector<Counted> a;
    a.reserve(n);
    for (int i = 0; i < n; i++) {
        a.emplace_back(i, counter);
    }
    return a;
}

// Recibe el arreglo completo por valor: cada llamada copia n elementos, por chico que sea [lo, hi).
inline int search_whole_copy(std::vector<Counted> a, std::size_t lo, std::size_t hi, int target, int& calls) {
    calls++;
    if (lo == hi) {
        return -1;
    }
    std::size_t mid = lo + (hi - lo) / 2;
    if (a[mid].value == target) {
        return static_cast<int>(mid);
    }
    if (target < a[mid].value) {
        return search_whole_copy(a, lo, mid, target, calls);
    }
    return search_whole_copy(a, mid + 1, hi, target, calls);
}

// Copia solo la mitad que sigue: cada llamada paga el tamaño de su propio subproblema.
inline bool search_half_copy(const std::vector<Counted>& a, int target, int& calls) {
    calls++;
    if (a.empty()) {
        return false;
    }
    std::size_t mid = a.size() / 2;
    if (a[mid].value == target) {
        return true;
    }
    if (target < a[mid].value) {
        std::vector<Counted> half(a.begin(), a.begin() + static_cast<std::ptrdiff_t>(mid));
        return search_half_copy(half, target, calls);
    }
    std::vector<Counted> half(a.begin() + static_cast<std::ptrdiff_t>(mid) + 1, a.end());
    return search_half_copy(half, target, calls);
}

// La misma búsqueda sin copiar nada: el costo por llamada es constante.
inline int search_by_reference(const std::vector<Counted>& a, std::size_t lo, std::size_t hi, int target, int& calls) {
    calls++;
    if (lo == hi) {
        return -1;
    }
    std::size_t mid = lo + (hi - lo) / 2;
    if (a[mid].value == target) {
        return static_cast<int>(mid);
    }
    if (target < a[mid].value) {
        return search_by_reference(a, lo, mid, target, calls);
    }
    return search_by_reference(a, mid + 1, hi, target, calls);
}

// Mergesort con el error: el arreglo auxiliar se recibe por valor, y cada llamada lo copia entero.
template <typename T>
void sort_range_buffer_by_value(std::vector<T>& a, std::vector<T> buffer, std::size_t lo, std::size_t hi) {
    if (hi - lo <= 1) {
        return;
    }
    std::size_t mid = lo + (hi - lo) / 2;
    sort_range_buffer_by_value(a, buffer, lo, mid);
    sort_range_buffer_by_value(a, buffer, mid, hi);
    merge_ranges(a, buffer, lo, mid, hi);
}

copy_count.cppDescargar

// Cuenta las copias de elementos en una búsqueda binaria y en mergesort, según cómo se pase el arreglo.
// La búsqueda es la del peor caso: un valor menor que todos, que siempre sigue por la izquierda.
#include <iostream>
#include <string>
#include <vector>

#include "copy_cost.h"

int main() {
    std::cout << "búsqueda binaria\n";
    std::cout << "n        llamadas  entero por valor  solo la mitad  por referencia\n";
    for (int n : {1024, 2048, 4096, 8192}) {
        long long whole = 0;
        int calls = 0;
        std::vector<Counted> a = counted_range(n, &whole);
        search_whole_copy(a, 0, a.size(), -1, calls);

        long long half = 0;
        int half_calls = 0;
        std::vector<Counted> b = counted_range(n, &half);
        search_half_copy(b, -1, half_calls);

        long long reference = 0;
        int reference_calls = 0;
        std::vector<Counted> c = counted_range(n, &reference);
        search_by_reference(c, 0, c.size(), -1, reference_calls);

        std::cout << n << "     " << calls << std::string(10 - std::to_string(calls).size(), ' ') << whole
                  << std::string(18 - std::to_string(whole).size(), ' ') << half
                  << std::string(15 - std::to_string(half).size(), ' ') << reference << '\n';
    }

    std::cout << "\nmergesort con el auxiliar por valor\n";
    std::cout << "n        llamadas  copias\n";
    for (int n : {1024, 2048, 4096}) {
        long long copies = 0;
        std::vector<Counted> a = counted_range(n, &copies);
        sort_range_buffer_by_value(a, a, 0, a.size());
        long long calls = 2LL * n - 1;
        std::cout << n << "     " << calls << std::string(10 - std::to_string(calls).size(), ' ') << copies << '\n';
    }
}

from_code.hDescargar

// Tres funciones que no hacen nada útil: solo suman 1 por cada unidad de trabajo, para comparar
// lo que cuestan con la recurrencia que se lee en su código.
#pragma once

// T(n) = 2 T(n/2) + n
inline void two_calls_linear(int n, long long& work) {
    if (n <= 1) {
        work++;
        return;
    }
    for (int i = 0; i < n; i++) {
        work++;
    }
    two_calls_linear(n / 2, work);
    two_calls_linear(n / 2, work);
}

// T(n) = 3 T(n/2) + n
inline void three_calls_linear(int n, long long& work) {
    if (n <= 1) {
        work++;
        return;
    }
    for (int call = 0; call < 3; call++) {
        three_calls_linear(n / 2, work);
    }
    for (int i = 0; i < n; i++) {
        work++;
    }
}

// T(n) = 8 T(n/2) + n²
inline void eight_calls_quadratic(int n, long long& work) {
    if (n <= 1) {
        work++;
        return;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            work++;
        }
    }
    for (int call = 0; call < 8; call++) {
        eight_calls_quadratic(n / 2, work);
    }
}

inversions_brute.hDescargar

// Inversiones por fuerza bruta: se revisan todos los pares. Cuesta Θ(n²).
#pragma once

#include <cstddef>
#include <vector>

inline long long count_inversions_brute(const std::vector<int>& a, std::size_t lo, std::size_t hi) {
    long long count = 0;
    for (std::size_t i = lo; i < hi; i++) {
        for (std::size_t j = i + 1; j < hi; j++) {
            if (a[i] > a[j]) {
                count++;
            }
        }
    }
    return count;
}

inline long long count_inversions_brute(const std::vector<int>& a) {
    return count_inversions_brute(a, 0, a.size());
}

// Pares (x, y) con x en a[lo, mid), y en a[mid, hi) y x > y.
inline long long count_cross_brute(const std::vector<int>& a, std::size_t lo, std::size_t mid, std::size_t hi) {
    long long count = 0;
    for (std::size_t i = lo; i < mid; i++) {
        for (std::size_t j = mid; j < hi; j++) {
            if (a[i] > a[j]) {
                count++;
            }
        }
    }
    return count;
}

inversions.cppDescargar

// Inversiones por fuerza bruta: las de unos arreglos chicos y, en cada nodo del árbol de mergesort,
// cuántas quedan dentro de cada mitad y cuántas cruzan.
#include <cstddef>
#include <iostream>
#include <vector>

#include "inversions_brute.h"

static void print_pairs(const std::vector<int>& a) {
    for (std::size_t i = 0; i < a.size(); i++) {
        std::cout << (i == 0 ? "" : " ") << a[i];
    }
    std::cout << ": " << count_inversions_brute(a) << " inversiones:";
    for (std::size_t i = 0; i < a.size(); i++) {
        for (std::size_t j = i + 1; j < a.size(); j++) {
            if (a[i] > a[j]) {
                std::cout << " (" << a[i] << "," << a[j] << ")";
            }
        }
    }
    std::cout << '\n';
}

static void print_node(const std::vector<int>& a, std::size_t lo, std::size_t hi) {
    if (hi - lo <= 1) {
        return;
    }
    std::size_t mid = lo + (hi - lo) / 2;
    std::cout << "[" << lo << "," << hi << ")  izquierda " << count_inversions_brute(a, lo, mid) << "  derecha "
              << count_inversions_brute(a, mid, hi) << "  cruzadas " << count_cross_brute(a, lo, mid, hi) << "  total "
              << count_inversions_brute(a, lo, hi) << '\n';
    print_node(a, lo, mid);
    print_node(a, mid, hi);
}

int main() {
    print_pairs({3, 1, 4, 2});
    print_pairs({1, 2, 3, 4});
    print_pairs({4, 3, 2, 1});
    std::cout << '\n';
    print_node({5, 2, 6, 1, 4, 3}, 0, 6);
}

merge_bench.cppDescargar

// Mide mergesort con n y 2n, con datos al azar. Se compila con -O2 y sin sanitizers.
// Cada fila es el menor de 3 tiempos. Los tiempos dependen de la máquina.
#include <chrono>
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>

#include "merge_sort.h"

static double measure_ms(const std::vector<int>& input) {
    double best = 1e18;
    for (int run = 0; run < 3; run++) {
        std::vector<int> a = input;
        auto start = std::chrono::steady_clock::now();
        merge_sort(a);
        auto end = std::chrono::steady_clock::now();
        best = std::min(best, std::chrono::duration<double, std::milli>(end - start).count());
    }
    return best;
}

int main() {
    std::mt19937 rng(2);
    std::cout << "n         tiempo ms  razón  predice 2(k+1)/k\n" << std::fixed;
    double previous = 0;
    for (int k = 17; k <= 23; k++) {
        std::size_t n = std::size_t{1} << k;
        std::vector<int> input(n);
        for (int& x : input) {
            x = static_cast<int>(rng() >> 1);
        }
        double ms = measure_ms(input);
        std::cout << std::left << std::setw(10) << n << std::right << std::setw(9) << std::setprecision(1) << ms;
        if (previous > 0) {
            std::cout << std::setw(7) << std::setprecision(2) << ms / previous << std::setw(9)
                      << 2.0 * k / (k - 1);
        }
        std::cout << '\n';
        previous = ms;
    }
}

merge_sort_demo.cppDescargar

// Sigue mergesort sobre un arreglo: imprime cada mezcla en el orden en que ocurre.
#include <cstddef>
#include <iostream>
#include <vector>

#include "merge_sort.h"

static void print_range(const std::vector<int>& a, std::size_t lo, std::size_t hi) {
    for (std::size_t i = lo; i < hi; i++) {
        std::cout << (i == lo ? "" : " ") << a[i];
    }
}

static void traced_sort(std::vector<int>& a, std::vector<int>& buffer, std::size_t lo, std::size_t hi) {
    if (hi - lo <= 1) {
        return;
    }
    std::size_t mid = lo + (hi - lo) / 2;
    traced_sort(a, buffer, lo, mid);
    traced_sort(a, buffer, mid, hi);
    std::cout << "mezclar [" << lo << "," << mid << ") y [" << mid << "," << hi << "): ";
    print_range(a, lo, mid);
    std::cout << " | ";
    print_range(a, mid, hi);
    merge_ranges(a, buffer, lo, mid, hi);
    std::cout << " -> ";
    print_range(a, lo, hi);
    std::cout << '\n';
}

int main() {
    std::vector<int> a = {5, 2, 6, 1, 4, 3};
    std::vector<int> buffer(a.size());
    traced_sort(a, buffer, 0, a.size());
}

merge_sort.hDescargar

// Mergesort sobre un std::vector, con un solo arreglo auxiliar para toda la recursión.
#pragma once

#include <cstddef>
#include <vector>

// Mezcla a[lo, mid) y a[mid, hi), ya ordenados, y deja ordenado a[lo, hi).
// Invariante, antes de cada vuelta: buffer[lo, k) tiene, ordenados, los elementos de a[lo, i) y
// de a[mid, j), y ninguno es mayor que algún elemento que todavía no se copió.
template <typename T>
void merge_ranges(std::vector<T>& a, std::vector<T>& buffer, std::size_t lo, std::size_t mid, std::size_t hi) {
    std::size_t i = lo;
    std::size_t j = mid;
    for (std::size_t k = lo; k < hi; k++) {
        // Con <=, en un empate pasa primero el de la izquierda: eso hace estable el orden.
        if (j == hi || (i < mid && a[i] <= a[j])) {
            buffer[k] = a[i];
            i++;
        } else {
            buffer[k] = a[j];
            j++;
        }
    }
    for (std::size_t k = lo; k < hi; k++) {
        a[k] = buffer[k];
    }
}

template <typename T>
void sort_range(std::vector<T>& a, std::vector<T>& buffer, std::size_t lo, std::size_t hi) {
    if (hi - lo <= 1) {
        return;
    }
    std::size_t mid = lo + (hi - lo) / 2;
    sort_range(a, buffer, lo, mid);
    sort_range(a, buffer, mid, hi);
    merge_ranges(a, buffer, lo, mid, hi);
}

template <typename T>
void merge_sort(std::vector<T>& a) {
    std::vector<T> buffer(a.size());
    sort_range(a, buffer, 0, a.size());
}

merge_trace.cppDescargar

// Sigue una sola mezcla, vuelta por vuelta. Cuando pasa un elemento de la derecha, también dice
// cuántos elementos seguían en la izquierda.
#include <cstddef>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> a = {2, 5, 6, 1, 3, 4};
    std::size_t mid = 3;
    std::size_t hi = a.size();
    std::size_t i = 0;
    std::size_t j = mid;
    std::cout << "k  i  j  pasa  de         quedan a la izquierda\n";
    for (std::size_t k = 0; k < hi; k++) {
        std::cout << k << "  " << i << "  " << j << "  ";
        if (j == hi || (i < mid && a[i] <= a[j])) {
            std::cout << a[i] << "     izquierda  -\n";
            i++;
        } else {
            std::cout << a[j] << "     derecha    " << mid - i << '\n';
            j++;
        }
    }
}

recurrences.cppDescargar

// Compara T(n), calculado con la recurrencia, con la solución que dice la teoría. Si la solución
// es correcta, la razón se acerca a una constante. Es aritmética: no corre ningún algoritmo, y por
// eso puede llegar a n = 2^1024.
#include <cmath>
#include <iomanip>
#include <iostream>

#include "recurrences.h"

int main() {
    std::cout << "log n  8T+n^2   3T+n     T+1      2T+n     2T+nlogn  2T+n/logn\n";
    std::cout << "       /n^3     /n^1,585 /log n   /nlogn   /nlog^2n  /nloglogn\n";
    std::cout << std::fixed << std::setprecision(3);
    long double log2_of_3 = std::log2(3.0L);
    for (int k = 4; k <= 1024; k *= 2) {
        long double kk = k;
        long double n = std::ldexp(1.0L, k);
        std::cout << std::left << std::setw(7) << k << std::right;
        std::cout << std::setw(5) << solve_power_of_two<long double>(8, k, f_n2) / (n * n * n) << "    ";
        std::cout << std::setw(5) << solve_power_of_two<long double>(3, k, f_n) / std::pow(n, log2_of_3) << "    ";
        std::cout << std::setw(5) << solve_power_of_two<long double>(1, k, f_one) / kk << "    ";
        std::cout << std::setw(5) << solve_power_of_two<long double>(2, k, f_n) / (n * kk) << "    ";
        std::cout << std::setw(5) << solve_power_of_two<long double>(2, k, f_n_log_n) / (n * kk * kk) << "     ";
        std::cout << std::setw(5) << solve_power_of_two<long double>(2, k, f_n_over_log_n) / (n * std::log2(kk)) << '\n';
    }
}

recurrences.hDescargar

// Evalúa recurrencias T(n) = a T(n/2) + f(n), con T(1) = 1, en las potencias de 2.
#pragma once

#include <cmath>
#include <vector>

// Devuelve T(2^k). f recibe k, de modo que f(k) es el valor de f en n = 2^k.
template <typename V, typename F>
V solve_power_of_two(int a, int k, F f) {
    V value = 1;
    for (int m = 1; m <= k; m++) {
        value = static_cast<V>(a) * value + f(m);
    }
    return value;
}

// El trabajo de cada nivel para n = 2^k. El nivel i tiene a^i subproblemas de tamaño 2^(k-i), y
// la última casilla son las hojas, cada una con T(1) = 1.
template <typename V, typename F>
std::vector<V> level_work(int a, int k, F f) {
    std::vector<V> levels;
    V nodes = 1;
    for (int i = 0; i < k; i++) {
        levels.push_back(nodes * f(k - i));
        nodes *= a;
    }
    levels.push_back(nodes);
    return levels;
}

// La f de cada recurrencia, en función de k = log n.
inline long double f_one(int) { return 1; }
inline long double f_n(int k) { return std::ldexp(1.0L, k); }
inline long double f_n2(int k) { return std::ldexp(1.0L, 2 * k); }
inline long double f_n_log_n(int k) { return k * std::ldexp(1.0L, k); }
inline long double f_n_over_log_n(int k) { return std::ldexp(1.0L, k) / k; }

recursion_tree.cppDescargar

// Imprime el trabajo de cada nivel del árbol de recursión.
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

#include "recurrences.h"

template <typename F>
static void print_tree(const std::string& title, int a, int k, F f) {
    std::cout << title << ", n = " << (1 << k) << '\n';
    std::vector<long double> levels = level_work<long double>(a, k, f);
    long double total = 0;
    for (std::size_t i = 0; i < levels.size(); i++) {
        if (i + 1 == levels.size()) {
            std::cout << "  hojas   ";
        } else {
            std::cout << "  nivel " << i << " ";
        }
        std::cout << std::setw(8) << std::fixed << std::setprecision(2) << levels[i] << '\n';
        total += levels[i];
    }
    std::cout << "  total   " << std::setw(8) << total << "\n\n";
}

int main() {
    print_tree("8 T(n/2) + n^2", 8, 4, f_n2);
    print_tree("2 T(n/2) + n", 2, 4, f_n);
    print_tree("2 T(n/2) + n^2", 2, 4, f_n2);
    print_tree("2 T(n/2) + n log n", 2, 4, f_n_log_n);
    print_tree("2 T(n/2) + n / log n", 2, 4, f_n_over_log_n);
}

Pruebas

Comprueban lo que afirman los apuntes; se ejecutan con make test.

test_examples.cppDescargar

// Comprueba lo que afirman los apuntes de la semana. Falla con assert si algo no se cumple.
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <iostream>
#include <limits>
#include <numeric>
#include <random>
#include <vector>

#include "comparison_count.h"
#include "copy_cost.h"
#include "from_code.h"
#include "inversions_brute.h"
#include "merge_sort.h"
#include "recurrences.h"

static std::vector<int> random_values(std::mt19937& rng, std::size_t n, unsigned range) {
    std::vector<int> a(n);
    for (int& x : a) {
        x = static_cast<int>(rng() % range);
    }
    return a;
}

static void test_merge_sort() {
    std::vector<int> empty;
    merge_sort(empty);
    assert(empty.empty());
    std::vector<int> one = {7};
    merge_sort(one);
    assert(one == std::vector<int>{7});
    std::vector<int> two = {2, 1};
    merge_sort(two);
    assert((two == std::vector<int>{1, 2}));

    std::mt19937 rng(1);
    for (int round = 0; round < 2000; round++) {
        std::vector<int> a = random_values(rng, rng() % 40, round % 2 == 0 ? 5 : 1000);
        std::vector<int> expected = a;
        std::sort(expected.begin(), expected.end());
        merge_sort(a);
        assert(a == expected);
    }
}

struct Item {
    int key = 0;
    int tag = 0;
    bool operator<=(const Item& other) const { return key <= other.key; }
};

// Con <= en la mezcla, los elementos con la misma clave conservan su orden original.
static void test_stability() {
    std::mt19937 rng(2);
    for (int round = 0; round < 500; round++) {
        std::vector<Item> a(rng() % 50);
        for (std::size_t i = 0; i < a.size(); i++) {
            a[i] = {static_cast<int>(rng() % 4), static_cast<int>(i)};
        }
        merge_sort(a);
        for (std::size_t i = 1; i < a.size(); i++) {
            assert(a[i - 1].key <= a[i].key);
            assert(a[i - 1].key != a[i].key || a[i - 1].tag < a[i].tag);
        }
    }
}

// La invariante de los apuntes, comprobada en cada vuelta de la mezcla, con y sin repetidos.
static void test_merge_invariant() {
    std::mt19937 rng(3);
    for (int round = 0; round < 2000; round++) {
        std::vector<int> left = random_values(rng, rng() % 12, 6 + round % 50);
        std::vector<int> right = random_values(rng, rng() % 12, 6 + round % 50);
        std::sort(left.begin(), left.end());
        std::sort(right.begin(), right.end());
        std::vector<int> a = left;
        a.insert(a.end(), right.begin(), right.end());
        std::size_t mid = left.size();
        std::size_t hi = a.size();
        std::vector<int> buffer(hi);
        std::size_t i = 0;
        std::size_t j = mid;
        for (std::size_t k = 0; k <= hi; k++) {
            // (1) Se copiaron exactamente a[0, i) y a[mid, j).
            assert(i + (j - mid) == k);
            std::vector<int> copied(a.begin(), a.begin() + static_cast<std::ptrdiff_t>(i));
            copied.insert(copied.end(), a.begin() + static_cast<std::ptrdiff_t>(mid),
                          a.begin() + static_cast<std::ptrdiff_t>(j));
            std::sort(copied.begin(), copied.end());
            std::vector<int> prefix(buffer.begin(), buffer.begin() + static_cast<std::ptrdiff_t>(k));
            // (2) El prefijo está ordenado y tiene esos mismos elementos.
            assert(prefix == copied);
            // (3) Nada de lo copiado es mayor que algo de lo que falta.
            if (k > 0) {
                for (std::size_t p = i; p < mid; p++) {
                    assert(buffer[k - 1] <= a[p]);
                }
                for (std::size_t p = j; p < hi; p++) {
                    assert(buffer[k - 1] <= a[p]);
                }
            }
            if (k == hi) {
                break;
            }
            if (j == hi || (i < mid && a[i] <= a[j])) {
                buffer[k] = a[i++];
            } else {
                buffer[k] = a[j++];
            }
        }
    }
}

static void test_recurrences() {
    // Las formas cerradas de los apuntes, exactas con enteros, para n = 2^k.
    using Int = long long;
    for (int k = 0; k <= 20; k++) {
        Int n = Int{1} << k;
        auto one = [](int) -> Int { return 1; };
        auto linear = [](int m) -> Int { return Int{1} << m; };
        auto quadratic = [](int m) -> Int { return Int{1} << (2 * m); };
        auto n_log_n = [](int m) -> Int { return m * (Int{1} << m); };
        assert(solve_power_of_two<Int>(2, k, linear) == n * k + n);
        assert(solve_power_of_two<Int>(1, k, one) == k + 1);
        assert(solve_power_of_two<Int>(2, k, one) == 2 * n - 1);
        assert(solve_power_of_two<Int>(2, k, quadratic) == 2 * n * n - n);
        assert(solve_power_of_two<Int>(2, k, n_log_n) == n * k * (k + 1) / 2 + n);
        if (k <= 16) {
            assert(solve_power_of_two<Int>(8, k, quadratic) == 2 * n * n * n - n * n);
        }
        // 3T(n/2) + n: 3^(k+1) - 2n, donde 3^k = n^(log 3).
        Int power_of_three = 1;
        for (int i = 0; i <= k; i++) {
            power_of_three *= 3;
        }
        assert(solve_power_of_two<Int>(3, k, linear) == power_of_three - 2 * n);
    }
    // 2T(n/2) + n / log n: T(n) = n (H_k + 1), con H_k = 1 + 1/2 + ... + 1/k.
    long double harmonic = 0;
    for (int k = 1; k <= 200; k++) {
        harmonic += 1.0L / k;
        long double n = std::ldexp(1.0L, k);
        long double value = solve_power_of_two<long double>(2, k, f_n_over_log_n);
        assert(std::fabs(value / n - (harmonic + 1)) < 1e-12L);
        // Y cada nivel i cuesta n / (k - i).
        std::vector<long double> levels = level_work<long double>(2, k, f_n_over_log_n);
        for (int i = 0; i < k; i++) {
            assert(std::fabs(levels[static_cast<std::size_t>(i)] / n - 1.0L / (k - i)) < 1e-12L);
        }
    }
}

// Lo que cuesta cada función de from_code.h es lo que dice su recurrencia.
static void test_from_code() {
    for (int k = 0; k <= 10; k++) {
        int n = 1 << k;
        auto linear = [](int m) -> long long { return 1LL << m; };
        auto quadratic = [](int m) -> long long { return 1LL << (2 * m); };
        long long work = 0;
        two_calls_linear(n, work);
        assert(work == solve_power_of_two<long long>(2, k, linear));
        work = 0;
        three_calls_linear(n, work);
        assert(work == solve_power_of_two<long long>(3, k, linear));
        if (k <= 6) {
            work = 0;
            eight_calls_quadratic(n, work);
            assert(work == solve_power_of_two<long long>(8, k, quadratic));
        }
    }
}

static void test_copies() {
    for (int k = 0; k <= 13; k++) {
        int n = 1 << k;
        // Con el arreglo entero por valor: n copias por cada llamada, k + 2 llamadas contando la primera
        // y la del rango vacío.
        long long whole = 0;
        int calls = 0;
        std::vector<Counted> a = counted_range(n, &whole);
        assert(search_whole_copy(a, 0, a.size(), -1, calls) == -1);
        assert(calls == k + 2);
        assert(whole == static_cast<long long>(calls) * n);

        // Copiando la mitad: 2^(k-1) + 2^(k-2) + ... + 1 = n - 1 copias.
        long long half = 0;
        int half_calls = 0;
        std::vector<Counted> b = counted_range(n, &half);
        assert(!search_half_copy(b, -1, half_calls));
        assert(half == n - 1);

        // Por referencia, ninguna.
        long long reference = 0;
        int reference_calls = 0;
        std::vector<Counted> c = counted_range(n, &reference);
        assert(search_by_reference(c, 0, c.size(), -1, reference_calls) == -1);
        assert(reference == 0);
        assert(reference_calls == calls);
    }
    // Mergesort con el auxiliar por valor: 2n - 1 llamadas, cada una copia n elementos.
    for (int n : {1, 2, 3, 7, 100, 1000}) {
        long long copies = 0;
        std::vector<Counted> a = counted_range(n, &copies);
        std::reverse(a.begin(), a.end());
        copies = 0;  // Invertir también copia: solo interesan las copias de la recursión.
        sort_range_buffer_by_value(a, a, 0, a.size());
        assert(copies == (2LL * n - 1) * n);
        for (int i = 0; i < n; i++) {
            assert(a[static_cast<std::size_t>(i)].value == i);
        }
    }
}

static void test_comparisons() {
    for (std::size_t n = 1; n <= 2000; n++) {
        assert(worst_case_recurrence(n) == worst_case_formula(n));
        std::vector<int> sorted(n);
        std::iota(sorted.begin(), sorted.end(), 0);
        std::vector<int> worst = worst_case_input(sorted);
        assert(count_comparisons(worst) == worst_case_formula(n));
        // Y ninguna entrada se pasa de esa cota.
        assert(count_comparisons(sorted) <= worst_case_formula(n));
    }
    std::mt19937 rng(4);
    for (int round = 0; round < 2000; round++) {
        std::vector<int> a = random_values(rng, 1 + rng() % 64, 100);
        assert(count_comparisons(a) <= worst_case_formula(a.size()));
    }
    // En potencias de 2 la fórmula es n log n - n + 1.
    for (int k = 0; k <= 20; k++) {
        long long n = 1LL << k;
        assert(worst_case_formula(static_cast<std::size_t>(n)) == n * k - n + 1);
    }
}

static void test_inversions() {
    assert(count_inversions_brute({3, 1, 4, 2}) == 3);
    assert(count_inversions_brute({5, 2, 6, 1, 4, 3}) == 9);
    assert(count_inversions_brute({}) == 0);
    assert(count_inversions_brute({1}) == 0);
    assert(count_inversions_brute({2, 2, 2}) == 0);

    // El máximo es n(n-1)/2, y entre permutaciones solo lo alcanza la invertida.
    for (int n = 1; n <= 8; n++) {
        std::vector<int> p(static_cast<std::size_t>(n));
        std::iota(p.begin(), p.end(), 0);
        long long best = 0;
        int attained = 0;
        do {
            long long count = count_inversions_brute(p);
            if (count > best) {
                best = count;
                attained = 1;
            } else if (count == best) {
                attained++;
            }
        } while (std::next_permutation(p.begin(), p.end()));
        assert(best == n * (n - 1) / 2);
        assert(attained == 1);
    }
    // Con n = 65 537 ya no cabe en int; con 65 536, todavía sí.
    assert(65536LL * 65535 / 2 <= std::numeric_limits<int>::max());
    assert(65537LL * 65536 / 2 > std::numeric_limits<int>::max());

    std::mt19937 rng(5);
    for (int round = 0; round < 2000; round++) {
        std::vector<int> a = random_values(rng, rng() % 30, round % 2 == 0 ? 4 : 100);
        std::size_t mid = a.size() / 2;
        // Inversiones = dentro de la izquierda + dentro de la derecha + cruzadas.
        assert(count_inversions_brute(a) == count_inversions_brute(a, 0, mid) + count_inversions_brute(a, mid, a.size()) +
                                                count_cross_brute(a, 0, mid, a.size()));
        // Ordenar cada mitad no cambia las cruzadas.
        std::vector<int> halves = a;
        std::sort(halves.begin(), halves.begin() + static_cast<std::ptrdiff_t>(mid));
        std::sort(halves.begin() + static_cast<std::ptrdiff_t>(mid), halves.end());
        assert(count_cross_brute(a, 0, mid, a.size()) == count_cross_brute(halves, 0, mid, a.size()));
    }
}

// Cada intercambio de vecinos cambia las inversiones en exactamente 1, y ordenar intercambiando
// vecinos desordenados hace tantos intercambios como inversiones había.
static void test_adjacent_swaps() {
    std::mt19937 rng(6);
    for (int round = 0; round < 1000; round++) {
        std::vector<int> a(1 + rng() % 25);
        std::iota(a.begin(), a.end(), 0);
        for (std::size_t i = a.size() - 1; i > 0; i--) {
            std::swap(a[i], a[rng() % (i + 1)]);
        }
        long long inversions = count_inversions_brute(a);
        long long swaps = 0;
        for (std::size_t pass = 0; pass < a.size(); pass++) {
            for (std::size_t i = 0; i + 1 < a.size(); i++) {
                if (a[i] > a[i + 1]) {
                    long long before = count_inversions_brute(a);
                    std::swap(a[i], a[i + 1]);
                    assert(count_inversions_brute(a) == before - 1);
                    swaps++;
                }
            }
        }
        assert(swaps == inversions);
    }
}

// En una mezcla, cuando pasa un elemento de la derecha, los que quedan a la izquierda son justo los
// mayores que él. Sumar 1 por cada uno, en cambio, se queda corto. Se compara con los pares contados uno por uno.
static void test_merge_step() {
    // El ejemplo de los apuntes: 3 pasos desde la derecha, pero 7 pares cruzados.
    std::vector<int> example = {2, 5, 6, 1, 3, 4};
    assert(count_cross_brute(example, 0, 3, 6) == 7);

    std::mt19937 rng(7);
    for (int round = 0; round < 3000; round++) {
        std::vector<int> left = random_values(rng, rng() % 15, round % 2 == 0 ? 5 : 100);
        std::vector<int> right = random_values(rng, rng() % 15, round % 2 == 0 ? 5 : 100);
        std::sort(left.begin(), left.end());
        std::sort(right.begin(), right.end());
        std::size_t i = 0;
        std::size_t j = 0;
        while (i < left.size() || j < right.size()) {
            if (j == right.size() || (i < left.size() && left[i] <= right[j])) {
                i++;
            } else {
                auto greater = static_cast<std::size_t>(
                    std::count_if(left.begin(), left.end(), [&](int x) { return x > right[j]; }));
                assert(greater == left.size() - i);
                j++;
            }
        }
    }
}

int main() {
    test_merge_sort();
    test_stability();
    test_merge_invariant();
    test_recurrences();
    test_from_code();
    test_copies();
    test_comparisons();
    test_inversions();
    test_adjacent_swaps();
    test_merge_step();
    std::cout << "todas las pruebas pasaron\n";
}

Laboratorio

Archivos de partida del laboratorio de la semana.

lab/compare_rankings/MakefileDescargar

TIEMPO = 2
include ../../../lab.mk

lab/compare_rankings/README.mdDescargar

# Comparar rankings

Un festival de cortometrajes pidió a dos jurados que ordenaran las mismas n películas, de la que más les gustó a la que menos.
Cada película tiene un código entre 1 y n. Los organizadores quieren saber cuánto se parecen las dos listas, y para eso cuentan los **pares en desacuerdo**: un par de
películas está en desacuerdo si el primer jurado pone a una antes que la otra, y el segundo jurado las pone al revés.

Dos listas iguales no tienen ningún par en desacuerdo. Una lista y esa misma lista al revés están en desacuerdo en todos los pares.

Escriban un programa que calcule cuántos pares están en desacuerdo.

## Entrada

La primera línea tiene el entero n, la cantidad de películas.

La segunda línea tiene n enteros: los códigos de las películas en el orden del primer jurado, del primer lugar al último.

La tercera línea tiene n enteros: los códigos en el orden del segundo jurado.

Cada una de las dos listas contiene cada código de 1 a n exactamente una vez.

## Salida

Una línea con la cantidad de pares de películas en desacuerdo.

## Límites

- 1 ≤ n ≤ 300 000.

## Ejemplo

Entrada:

```text
5
3 1 4 5 2
1 3 2 5 4
```

Salida:

```text
4
```

Los pares en desacuerdo son (3, 1), (4, 5), (4, 2) y (5, 2). Por ejemplo, el primer jurado pone a la película 3 antes que la 1, y el segundo, a la 1 antes que la 3.

## Tiempo

2 segundos por caso.

## Cómo trabajar

1. Reduzcan el problema: ¿cómo se escribe la pregunta sobre dos listas como una pregunta sobre un solo arreglo?
2. Escriban primero la versión que revisa todos los pares. Debe dar AC en los casos pequeños y TLE en los grandes. Guárdenla: les servirá para comparar respuestas en casos chicos al azar.
3. Escriban la versión rápida, y hagan que pase todos los casos.
4. Midan su versión final con n y con 2n. El generador del caso 08 acepta otro n:

   ```sh
   g++ -O2 -std=c++20 casos/gen_08.cpp -o build/gen_08
   build/gen_08 150000 > build/n.in
   build/gen_08 300000 > build/2n.in
   time build/solution < build/n.in
   time build/solution < build/2n.in
   ```

   Repitan varias veces y con varios tamaños, y comparen la razón entre los tiempos con la que predice la recurrencia de su algoritmo. ¿Qué pasa con esa razón en la versión que revisa todos los pares?

lab/compare_rankings/solution.cppDescargar

// Comparar rankings. Este esqueleto lee la entrada e imprime una respuesta incorrecta: el trabajo es suyo.
#include <iostream>
#include <vector>

int main() {
    int n;
    std::cin >> n;
    std::vector<int> first(n);
    std::vector<int> second(n);
    for (int& code : first) {
        std::cin >> code;
    }
    for (int& code : second) {
        std::cin >> code;
    }
    std::cout << -1 << '\n';
}

Compilación

Cómo se compilan y ejecutan los ejemplos.

MakefileDescargar

# Semana 2: recurrencias y mergesort. Se usa dentro del entorno del curso.
#
#   make           compila los programas de la clase en build/
#   make test      corre las pruebas de los ejemplos y de los apuntes
#   make bench     corre las mediciones, con -O2 y sin sanitizers
#   make clean     borra lo generado
#
# El laboratorio está en lab/compare_rankings/ y tiene su propio Makefile: make test
# no lo toca.

CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined
BENCHFLAGS = -Wall -Wextra -std=c++20 -O2
BUILD = build
PROGRAMS = merge_sort_demo merge_trace recursion_tree recurrences copy_count comparisons inversions test_examples
BENCHES = merge_bench copy_bench brute_bench
HEADERS = merge_sort.h comparison_count.h recurrences.h copy_cost.h inversions_brute.h from_code.h

.PHONY: all test bench clean

all: $(PROGRAMS:%=$(BUILD)/%) $(BENCHES:%=$(BUILD)/%)

$(PROGRAMS:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(HEADERS) | $(BUILD)
	$(CXX) $(CXXFLAGS) $< -o $@

# Las mediciones van con -O2 y sin sanitizers.
$(BENCHES:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(HEADERS) | $(BUILD)
	$(CXX) $(BENCHFLAGS) $< -o $@

$(BUILD):
	mkdir -p $@

test: all
	$(BUILD)/test_examples

bench: $(BENCHES:%=$(BUILD)/%)
	$(BUILD)/merge_bench
	$(BUILD)/copy_bench
	$(BUILD)/brute_bench

clean:
	rm -rf $(BUILD)