Estructuras, costos y UVa 11078 · Refuerzo PUJ 17 de octubre¶
La sesión empezó por lo que trae un archivo de entrada y cómo se lee, y siguió
con lo que cuesta cada operación sobre las estructuras de la biblioteca
estándar. Cada estructura se abrió por dentro: dónde quedan sus elementos en
memoria, qué guarda un puntero o un iterador y qué operación paga el precio
oculto. Varias cosas se comprobaron compilando en vivo: el vector que se muda
de bloque, la aritmética de punteros, la matriz de Python con filas repetidas,
la lista enlazada recorrida por índice y la pila de llamadas de un factorial
vista en gdb. La segunda parte cambió dos ciclos anidados por un recorrido
que arrastra el máximo, y con esa idea se resolvió UVa 11078 en C++ hasta
dejarlo listo para enviar.
Al terminar la sesión se espera poder:
- Leer una entrada por palabras en Python y en C++, sin depender de cómo vienen partidas las líneas.
- Dar el costo de leer, escribir, buscar y recorrer en cada estructura, y escoger la que hace barata la operación que se repite.
- Explicar por qué un
vectorque crece invalida sus iteradores y por qué recorrer una lista enlazada por índice cuesta \(\Theta(n^2)\). - Calcular a mano los índices de los hijos y del padre en un montículo guardado en arreglo, e insertar y extraer en él.
- Reconocer dos ciclos anidados donde el de adentro vuelve sobre lo que ya recorrió el de afuera, y reemplazarlos por un recorrido.
- Resolver UVa 11078 en \(\Theta(n)\) por caso, con la respuesta negativa bien inicializada.
Diapositivas y tablero¶
programacion-anotada.pdf,
135 páginas: las 132 del deck de programación del bloque con lo escrito encima
durante la sesión, y tres hojas de tablero insertadas. La página 25 tiene el
factorial con el árbol de llamadas y la pila de marcos dibujada sobre main;
la 26, la salida de backtrace en gdb; la 38, la inserción del 11 y la
extracción del tope en el montículo. Lo escrito a mano está sobre todo entre
las páginas 11 y 55: el borrado que corre elementos, las direcciones de un
arreglo de 4 en 4 bytes, el índice dentro del deque, la tabla hash con su
factor de carga y la traza del máximo de atrás.
La grabación de la sesión, partida en videos cortos por tema, está en la lista de reproducción del refuerzo.
Código de la sesión¶
Los programas, limpios y probados, están en codigo/sesion1:
| Archivo | Qué muestra |
|---|---|
punteros.cpp |
a[i] es *(a + i) y las direcciones avanzan de sizeof(int) en sizeof(int) |
iteradores_vector.cpp |
el vector que se queda sin capacidad se muda y deja colgando lo que apuntaba al bloque viejo |
matriz_referencias.py |
[[0] * m] * n repite la misma fila \(n\) veces |
lista_por_indice.cpp |
sumar una lista enlazada por índice contra seguir los next |
factorial.cpp |
la pila de llamadas, para mirarla en gdb |
uva11078.cpp, uva11078.py |
UVa 11078 en un recorrido |
uva11078_dos_ciclos.cpp |
UVa 11078 con dos ciclos, la forma directa que se escribió primero |
uva11078.in |
la muestra del enunciado |
Todos se compilan con
g++ -std=c++17 -Wall -Wextra -g -o programa programa.cpp
-Wall -Wextra avisa de variables sin inicializar, de formatos de printf
que no casan con el argumento y de otros errores que de otro modo aparecen
como un fallo en el juez. -g deja la información que necesita el depurador.
La entrada llega desde un archivo con <, la salida va a otro con >, y
diff compara la salida con la esperada:
./uva11078 < uva11078.in > salida.txt
diff salida.txt esperado.txt
Si diff no imprime nada, las dos coinciden.
Lo que trae la entrada¶
Dos archivos con los mismos números, partidos distinto:
| Archivo A | Archivo B |
|---|---|
5 |
5 |
3 -1 4 1 5 |
3 -1 |
4 1 |
|
5 |
Un programa que lee la segunda línea con input().split() funciona con A y
se queda con 3 -1 en B. Lo que no depende de las líneas es leer por
palabras:
- En Python,
datos = sys.stdin.read().split()trae toda la entrada partida en espacios y saltos de línea por igual, y un índiceposavanza sobre esa lista. - En C++,
scanf("%d", &x)salta todo el espacio en blanco antes del número, saltos de línea incluidos.
scanf recibe la dirección de cada variable, &a y &b: C pasa por valor
esa dirección, y con ella scanf escribe en la variable. Devuelve cuántos
valores leyó, y al llegar al final del archivo devuelve EOF. Por eso la
lectura de pares hasta que se acabe la entrada es
int a, b;
while (scanf("%d %d", &a, &b) == 2) {
printf("%d\n", a + b);
}
La entrada y la salida de C++ se escriben con scanf y printf. cin y
cout, con la configuración por defecto, se mantienen sincronizados
con la entrada estándar de C y suelen ser más lentos, lo que en un archivo de
cientos de miles de números se nota frente al límite de tiempo.
Lo que cuesta cada operación¶
| Operación | Python (list) |
C++ (vector) |
Costo |
|---|---|---|---|
| Acceder por posición | a[i] |
a[i] |
\(O(1)\) |
| Tamaño | len(a) |
a.size() |
\(O(1)\) |
| Agregar al final | a.append(x) |
a.push_back(x) |
\(O(1)\) amortizado |
| Quitar el último | a.pop() |
a.pop_back() |
\(O(1)\) |
| Insertar en \(p\) | a.insert(p, x) |
a.insert(a.begin() + p, x) |
\(O(n - p)\) |
| Borrar en \(p\) | del a[p] |
a.erase(a.begin() + p) |
\(O(n - p)\) |
| Buscar un valor | x in a |
recorrido con for |
\(O(n)\) |
| Máximo | max(a) |
recorrido con for |
\(O(n)\) |
Insertar o borrar en la posición \(p\) cuesta \(O(n - p)\) porque los elementos de la derecha se corren. Borrar el 2 de \([1, 2, 3, 4]\) deja un hueco en la casilla 1, y el 3 y el 4 pasan una casilla a la izquierda: queda \([1, 3, 4]\). Borrar el primero corre a todos.
x in a, max(a) y a.insert(0, x) caben en una línea y recorren la lista
entera. Dentro de un ciclo de \(n\) vueltas, el programa cuesta \(O(n^2)\). La
list de Python es un arreglo, no una lista enlazada.
Las estructuras y cómo están hechas¶
| Estructura | C++ | Python | Cómo está hecha |
|---|---|---|---|
| Arreglo dinámico | vector |
list |
un bloque contiguo que se muda cuando se llena |
| Lista enlazada | list |
nodos con punteros al siguiente y al anterior | |
| Doble extremo | deque |
collections.deque |
un mapa de bloques de tamaño fijo |
| Pila | stack |
list |
un arreglo o un deque, usado solo por el tope |
| Cola | queue |
collections.deque |
un deque, usado por los dos extremos |
| Tabla hash | unordered_map, unordered_set |
dict, set |
un arreglo de casillas y una función hash |
| Árbol balanceado | map, set |
un árbol rojo-negro | |
| Montículo | priority_queue |
heapq |
un árbol binario completo guardado en un arreglo |
Punteros, iteradores y memoria¶
Un puntero guarda una dirección. Un iterador generaliza esa idea a cualquier
contenedor: begin() apunta al primer elemento, end() a la casilla que
sigue al último, ++ avanza uno y -- retrocede uno. En un vector,
it + k salta \(k\) casillas en \(O(1)\); en una list el iterador solo avanza
o retrocede de a un nodo.
Cada programa usa tres zonas de memoria. Las variables locales y los parámetros viven en la pila de llamadas, que es pequeña. Los elementos de los contenedores van en el heap, que es donde caben los vectores grandes. Las variables globales tienen su propia zona, que existe durante todo el programa.
Arreglo dinámico: vector y list¶
Un vector guarda tres datos: el puntero al bloque, el tamaño y la
capacidad. Acceder a a[i] es calcular a + i, una suma, y por eso cuesta
\(O(1)\). Esa suma cuenta casillas, no bytes: si el bloque empieza en la
dirección 180 y cada int ocupa 4 bytes, la casilla 0 está en 180 y la 1 en
184. El salto lo decide el tipo del elemento, no el tamaño del arreglo.
int arreglo[100];
for (int i = 0; i < 100; i++) {
arreglo[i] = 10 * i;
}
for (int k = 0; k < 4; k++) {
printf("arreglo + %d esta en %p y guarda %d (arreglo[%d] = %d)\n", k,
(void *)(arreglo + k), *(arreglo + k), k, arreglo[k]);
}
En una corrida de punteros.cpp:
sizeof(int) = 4 bytes
arreglo + 0 esta en 0x7ffebd3f8300 y guarda 0 (arreglo[0] = 0)
arreglo + 1 esta en 0x7ffebd3f8304 y guarda 10 (arreglo[1] = 10)
arreglo + 2 esta en 0x7ffebd3f8308 y guarda 20 (arreglo[2] = 20)
arreglo + 3 esta en 0x7ffebd3f830c y guarda 30 (arreglo[3] = 30)
Las direcciones cambian de una corrida a otra; la distancia de 4 bytes entre
casillas, no. Escribir *(arreglo + k) en lugar de arreglo[k] no aporta
nada en un programa, pero muestra qué hace el corchete.
Cuando el tamaño alcanza la capacidad, el siguiente push_back pide un
bloque más grande, copia los elementos y libera el viejo. Esa mudanza cuesta
\(O(n)\); como la capacidad crece por un factor constante (GCC la duplica), las
mudanzas son pocas y push_back cuesta \(O(1)\) amortizado. Si se sabe cuántos
elementos van a llegar, a.reserve(n) pide el bloque de una vez, sin
inicializar nada, y el vector no se muda en el camino.
La mudanza tiene otra consecuencia: todo puntero o iterador al bloque viejo
queda colgando. iteradores_vector.cpp guarda la dirección del primer
elemento, borra uno y agrega dos:
vector<int> cosita = {1, 2, 3, 4};
vector<int>::iterator it = cosita.begin();
const int *antes = &*it;
cosita.erase(cosita.begin() + 2); // queda 1, 2, 4
cosita.push_back(20);
cosita.push_back(10); // el quinto elemento no cabe en la capacidad 4
if (antes == cosita.data()) {
printf("el bloque es el mismo\n");
} else {
printf("el vector se mudo: it y antes apuntan al bloque viejo\n");
}
inicio: tamano 4, capacidad 4, datos en 0x5578df139020
tras erase: tamano 3, capacidad 4, datos en 0x5578df139020
tras 2 push: tamano 5, capacidad 8, datos en 0x5578df13a050
el vector se mudo: it y antes apuntan al bloque viejo
Con el erase y el primer push_back el bloque sigue siendo el mismo. El
segundo push_back necesita una quinta casilla, el vector pasa a capacidad 8
en otra dirección, y desde ahí leer *it o *antes es comportamiento
indefinido: se toca memoria que ya se devolvió. Después de insertar en un
vector, los iteradores anteriores no se usan.
La list de Python también es un arreglo dinámico, pero de referencias: cada
casilla apunta a un objeto. De ahí la trampa de la matriz.
compartida = [[0] * m] * n
separadas = [[0] * m for _ in range(n)]
compartida[0][0] = 1
separadas[0][0] = 1
Con \(n = 3\) y \(m = 4\), matriz_referencias.py imprime
compartida tras compartida[0][0] = 1:
[1, 0, 0, 0]
[1, 0, 0, 0]
[1, 0, 0, 0]
separadas tras separadas[0][0] = 1:
[1, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
misma fila en compartida: True
misma fila en separadas: False
* n copia \(n\) veces la referencia a una sola fila, así que cambiar una
casilla las cambia todas. La comprensión crea una fila nueva en cada vuelta.
Lista enlazada: list de C++¶
Cada nodo guarda el dato y un puntero al siguiente; la list de C++ es
doblemente enlazada y guarda también un puntero al anterior. Con un iterador
puesto en una posición, insertar o borrar ahí cuesta \(O(1)\): se crea el nodo
y se cambian dos o cuatro punteros, sin correr a nadie. El precio está en la
memoria y en el acceso. Cada insert hace un new, y en una máquina de 64
bits cada nodo de list carga 16 bytes de punteros además del int de 4,
más lo que agregue el asignador; una lista simple carga 8.
No hay a[i] en una list. Para llegar a la posición \(i\) hay que salir de
la cabeza y avanzar \(i\) nodos, y un for que pide cada posición vuelve a la
cabeza en cada vuelta: \(0 + 1 + \cdots + (n-1) = n(n-1)/2\) pasos,
\(\Theta(n^2)\). lista_por_indice.cpp escribe la lista a mano y suma sus
\(n = 10\,000\) elementos de las dos formas.
// Vuelve a la cabeza y avanza i nodos: Theta(i).
int get(int i) {
Nodo *actual = head;
for (int j = 0; j < i; j++) {
actual = actual->next;
}
return actual->dato;
}
for (int i = 0; i < n; i++) { // por índice: Theta(n^2)
suma += lst.get(i);
}
Nodo *actual = lst.head; // por iterador: Theta(n)
while (actual != nullptr) {
suma += actual->dato;
actual = actual->next;
}
En tres corridas sin optimizar en un Ryzen 7 7435HS, por índice tardó entre
0,10 y 0,11 segundos y por iterador entre 19 y 28 microsegundos, miles de
veces menos. Las dos sumas dan 49 995 000. El archivo libera los nodos en
el destructor de Lista.
Doble extremo: deque¶
Un deque es un arreglo de punteros, el mapa, a bloques de tamaño fijo.
Insertar por cualquiera de los dos extremos escribe en la casilla libre del
bloque de la punta, y cuando ese bloque se llena se pide otro sin copiar los
demás. En libstdc++, la biblioteca de GCC, cada bloque ocupa 512 bytes; en el
collections.deque de Python, 64 elementos.
En el tablero el bloque es de \(B = 4\) casillas y el frente está en la
casilla 2 del bloque 0, así que \(\mathit{ini} = 2\). La posición \(s\) del
deque cae en
| Bloque | Casilla 0 | Casilla 1 | Casilla 2 | Casilla 3 |
|---|---|---|---|---|
| 0 | \(3\) (\(s = 0\)) | \(1\) (\(s = 1\)) | ||
| 1 | \(4\) (\(s = 2\)) | \(1\) (\(s = 3\)) | \(5\) (\(s = 4\)) | \(9\) (\(s = 5\)) |
| 2 | \(2\) (\(s = 6\)) | \(6\) (\(s = 7\)) |
Para \(s = 5\): \((2 + 5) / 4 = 1\) y \(7 \bmod 4 = 3\), la casilla 3 del bloque 1,
que guarda el 9. Una división y un módulo: d[s] es \(O(1)\) en C++. El
iterador del deque guarda el bloque y la casilla. El deque de Python no
calcula así: d[i] es \(O(1)\) cerca de los extremos y \(O(n)\) en la mitad, y
para leer por posición se usa list.
Pila: stack y la list de Python¶
El último que entra es el primero que sale. std::stack usa por defecto un
deque por debajo, y se le puede pedir un vector; en Python la pila es una
list con append, pop y a[-1], todos \(O(1)\). top y pop sobre una
pila vacía son comportamiento indefinido en C++, así que antes se pregunta
empty().
La pila de llamadas es una pila implícita. Cada llamada a una función empuja un marco con sus parámetros y sus variables locales, y al terminar lo saca.
long factorial(int n) {
long resultado;
if (n == 0) {
resultado = 1;
} else {
resultado = n * factorial(n - 1);
}
return resultado;
}
factorial(5) llama a factorial(4), que llama a factorial(3), y así
hasta factorial(0), que devuelve 1 sin llamar a nadie. En ese momento hay
seis marcos de factorial sobre el de main. Después se resuelven en orden
inverso: \(1 \cdot 1\), \(2 \cdot 1\), \(3 \cdot 2\), \(4 \cdot 6\) y \(5 \cdot 24 =
120\).
| Marco | n |
Espera | Devuelve |
|---|---|---|---|
factorial(0) |
0 | 1 | |
factorial(1) |
1 | factorial(0) |
1 |
factorial(2) |
2 | factorial(1) |
2 |
factorial(3) |
3 | factorial(2) |
6 |
factorial(4) |
4 | factorial(3) |
24 |
factorial(5) |
5 | factorial(4) |
120 |
main |
factorial(5) |
Para verlo en el depurador se compila con -g, se pone un punto de
interrupción en la línea del caso base y se pide la pila con backtrace:
$ g++ -std=c++17 -Wall -Wextra -g -o factorial factorial.cpp
$ gdb ./factorial
(gdb) break 8
(gdb) run
Breakpoint 1, factorial (n=0) at factorial.cpp:8
(gdb) backtrace
#0 factorial (n=0) at factorial.cpp:8
#1 0x0000555555555168 in factorial (n=1) at factorial.cpp:10
#2 0x0000555555555168 in factorial (n=2) at factorial.cpp:10
#3 0x0000555555555168 in factorial (n=3) at factorial.cpp:10
#4 0x0000555555555168 in factorial (n=4) at factorial.cpp:10
#5 0x0000555555555168 in factorial (n=5) at factorial.cpp:10
#6 0x0000555555555193 in main () at factorial.cpp:17
Cada marco tiene su propio n. Con next se avanza línea a línea y los
marcos desaparecen a medida que cada llamada devuelve su valor.
Esa pila tiene un tamaño fijo, típicamente 8 MB en Linux, y una recursión de
un millón de niveles suele desbordarla. Lo que se pasa por valor se copia en
cada marco: un vector pasado por valor a una función recursiva se copia
entero en cada llamada, y se pasa por referencia para no copiarlo. Python
corta antes, con un límite de 1000 niveles por defecto que se consulta con
sys.getrecursionlimit().
Cola: queue y collections.deque¶
El primero que entra es el primero que sale. std::queue envuelve un
deque: push agrega al final y pop quita del frente. En Python la cola es
collections.deque con append y popleft. Las dos operaciones son \(O(1)\),
porque el frente avanza sin correr a los demás. a.pop(0) sobre una list
corre todos los elementos una casilla, \(O(n)\), y una cola de \(n\) elementos
atendida así cuesta \(O(n^2)\).
Direccionamiento directo y tabla hash¶
Si las claves posibles son pocas, como las 26 letras, un arreglo de \(U\) casillas indexado por la clave responde todo en \(O(1)\): el direccionamiento directo. Cuando las claves posibles son muchas más que las que llegan, la tabla hash usa \(m\) casillas y una función \(h\) que lleva cada clave a una de ellas.
En el tablero, \(m = 5\) y \(h(k) = k \bmod 5\), con las claves 15, 12, 7, 22 y 4:
| Casilla | Claves |
|---|---|
| 0 | \(15\) |
| 1 | |
| 2 | \(12 \to 7 \to 22\) |
| 3 | |
| 4 | \(4\) |
12, 7 y 22 chocan en la casilla 2: es una colisión, y con encadenamiento cada casilla guarda una lista con las claves que caen ahí. El factor de carga es \(\alpha = n/m\), el largo promedio de esas listas. Si la función reparte las claves de manera uniforme e independiente, buscar cuesta \(\Theta(1 + \alpha)\) en promedio: el 1 por calcular \(h(k)\) y \(\alpha\) por recorrer la lista (CLRS, 3.ª ed., sección 11.2). La tabla crece cuando \(\alpha\) pasa de un umbral, de modo que \(\alpha\) se mantiene acotado y la búsqueda queda en \(O(1)\) en promedio.
unordered_map encadena, con un nodo por par. El dict de Python no usa
listas: si la casilla está ocupada, busca otra libre. Un set es una tabla
de claves sin valor, y por eso no guarda repetidos. Dos cuidados: cuando la
tabla crece, los iteradores de C++ dejan de valer, y en Python modificar un
dict mientras se recorre lanza RuntimeError. El orden en que se recorre
una tabla hash de C++ no tiene relación con el orden de las claves.
Árbol balanceado: map y set¶
En un árbol binario de búsqueda, lo menor que un nodo va a su izquierda y lo
mayor a su derecha; map y set no admiten claves repetidas. Buscar,
insertar y borrar cuestan \(O(h)\), con \(h\) la altura. Si las claves llegan
ordenadas, como 1, 2, 3, 4, 5, cada nodo cuelga a la derecha del anterior, el
árbol es una cadena de altura \(n\) y todo cuesta \(O(n)\): una lista enlazada es
el caso del árbol en que cada nodo tiene a lo sumo un hijo.
map y set de C++ son árboles rojo-negro: la raíz es negra, un nodo rojo no
tiene hijos rojos y todos los caminos de un nodo a sus hojas pasan por la
misma cantidad de nodos negros. Al insertar o borrar, rotaciones y cambios de
color restauran esas propiedades, y con ellas la altura queda en
\(O(\log n)\). El árbol del tablero, con raíz 8, hijos 4 y 12 y hojas 2, 6, 10
y 14, tiene altura 2 con siete nodos.
Montículo: priority_queue y heapq¶
Un montículo máximo es un árbol binario completo, con todos los niveles llenos salvo quizá el último, que se llena de izquierda a derecha, y en el que cada padre es mayor o igual que sus hijos. Por la forma, se guarda en un arreglo por niveles, sin punteros. Con la raíz en la posición 0:
| Posición | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| Valor | 9 | 7 | 8 | 3 | 5 | 6 |
\(\mathrm{hiz}(0) = 1\) y \(\mathrm{hder}(0) = 2\): el 7 y el 8 son hijos del 9. \(\mathrm{hiz}(2) = 5\), el 6. \(P(2) = 0\) y \(P(4) = 1\): el 5 es hijo del 7.
Insertar el 11¶
Entra en la primera casilla libre, la 6, como hijo derecho del 8, y sube mientras sea mayor que su padre.
| Paso | Arreglo | Compara |
|---|---|---|
| Entra en la posición 6 | \(9, 7, 8, 3, 5, 6, \mathbf{11}\) | \(11 > 8 = P(6)\), sube |
| Pasa a la posición 2 | \(9, 7, \mathbf{11}, 3, 5, 6, 8\) | \(11 > 9 = P(2)\), sube |
| Llega a la raíz | \(\mathbf{11}, 7, 9, 3, 5, 6, 8\) |
Extraer el tope¶
Se parte del montículo original \(9, 7, 8, 3, 5, 6\). El 9 sale, el último, 6, pasa a la raíz y baja intercambiándose con el mayor de sus hijos mientras alguno lo supere.
| Paso | Arreglo | Compara |
|---|---|---|
| El 6 pasa a la raíz | \(\mathbf{6}, 7, 8, 3, 5\) | hijos 7 y 8, el mayor es 8 |
| Baja a la posición 2 | \(8, 7, \mathbf{6}, 3, 5\) | \(\mathrm{hiz}(2) = 5\) no existe, para |
Las dos operaciones hacen a lo sumo un intercambio por nivel, y un árbol completo de \(n\) nodos tiene altura \(\lfloor \log_2 n \rfloor\): \(O(\log n)\). Leer el tope es \(O(1)\). Buscar un valor cualquiera es \(O(n)\), porque el montículo solo garantiza que el padre supera a los hijos, no dónde está cada valor.
priority_queue de C++ guarda el arreglo en un vector, no tiene
iteradores y deja arriba el mayor. heapq de Python trabaja sobre una list
y deja en h[0] el menor. Para el menor en C++ se declara
priority_queue<int, vector<int>, greater<int>>; para el mayor en Python se
guardan los valores con el signo cambiado.
Las tablas de costos¶
Leer es consultar un elemento sin quitarlo; escribir, insertarlo; buscar, preguntar si un valor está; recorrer, visitar todos una vez. Recorrer cuesta \(O(n)\); lo que cuesta \(O(1)\) es avanzar un paso.
| Estructura | Leer | Escribir | Buscar | Recorrer |
|---|---|---|---|---|
| Arreglo dinámico | \(O(1)\) en \(i\) | \(O(1)\) al final, \(O(n-p)\) en \(p\) | \(O(n)\) | \(O(n)\) |
| Lista enlazada | \(O(i)\) en \(i\) | \(O(1)\) en el iterador | \(O(n)\) | \(O(n)\) |
| Doble extremo | \(O(1)\) en los extremos | \(O(1)\) en los extremos | \(O(n)\) | \(O(n)\) |
| Pila | \(O(1)\) el tope | \(O(1)\) en el tope | no se busca | no se recorre |
| Cola | \(O(1)\) el frente | \(O(1)\) al final | no se busca | no se recorre |
| Estructura | Leer | Escribir | Buscar | Recorrer |
|---|---|---|---|---|
| Direccionamiento directo | \(O(1)\) | \(O(1)\) | \(O(1)\) | \(O(U)\) |
| Tabla hash | \(O(1)\) promedio | \(O(1)\) promedio | \(O(1)\) promedio | \(O(n)\), sin orden |
| Árbol balanceado | \(O(\log n)\) | \(O(\log n)\) | \(O(\log n)\) | \(O(n)\), en orden |
| Árbol binario de búsqueda | \(O(h)\) | \(O(h)\) | \(O(h)\) | \(O(n)\), en orden |
| Montículo | \(O(1)\) el tope | \(O(\log n)\) | \(O(n)\) | no en orden |
En un arreglo ordenado, la búsqueda binaria mira la mitad y descarta la otra:
\(T(n) = T(n/2) + O(1)\), que da \(O(\log n)\). Sin orden, buscar es \(O(n)\).
Ordenar cuesta \(O(n \log n)\) y se paga una vez. El \(O(1)\) de la tabla hash es
el caso promedio: si muchas claves caen en la misma casilla, buscar se vuelve
\(O(n)\), mientras que map cuesta \(O(\log n)\) siempre y además recorre las
claves en orden.
Para escoger, se escribe qué operación se repite dentro del ciclo principal y se busca la estructura donde esa operación es \(O(1)\) u \(O(\log n)\):
| El programa necesita | Estructura |
|---|---|
| Guardar la entrada y leerla por posición | arreglo dinámico |
| Deshacer: el último que entró sale primero | pila |
| Atender en orden de llegada | cola |
| Insertar en medio sin correr nada | lista enlazada |
| Contar cuántas veces aparece cada clave | tabla hash o map |
| Saber si un valor ya apareció | conjunto |
| Sacar siempre el menor o el mayor | montículo |
| El vecino de un valor en orden | set o arreglo ordenado |
| Visitar por capas desde un origen | cola |
Un recorrido en vez de dos¶
Si lo que se necesita de las casillas anteriores se puede actualizar con la que acaba de entrar, el segundo recorrido sobra: ese dato se guarda en una variable y se actualiza en la misma vuelta. El máximo, el mínimo, la suma, el conteo de los que cumplen algo y el mejor resultado visto se actualizan así en \(O(1)\). El caso se reconoce por dos ciclos anidados donde el de adentro vuelve a mirar lo que el de afuera ya recorrió.
Con \(v = [4, 7, 2, 9, 5]\), para cada posición \(j\) se busca el mayor valor que quedó atrás, entre \(v[0]\) y \(v[j-1]\):
| \(j\) | Lo de atrás | Mayor atrás |
|---|---|---|
| 0 | nada | |
| 1 | \(v[0..0] = 4\) | 4 |
| 2 | \(v[0..1] = 4, 7\) | 7 |
| 3 | \(v[0..2] = 4, 7, 2\) | 7 |
| 4 | \(v[0..3] = 4, 7, 2, 9\) | 9 |
La fila de abajo, 4, 7, 7, 9, nunca baja, y cambia solo cuando el que acaba de pasar supera a todos los anteriores.
La forma directa vuelve a recorrer lo de atrás para cada \(j\):
def maximos_dos_ciclos(v):
res = [None] * len(v)
for j in range(1, len(v)):
mayor = v[0]
for i in range(1, j):
if v[i] > mayor:
mayor = v[i]
res[j] = mayor
return res
Para \(j = 1\) mira una casilla, para \(j = 2\) dos, y para \(j = n - 1\) mira \(n - 1\):
del orden de \(n^2\). Con \(n = 100\,000\) son unos \(5 \cdot 10^9\) pasos.
Lo de atrás de \(j = 3\) es \(4, 7, 2\) y lo de atrás de \(j = 2\) es \(4, 7\): se diferencian en una sola casilla, la que acaba de entrar. El mayor de atrás de \(j + 1\) es el mayor entre el que ya se tenía para \(j\) y \(v[j]\).
def maximos_un_recorrido(v):
res = [None] * len(v)
mayor = v[0]
for j in range(1, len(v)):
res[j] = mayor
if v[j] > mayor:
mayor = v[j]
return res
Una comparación por posición, \(n - 1\) en total: \(\Theta(n)\).
| \(j\) | \(v[j]\) | mayor al entrar |
mayor al salir |
|---|---|---|---|
| 1 | 7 | 4 | 7 |
| 2 | 2 | 7 | 7 |
| 3 | 9 | 7 | 9 |
| 4 | 5 | 9 | 9 |
Dentro de la vuelta, primero se usa mayor y después entra \(v[j]\). Al revés,
en \(j = 3\) se leería 9 como lo de atrás y la casilla se estaría comparando
consigo misma.
UVa 11078: Open Credit System¶
- Enunciado y envío: https://vjudge.net/problem/UVA-11078
Un curso tiene \(n\) estudiantes numerados por antigüedad: si \(i < j\), el estudiante \(i\) es más antiguo que el \(j\). Todos presentaron una prueba de nivel, y el profesor quiere la mayor diferencia que un antiguo le saca a uno más nuevo, el máximo de \(a[i] - a[j]\) con \(i < j\), sin valor absoluto. Si un antiguo saca 80 y un nuevo 70, la diferencia es 10. Llegan menos de 20 casos; en cada uno, \(2 \le n \le 100\,000\), un puntaje por línea y \(|a[i]| < 150\,000\). Sale un número por caso.
La muestra¶
| Caso | Puntajes | Respuesta |
|---|---|---|
| 1 | \(100, 20\) | \(100 - 20 = 80\) |
| 2 | \(4, 3, 2, 1\) | \(4 - 1 = 3\) |
| 3 | \(1, 2, 3, 4\) | \(1 - 2 = -1\) |
En el tercer caso la respuesta no es \(4 - 1 = 3\), porque el 4 es el último: es el más nuevo y tiene que ir a la derecha de la resta. Con \(i < j\), las parejas son \(1 - 2\), \(1 - 3\), \(1 - 4\), \(2 - 3\), \(2 - 4\) y \(3 - 4\), todas negativas, y la mayor es \(-1\). La respuesta puede ser negativa, y un programa que imprime 0 cuando ningún antiguo supera a uno nuevo falla este caso.
Todas las parejas¶
for (int i = 0; i < npts - 1; i++) {
for (int j = i + 1; j < npts; j++) {
if (pts[i] - pts[j] > diferencia) {
diferencia = pts[i] - pts[j];
}
}
}
El ciclo de adentro da \(n - 1 - i\) vueltas, \(n(n-1)/2\) parejas en total: con \(n = 100\,000\), unos \(5 \cdot 10^9\) por caso. Medido en Python para las diapositivas, en un Ryzen 7 7435HS, la versión de dos ciclos tarda 2,84 s con \(n = 10\,000\) y 11,32 s con \(n = 20\,000\): al duplicar \(n\) el tiempo se multiplica por 4, y con \(n = 100\,000\) serían unos 280 segundos por caso.
Fijar al más nuevo¶
Fijado el estudiante nuevo \(j\), el antiguo que le saca más es el de mayor puntaje entre \(a[0], \ldots, a[j-1]\), porque se resta siempre el mismo \(a[j]\). Ese mayor es el máximo de atrás de la sección anterior: al pasar de \(j\) a \(j + 1\) entra un solo candidato, \(a[j]\), y el máximo se actualiza con una comparación. La respuesta es el mejor \(\mathit{mayor} - a[j]\) que aparezca en el camino. Solo importa el máximo de los anteriores: el mínimo daría \(a[j] - a[i]\), que es otra resta.
Con \(a = [1, 9, 2, 8, 3]\), mayor arranca en \(a[0] = 1\) y diferencia en
\(a[0] - a[1] = -8\):
| \(j\) | \(a[j]\) | \(\mathit{mayor} - a[j]\) | diferencia |
mayor al salir |
|---|---|---|---|---|
| inicio | \(-8\) | 1 | ||
| 1 | 9 | \(1 - 9 = -8\) | \(-8\) | 9 |
| 2 | 2 | \(9 - 2 = 7\) | 7 | 9 |
| 3 | 8 | \(9 - 8 = 1\) | 7 | 9 |
| 4 | 3 | \(9 - 3 = 6\) | 7 | 9 |
La respuesta es 7. Un recorrido con dos comparaciones por vuelta, \(\Theta(n)\) por caso.
La solución¶
vector<int> pts(100000);
int main() {
int casos;
scanf("%d", &casos);
for (int c = 0; c < casos; c++) {
int npts;
scanf("%d", &npts);
for (int p = 0; p < npts; p++) {
scanf("%d", &pts[p]);
}
int mayor = pts[0];
int diferencia = pts[0] - pts[1];
for (int i = 1; i < npts; i++) {
if (mayor - pts[i] > diferencia) {
diferencia = mayor - pts[i];
}
if (pts[i] > mayor) {
mayor = pts[i];
}
}
printf("%d\n", diferencia);
}
return 0;
}
El vector global tiene el tamaño máximo del enunciado, \(100\,000\), y se
reutiliza en cada caso. La diferencia está entre \(-300\,000\) y \(300\,000\), y
cabe en un int.
def mayor_diferencia(pts):
mayor = pts[0]
diferencia = pts[0] - pts[1]
for i in range(1, len(pts)):
if mayor - pts[i] > diferencia:
diferencia = mayor - pts[i]
if pts[i] > mayor:
mayor = pts[i]
return diferencia
def main():
datos = sys.stdin.read().split()
casos = int(datos[0])
pos = 1
for c in range(casos):
npts = int(datos[pos])
pts = []
for p in range(npts):
pts.append(int(datos[pos + 1 + p]))
pos = pos + 1 + npts
print(mayor_diferencia(pts))
Las dos versiones imprimen 80, 3 y \(-1\) con uva11078.in.
Dónde arranca el ciclo¶
La primera versión del recorrido tenía el ciclo desde i = 0 e imprimió 80,
3 y 0. En la vuelta \(i = 0\), mayor todavía es pts[0], así que
\(\mathit{mayor} - \mathit{pts}[0] = 0\): la pareja del primer estudiante
consigo mismo. En los dos primeros casos la respuesta es positiva y ese 0 no
estorba; en el tercero sí:
| \(i\) | \(\mathit{pts}[i]\) | \(\mathit{mayor} - \mathit{pts}[i]\) | diferencia |
mayor al salir |
|---|---|---|---|---|
| inicio | \(-1\) | 1 | ||
| 0 | 1 | \(1 - 1 = 0\) | 0 | 1 |
| 1 | 2 | \(1 - 2 = -1\) | 0 | 2 |
| 2 | 3 | \(2 - 3 = -1\) | 0 | 3 |
| 3 | 4 | \(3 - 4 = -1\) | 0 | 4 |
El ciclo empieza en i = 1, y diferencia arranca con una pareja que
existe, pts[0] - pts[1]. Arrancarla en 0 produce el mismo error por otro
camino: pasa los dos primeros casos e imprime 0 en el tercero. Escribir
max(a[:j]) dentro del ciclo, en Python, también falla: devuelve el programa
a \(O(n^2)\).
La actividad maximo-acumulado recorre el problema paso a paso.
Lo que sigue¶
De la sesión quedan UVa 507, Jill Rides Again, con el mejor tramo de un arreglo, y UVa 108, Maximum Sum, con las matrices y sus acumulados, además de la hora de lógica sobre proposiciones y predicados. Los enunciados, los enlaces de envío y las soluciones están en la página de la sesión y en las soluciones. Los tres pasan a la sesión del 24 de octubre, donde cada problema cierra con su costo en \(O\).