# Laboratorio de la semana 3: predecir el crecimiento y medirlo

Los comandos se corren desde `code/week-03`. Las ideas están en los apuntes, en
[notes/week-03.md](../../../notes/week-03.md).

| Archivo | Qué es | ¿Lo cambian? |
|---|---|---|
| `work.h` | `Work`: un paso de trabajo que cuesta Θ(1) y se puede contar | No |
| `mysteries.h`, `mysteries.cpp` | Las seis funciones misteriosas | No |
| `measure.h` | `Row` y `seconds_per_call` | No |
| `measure.cpp` | El medidor | **Sí** |
| `run_doubling.cpp` | Corre el experimento con las seis y escribe un CSV | No |
| `vector_ops.h` | Lo que debe hacer cada operación de la sesión 2 | No |
| `vector_ops.cpp` | Las cuatro operaciones | **Sí** |
| `run_session2.cpp` | Los experimentos de la sesión 2 | **Sí** |
| `lab_tests.cpp`, `check.h` | Las pruebas públicas | No |
| `report.md` | Su informe | **Sí** |

```sh
make lab        # compila en build/lab/ las pruebas y los programas que miden
make test-lab   # comprueba todo; falla hasta que terminen
```

Los programas que miden se compilan con `-O2` y sin sanitizers. También se compila una copia con
`-O0` de cada uno, con el sufijo `_O0`. Las pruebas sí llevan sanitizers. Los tiempos dependen de su
máquina y de lo que esté corriendo en ella, así que ninguna prueba compara tiempos: comparan cuentas.

Cada sesión está pensada para unos 90 minutos de trabajo, y el resto queda para preguntar.

## Sesión 1

### Paso 1: predecir, sin correr nada (30 minutos)

Lean `mysteries.cpp`. Para cada función, anoten en `report.md` su clase de crecimiento y una línea que la
justifique. Sumen vueltas, o dibujen el árbol de llamadas. Si la función tiene varias partes, sumen las
partes. No corran nada todavía: si miden primero, ya no están prediciendo.

Una predicción equivocada no es un error del laboratorio. Corregirla a escondidas sí sería un problema, porque lo que
se aprende está en explicar la diferencia.

### Paso 2: el medidor (40 minutos)

En `measure.cpp`, escriban `fill_ratios`, `doubling_experiment` y `write_csv`. Lean antes
`seconds_per_call` en `measure.h`.

```sh
make lab && build/lab/lab_tests
```

Las pruebas se detienen en la primera falla y dicen cuál es. Las tres primeras son de este paso. Después de
pasarlas, `lab_tests` sigue con las de la sesión 2 y falla ahí: es lo esperado por ahora.

### Paso 3: duplicar (20 minutos)

```sh
build/lab/run_doubling build/lab/doubling.csv
```

Tarda unos segundos. Para cada función, llenen las dos últimas columnas de la tabla del informe. Lean las columnas
así:

- `razon` es T(n) / T(n/2). Cerca de 2 sugiere algo casi lineal, y cerca de 4, cuadrático.
- `T-Tant` es lo que sumó esta duplicación. Sirve cuando la razón se acerca a 1.
- `T/n` es el tiempo por elemento. Sirve para distinguir n de n log n.

No se queden solo con la última fila: miren la tabla entera.

## Sesión 2

### Paso 4: `push_back` frente a `insert` al inicio (25 minutos)

En `vector_ops.cpp`, escriban `fill_back` y `fill_front`. En `run_session2.cpp`, escriban
`measure_fill`. Todavía no expliquen por qué `push_back` es tan barato si el arreglo a veces tiene que
crecer: esa cuenta es de la semana 4. Sí expliquen `insert` al inicio: ¿cuántos elementos mueve?

### Paso 5: búsqueda lineal frente a binaria (30 minutos)

Escriban `linear_search` y `binary_search` en `vector_ops.cpp`, y `measure_search` en `run_session2.cpp`.
Busquen el peor caso de las dos y expliquen cómo lo lograron. Cuidado con buscar siempre la misma key: se
miden muchas llamadas seguidas, y el procesador puede aprender el camino.

```sh
make lab && build/lab/run_session2 build/lab/session2.csv
```

### Paso 6: `-O0` y `-O2` (20 minutos)

```sh
build/lab/run_doubling_O0 build/lab/doubling_O0.csv
build/lab/run_session2_O0 build/lab/session2_O0.csv
```

Comparen con los CSV de `-O2`. ¿Qué cambió? ¿Qué no cambió? ¿Cambió lo mismo en todas las operaciones?
Escriban las secciones de la sesión 2 y la conclusión con los números que obtuvieron.

```sh
make test-lab
```