Semana 5 — Búsqueda lineal, búsqueda binaria, notación O grande y jerarquía de memoria
La búsqueda es una de las operaciones más fundamentales y frecuentes en computación. Desde localizar un contacto en el teléfono hasta verificar si un DNI existe en una base de datos de millones de registros, buscar un elemento dentro de una colección es un problema que aparece en prácticamente todo programa.
Formalmente, el problema de búsqueda se define así: dada una secuencia de n elementos y un valor objetivo (la clave), determinar si la clave se encuentra en la secuencia y, de ser así, reportar su posición. El resultado es un índice (si se encontró) o una señal de ausencia (si no se encontró).
Entrada: una secuencia datos de n elementos y un valor clave del mismo tipo que los elementos.
Salida: el índice i tal que datos[i] == clave, o bien -1 si la clave no está en la secuencia.
Precondición general: la secuencia tiene al menos cero elementos (puede estar vacía).
En las semanas anteriores hemos utilizado búsquedas implícitas dentro de nuestros patrones de procesamiento de secuencias —por ejemplo, al recorrer una secuencia buscando un divisor o verificando una condición—. Esta semana formalizamos la búsqueda como algoritmo explícito, lo encapsulamos en funciones (aplicando la modularización de la Semana 4) y analizamos rigurosamente su eficiencia.
El patrón de búsqueda con condición de corte de la Semana 3 (búsqueda de divisor para determinar primalidad, verificación de propiedad) es una instancia del algoritmo de búsqueda lineal que aquí generalizamos. La modularización de la Semana 4 nos permite encapsular cada algoritmo de búsqueda en una función con un contrato claro: precondiciones, parámetros y valor de retorno.
La búsqueda lineal es el algoritmo más directo: recorrer la secuencia elemento por elemento, desde el primero hasta el último, comparando cada uno con la clave buscada. Si se encuentra una coincidencia, se reporta la posición; si se llega al final sin encontrarla, se reporta ausencia.
La condición del while tiene dos partes unidas por and: primero se verifica que el índice está dentro de los límites (i < n) y luego se compara el elemento (datos[i] != clave). Gracias a la evaluación en cortocircuito (Semana 3), si i < n es falso, Python no evalúa datos[i], evitando un acceso fuera de rango. Al salir del bucle, la inspección post-bucle determina cuál de las dos condiciones causó la salida.
Tracemos la ejecución para datos = [15, 27, 8, 63, 42, 91, 5, 36] y clave = 42:
| Iteración | i | i < n | datos[i] | datos[i] != 42 | Acción |
|---|---|---|---|---|---|
| 1 | 0 | True | 15 | True | i ← 1 |
| 2 | 1 | True | 27 | True | i ← 2 |
| 3 | 2 | True | 8 | True | i ← 3 |
| 4 | 3 | True | 63 | True | i ← 4 |
| 5 | 4 | True | 42 | False | Sale del while |
Al salir: i = 4, i < 8 es verdadero ⇒ retorna 4. Se realizaron 5 comparaciones con elementos de la secuencia.
| Tipo | Entrada | Resultado esperado | Justificación |
|---|---|---|---|
| Normal | datos=[3,7,1,9,4], clave=9 | 3 | Elemento interior de la secuencia |
| Normal | datos=[3,7,1,9,4], clave=5 | -1 | Elemento ausente |
| Límite | datos=[3,7,1,9,4], clave=3 | 0 | Primer elemento (mejor caso) |
| Límite | datos=[3,7,1,9,4], clave=4 | 4 | Último elemento (peor caso si existe) |
| Extremo | datos=[], clave=5 | -1 | Secuencia vacía |
| Extremo | datos=[42], clave=42 | 0 | Secuencia de un elemento, encontrado |
| Extremo | datos=[42], clave=7 | -1 | Secuencia de un elemento, no encontrado |
¿Cuántas comparaciones realiza la búsqueda lineal en una secuencia de n elementos?
En los tres casos, la cantidad de trabajo crece proporcionalmente a n. Decimos que la búsqueda lineal tiene complejidad O(n) —una notación que formalizaremos en la Sección 4.
La búsqueda lineal es simple y correcta, pero si vamos a buscar muchas veces en la misma secuencia —un escenario muy frecuente en la práctica—, existen estrategias que reducen el tiempo promedio de búsquedas sucesivas sin cambiar el peor caso. Estas optimizaciones se basan en una observación empírica: no todas las claves se buscan con la misma frecuencia. Si podemos reorganizar la secuencia para que los elementos más buscados estén más cerca del inicio, las búsquedas futuras serán más rápidas en promedio.
En muchos sistemas reales, un elemento accedido recientemente tiene alta probabilidad de ser accedido de nuevo en el futuro cercano. Este principio, conocido como localidad temporal, es el mismo que aprovecha la memoria caché del procesador (tema holístico de esta semana). Aplicado a la búsqueda, sugiere que los elementos recién encontrados deberían estar más cerca del inicio de la secuencia.
Si los elementos recién incorporados a la secuencia tienen mayor probabilidad de ser buscados en el futuro inmediato, la primera optimización es trivial: insertar siempre al comienzo de la lista en lugar de al final. Así, los elementos más nuevos —presumiblemente los más buscados— se encuentran primero.
En una lista de Python (implementada como arreglo dinámico), insert(0, x) tiene costo O(n) porque debe desplazar todos los elementos existentes una posición hacia la derecha. La inserción al final (append) es O(1) amortizado. Por lo tanto, la inserción al comienzo solo conviene si el beneficio en las búsquedas posteriores compensa su costo. En una lista enlazada (estructura que se estudia en cursos posteriores), la inserción al comienzo es O(1).
La heurística mover al frente funciona así: cada vez que una búsqueda encuentra el elemento buscado, ese elemento se mueve a la primera posición de la secuencia (desplazando los demás). Esto garantiza que los elementos buscados recientemente siempre están al inicio.
Ventaja: se adapta rápidamente a patrones de acceso cambiantes. Un elemento buscado una vez queda inmediatamente al inicio, por lo que una segunda búsqueda consecutiva es O(1).
Desventaja: una sola búsqueda esporádica de un elemento poco frecuente lo coloca al frente, desplazando a todos los demás. Si la distribución de búsquedas es estable, esto puede ser contraproducente.
La heurística de transposición es más conservadora: cada vez que se encuentra la clave, se la intercambia con el elemento inmediatamente anterior. Así, los elementos frecuentemente buscados «ascienden» gradualmente hacia el inicio, sin saltos bruscos.
| Aspecto | Sin optimización | Move-to-Front | Transposición |
|---|---|---|---|
| Tras encontrar | No modifica la secuencia | Mueve el elemento a posición 0 | Intercambia con el vecino anterior |
| Adaptación | Ninguna | Inmediata (un acceso basta) | Gradual (requiere múltiples accesos) |
| Estabilidad | Orden fijo | Baja: un acceso aislado altera todo | Alta: sube solo si se busca repetidamente |
| Costo de reorganización | 0 | O(n) en lista con arreglo; O(1) en lista enlazada | O(1) siempre (un solo swap) |
| Mejor escenario | — | Distribución que cambia frecuentemente | Distribución estable de frecuencias |
Supongamos datos = [A, B, C, D, E] y la secuencia de búsquedas: D, D, D, D.
Move-to-Front: tras la primera búsqueda de D (4 comparaciones), la lista queda [D, A, B, C, E]. Las tres búsquedas siguientes de D cuestan 1 comparación cada una. Total: 4 + 1 + 1 + 1 = 7 comparaciones.
Transposición: búsqueda 1 (4 comp.) → [A, B, D, C, E]; búsqueda 2 (3 comp.) → [A, D, B, C, E]; búsqueda 3 (2 comp.) → [D, A, B, C, E]; búsqueda 4 (1 comp.) → [D, A, B, C, E]. Total: 4 + 3 + 2 + 1 = 10 comparaciones.
En este caso, Move-to-Front es más eficiente. Pero si la búsqueda de D fuera esporádica entre muchas búsquedas de A, Transposición evitaría que D desplace injustamente a A del frente.
En la Semana 3, al comparar las series de Leibniz y Nilakantha para aproximar π, observamos que dos algoritmos pueden resolver el mismo problema con eficiencias radicalmente diferentes. También al optimizar la verificación de primalidad, reducimos los divisores a probar de n − 2 a ⌊√n⌋. ¿Cómo expresar esta diferencia de manera precisa? La respuesta es la notación O grande (Big-O notation).
La notación O grande describe cómo crece el tiempo de ejecución (o el uso de memoria) de un algoritmo a medida que crece el tamaño de la entrada n. No nos interesa el tiempo exacto en milisegundos (que depende del hardware, el sistema operativo y la carga del procesador), sino el orden de crecimiento: ¿se duplica el tiempo cuando se duplica n? ¿Se cuadruplica? ¿Apenas cambia?
Decimos que un algoritmo tiene complejidad O(f(n)) si, para entradas suficientemente grandes, su tiempo de ejecución crece a lo sumo como la función f(n), salvo una constante multiplicativa. Es una cota superior del crecimiento.
Formalmente: T(n) ∈ O(f(n)) si existen constantes c > 0 y n0 ≥ 1 tales que T(n) ≤ c · f(n) para todo n ≥ n0.
La siguiente tabla muestra las complejidades más frecuentes, ordenadas de menor a mayor crecimiento, con ejemplos de operaciones y el impacto concreto sobre la cantidad de operaciones para distintos valores de n:
| Notación | Nombre | Ejemplo | n=10 | n=100 | n=1.000 | n=1.000.000 |
|---|---|---|---|---|---|---|
| O(1) | Constante | Acceder a datos[i] | 1 | 1 | 1 | 1 |
| O(log n) | Logarítmica | Búsqueda binaria | ~3 | ~7 | ~10 | ~20 |
| O(n) | Lineal | Búsqueda lineal | 10 | 100 | 1.000 | 1.000.000 |
| O(n log n) | Lineal-logarítmica | Merge sort | ~33 | ~664 | ~10.000 | ~20.000.000 |
| O(n²) | Cuadrática | Burbuja, selección | 100 | 10.000 | 1.000.000 | 1012 |
| O(2n) | Exponencial | Subconjuntos por fuerza bruta | 1.024 | ~1030 | — | — |
Apliquemos la notación O grande al algoritmo de búsqueda lineal:
datos[i] != clave. Es la operación que se repite en cada iteración del bucle y la que determina el crecimiento del tiempo de ejecución.
Cuando decimos que la búsqueda lineal es «O(n)» sin más especificación, nos referimos al peor caso.
La búsqueda binaria requiere una precondición que la búsqueda lineal no necesita: la secuencia debe estar ordenada. Esta precondición es un contrato —si no se cumple, el algoritmo no garantiza un resultado correcto—.
La búsqueda binaria sobre una secuencia desordenada puede dar resultados incorrectos: puede reportar que un elemento no está cuando sí está, o buscar en la mitad equivocada. Antes de usar búsqueda binaria, el programador debe garantizar que la secuencia está ordenada (o bien ordenarla previamente, lo cual tiene su propio costo).
La búsqueda binaria aprovecha el orden para descartar la mitad de los elementos en cada paso. La idea es análoga a buscar una palabra en un diccionario de papel: no se recorre página por página, sino que se abre por la mitad, se compara y se descarta la mitad que no puede contener la palabra.
Para datos = [5, 8, 15, 27, 36, 42, 63, 91] y clave = 42:
| Paso | izq | der | medio | datos[medio] | Comparación | Acción |
|---|---|---|---|---|---|---|
| 1 | 0 | 7 | 3 | 27 | 42 > 27 | izq ← 4 |
| 2 | 4 | 7 | 5 | 42 | 42 == 42 | Retorna 5 ✓ |
Solo 2 comparaciones. La búsqueda lineal habría necesitado 6 (recorrer las posiciones 0 a 5).
Un error frecuente al trazar la búsqueda binaria es confundir la posición visual de un elemento con su índice real. Por ejemplo, en la secuencia de 8 elementos anterior, el valor 42 está en la posición 5 (contando desde 0), no en la 6. Si al calcular medio = (4+7)//2 = 5 hubiéramos anotado erróneamente que datos[5] = 63, la traza habría continuado descartando la mitad equivocada y habría «concluido» que el 42 no está —un resultado incorrecto provocado no por un fallo del algoritmo, sino por un error humano en la traza—. La lección: siempre verificar cada valor consultando la secuencia concreta.
Tracemos la búsqueda de clave = 40 (ausente) en la misma secuencia:
| Paso | izq | der | medio | datos[medio] | Comparación | Acción |
|---|---|---|---|---|---|---|
| 1 | 0 | 7 | 3 | 27 | 40 > 27 | izq ← 4 |
| 2 | 4 | 7 | 5 | 42 | 40 < 42 | der ← 4 |
| 3 | 4 | 4 | 4 | 36 | 40 > 36 | izq ← 5 |
| 4 | 5 | 4 | — | — | izq > der | Retorna −1 |
3 comparaciones con elementos de la secuencia para determinar que 40 no está presente. La búsqueda lineal habría necesitado 8 (recorrer toda la secuencia).
En cada paso, la búsqueda binaria descarta la mitad de los elementos restantes. ¿Cuántas veces podemos dividir n por 2 antes de llegar a 1?
Partimos de n elementos. Tras 1 paso: n/2. Tras 2 pasos: n/4. Tras k pasos: n/2k. La búsqueda termina cuando n/2k ≤ 1, es decir, cuando 2k ≥ n, o sea, k ≥ log2(n).
Por lo tanto, la búsqueda binaria realiza a lo sumo ⌈log2(n)⌉ + 1 comparaciones. Esto es O(log n).
| Tipo | Entrada | Resultado | Justificación |
|---|---|---|---|
| Normal | datos=[2,5,8,12,16,23,38,56,72,91], clave=23 | 5 | Elemento interior |
| Normal | datos=[2,5,8,12,16,23,38,56,72,91], clave=50 | -1 | Ausente, entre elementos |
| Límite | datos=[2,5,8,12,16,23,38,56,72,91], clave=2 | 0 | Primer elemento |
| Límite | datos=[2,5,8,12,16,23,38,56,72,91], clave=91 | 9 | Último elemento |
| Límite | datos=[2,5,8,12,16,23,38,56,72,91], clave=1 | -1 | Menor que todos |
| Límite | datos=[2,5,8,12,16,23,38,56,72,91], clave=100 | -1 | Mayor que todos |
| Extremo | datos=[], clave=5 | -1 | Secuencia vacía |
| Extremo | datos=[42], clave=42 | 0 | Un elemento, encontrado |
La búsqueda binaria siempre examina el elemento central de la región, pero ¿es siempre la mejor elección? Cuando buscamos en una guía telefónica un apellido que empieza con «Z», no abrimos por la mitad: abrimos cerca del final. Estamos estimando la posición del elemento a partir de su valor y de los valores en los extremos de la región. Esta idea da origen a la búsqueda por interpolación.
En lugar de calcular el punto medio como (izq + der) // 2, la búsqueda por interpolación estima la posición más probable de la clave usando una interpolación lineal entre los valores de los extremos:
pos = izq + ⌊(clave − datos[izq]) × (der − izq) / (datos[der] − datos[izq])⌋
La intuición: si datos[izq] = 10, datos[der] = 100 y clave = 25, la clave está a ~17% del rango de valores, así que estimamos su posición a ~17% del rango de índices.
Para datos = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100] (distribución uniforme) y clave = 70:
| Paso | izq | der | Cálculo de pos | pos | datos[pos] | Acción |
|---|---|---|---|---|---|---|
| 1 | 0 | 9 | 0 + (70−10)×9/(100−10) = 6 | 6 | 70 | Retorna 6 ✓ |
Una sola comparación. La interpolación estimó exactamente la posición porque los datos están uniformemente distribuidos. La búsqueda binaria habría necesitado 2–3 comparaciones.
La eficiencia de la búsqueda por interpolación depende críticamente de la distribución de los valores:
| Distribución | Interpolación | Binaria | Recomendación |
|---|---|---|---|
| Uniforme Valores equiespaciados o casi |
O(log log n) | O(log n) | Interpolación |
| Aproximadamente uniforme DNIs, timestamps, IPs |
~O(log log n) | O(log n) | Interpolación |
| Sesgada / exponencial Valores concentrados en un extremo |
O(n) | O(log n) | Binaria |
| Desconocida | Impredecible | O(log n) garantizado | Binaria (más segura) |
Cuando la distribución es uniforme, la estimación por interpolación acota la región a √(der − izq) elementos en cada paso, en lugar de la mitad. Resolver la recurrencia resultante produce O(log log n). Para n = 1.000.000: log2(n) ≈ 20, pero log2(log2(n)) ≈ 4. La diferencia es significativa para grandes volúmenes de datos con distribución conocida.
Si los datos tienen distribución muy sesgada (por ejemplo, [1, 2, 3, 4, 5, 1000000]), la fórmula de interpolación puede estimar posiciones muy alejadas del valor real, generando una degradación a O(n) —peor que la búsqueda binaria—. La regla práctica es: usar interpolación solo cuando se tiene certeza razonable de que la distribución es aproximadamente uniforme. En caso de duda, la búsqueda binaria es la opción segura porque su peor caso O(log n) está garantizado sin importar la distribución.
La búsqueda por interpolación tiene otra ventaja práctica cuando los datos residen en disco: cada acceso a disco es costosísimo (~5–20 ms), así que reducir la cantidad de accesos de ~20 (binaria) a ~4 (interpolación) produce una aceleración medible. Esto explica su uso histórico en sistemas de bases de datos que operan sobre archivos indexados con claves numéricas distribuidas uniformemente.
En la Semana 4, al estudiar la pila de ejecución, observamos que cada invocación de función apila un nuevo frame con sus variables locales y su dirección de retorno. La búsqueda binaria tiene una estructura que se presta naturalmente a una formulación recursiva: el caso en que la clave está en el medio es el caso base (se retorna inmediatamente), y los casos en que se descarta una mitad son llamadas recursivas sobre una región más pequeña.
Cada llamada recursiva reduce el tamaño de la región (der − izq) a la mitad. Eventualmente, la región queda vacía (izq > der) o se encuentra la clave: estos son los casos base que detienen la recursión. Observe que en la pila de ejecución se apilarán a lo sumo ⌈log2(n)⌉ frames —uno por cada paso de la búsqueda—, un uso de memoria muy modesto.
La recursividad como técnica general de resolución de problemas se estudiará en detalle en la Semana 8, donde analizaremos su estructura (caso base, caso recursivo), su correctitud (convergencia al caso base), su relación con la pila de ejecución y su comparación sistemática con la iteración.
Las versiones iterativa y recursiva de la búsqueda binaria tienen la misma complejidad temporal O(log n). La iterativa usa O(1) de memoria adicional; la recursiva usa O(log n) por los frames apilados. En Python, la versión iterativa es generalmente preferible porque Python tiene un límite de profundidad de recursión (por defecto 1000, consultable con sys.getrecursionlimit()). Para n = 21000 la recursiva fallaría —pero eso son más elementos que partículas en el universo observable, así que en la práctica no es una limitación real para la búsqueda binaria.
| Aspecto | Búsqueda Lineal | Búsqueda Binaria | Búsqueda por Interpolación |
|---|---|---|---|
| Precondición | Ninguna | Secuencia ordenada | Secuencia ordenada + valores numéricos |
| Estrategia | Recorrido secuencial | Dividir por la mitad | Estimar posición por interpolación lineal |
| Peor caso | O(n) | O(log n) | O(n) si distribución sesgada |
| Caso promedio | O(n) | O(log n) | O(log log n) si distribución uniforme |
| Mejor caso | O(1) | O(1) | O(1) |
| n = 1.000.000 | Hasta 1.000.000 | Hasta 20 | ~4 (uniforme) o hasta 1.000.000 (sesgada) |
| ¿Cuándo usar? | Secuencias pequeñas o desordenadas | Secuencias ordenadas; elección segura universal | Secuencias ordenadas con distribución conocida y aproximadamente uniforme |
Ordenar una secuencia de n elementos cuesta O(n log n) (con un buen algoritmo, como merge sort, que estudiaremos en la Semana 6). Si solo vamos a buscar una vez, la búsqueda lineal O(n) es más barata que ordenar O(n log n) + buscar O(log n). Pero si vamos a buscar muchas veces (m búsquedas), el costo total es:
La segunda opción conviene cuando m es suficientemente grande. Por ejemplo, para n = 10.000 y m = 100 búsquedas: lineal ≈ 100 × 10.000 = 1.000.000 operaciones; binaria ≈ 133.000 + 100 × 14 = 134.400 operaciones. Con solo 100 búsquedas, la opción binaria ya es 7 veces más rápida.
La búsqueda binaria es un algoritmo notoriamente difícil de implementar correctamente. Donald Knuth observó que, a pesar de que la idea es simple, la primera implementación publicada (en 1946) contenía errores, y que pasaron 16 años hasta que se publicó una versión totalmente correcta. ¿Cómo verificar que nuestra implementación es correcta?
La clave para demostrar la correctitud es el invariante del bucle: una propiedad que es verdadera al comenzar cada iteración y que, al terminar el bucle, garantiza que el resultado es correcto.
Para la búsqueda binaria, el invariante es:
Invariante: si la clave está en datos, entonces está en datos[izq..der] (la sub-secuencia entre los índices izq y der, ambos incluidos).
Inicialización: antes de la primera iteración, izq = 0 y der = n-1, que abarca toda la secuencia ⇒ el invariante es trivialmente verdadero.
Mantenimiento: si datos[medio] < clave, todos los elementos en posiciones izq..medio son menores que clave (por el orden). Ajustar izq = medio + 1 preserva el invariante. El caso simétrico con der = medio - 1 es análogo.
Terminación: cuando izq > der, la región está vacía. Si la clave existiera, estaría en una región vacía —contradicción—. Retornar −1 es correcto.
1. Desbordamiento del cálculo del medio: la fórmula (izq + der) // 2 puede desbordar en lenguajes con enteros de tamaño fijo (C, Java) si izq + der excede el máximo. La alternativa segura es izq + (der - izq) // 2. En Python los enteros no tienen límite de tamaño, pero es un buen hábito.
2. Condición del bucle: usar izq < der en lugar de izq <= der provoca que no se examine el caso en que la región tiene exactamente un elemento (izq == der).
3. Actualización de límites: hacer izq = medio en lugar de izq = medio + 1 puede causar un bucle infinito cuando izq == medio (región de 2 elementos).
Los algoritmos de búsqueda no operan en abstracto: se ejecutan sobre datos almacenados en la memoria de la computadora. Pero «la memoria» no es un componente homogéneo —es una jerarquía de dispositivos con capacidades y velocidades radicalmente diferentes. Comprender esta jerarquía es esencial para entender por qué ciertos algoritmos son rápidos en la práctica (no solo en teoría).
Existe un compromiso fundamental en la tecnología de memorias: velocidad y capacidad son inversamente proporcionales al costo. La memoria más rápida (registros, SRAM) es extremadamente cara y solo se puede fabricar en cantidades pequeñas. La memoria más lenta (disco HDD) es barata y puede almacenar terabytes. La jerarquía es la solución ingenieril a este compromiso: usar poca memoria rápida para los datos que se usan ahora, y mucha memoria lenta para el resto.
La jerarquía funciona gracias a un fenómeno empírico de los programas reales: la localidad de referencia.
i de un bucle se lee y escribe en cada iteración.La búsqueda lineal tiene excelente localidad espacial: accede a posiciones consecutivas del arreglo, lo que aprovecha perfectamente las líneas de caché. La búsqueda binaria, en cambio, salta a posiciones distantes del arreglo en cada paso, lo que puede causar más cache misses. Para arreglos pequeños (decenas de elementos), la búsqueda lineal puede ser más rápida que la binaria en la práctica, a pesar de su peor complejidad asintótica, precisamente por la localidad de caché.
Las heurísticas de Move-to-Front y Transposición explotan la localidad temporal: asumen que un elemento buscado recientemente volverá a buscarse pronto, y lo colocan donde se encontrará más rápido.
La caché es una memoria pequeña y rápida (SRAM) ubicada dentro del procesador. Cuando la CPU necesita un dato, sigue este proceso:
Si un acceso a caché L1 fuera equivalente a buscar un libro en tu escritorio (2 segundos), entonces: caché L2 sería buscar en la estantería de tu cuarto (7 segundos), RAM sería ir a la biblioteca del edificio (3 minutos), SSD sería ir a una biblioteca pública (1 hora), y HDD sería pedir un libro por correo postal (2 semanas). Esta analogía ilustra por qué un cache miss es tan costoso en términos relativos.
En el extremo inferior de la jerarquía de memoria se encuentran los dispositivos de almacenamiento persistente (SSD, HDD). El sistema operativo gestiona el acceso a estos dispositivos a través del sistema de archivos, una abstracción que ya introdujimos en el documento «Funciones del Sistema Operativo». Aquí profundizamos en los conceptos más relevantes para un programador.
El sistema de archivos organiza la información en una estructura jerárquica de árbol. Cada archivo se identifica por su ruta (path), que puede ser absoluta (desde la raíz) o relativa (desde el directorio actual).
| Concepto | Linux / macOS | Windows |
|---|---|---|
| Raíz | / |
C:\ (una raíz por unidad) |
| Separador | / (barra) |
\ (contrabarra) |
| Ruta absoluta | /home/alumno/tp1.py |
C:\Users\alumno\tp1.py |
| Ruta relativa | ./datos/entrada.txt |
.\datos\entrada.txt |
| Directorio actual | . |
. |
| Directorio padre | .. |
.. |
En sistemas Unix/Linux, cada archivo tiene tres conjuntos de permisos: para el propietario, el grupo y otros. Cada conjunto define tres permisos: lectura (r), escritura (w) y ejecución (x).
La cadena de 10 caracteres al inicio se descompone en cuatro secciones, cada una con un significado específico:
El conjunto de permisos rwxr-xr-- se representa numéricamente como 754 en octal. Cada grupo de tres permisos es un número octal: r=4, w=2, x=1; los valores se suman dentro de cada grupo.
En Python, os.chmod('tp1.py', 0o754) establece estos permisos. El prefijo 0o indica notación octal. La representación octal conecta directamente con la representación binaria estudiada en la Semana 2: cada dígito octal corresponde exactamente a 3 bits. Así, el permiso rwx (7 en octal) equivale a 111 en binario, y r-- (4 en octal) equivale a 100 en binario. Esta correspondencia no es casual: el sistema de permisos Unix fue diseñado para aprovechar la relación entre octal y binario.
Todo acceso a archivos se realiza mediante llamadas al sistema (syscalls), que son solicitudes que el programa hace al kernel del SO. El documento «Sistema Operativo: Funciones y Administración de Archivos» detalla estas operaciones; aquí destacamos las más relevantes para entender cómo un programa interactúa con datos persistentes.
| Operación | Syscall | ¿Qué hace el SO? | Equivalente en Python |
|---|---|---|---|
| Abrir | open(path, flags) |
Resuelve la ruta recorriendo los directorios, verifica permisos y crea una entrada en la tabla de archivos abiertos del proceso. Retorna un descriptor de archivo (fd). | f = open('datos.txt', 'r') |
| Leer | read(fd, buf, n) |
Busca los bloques en el buffer cache; si no están, los trae del disco. Actualiza la posición actual de lectura. | contenido = f.read() |
| Escribir | write(fd, buf, n) |
Escribe en el buffer cache (puede ser asíncrono con el disco). Actualiza el inodo con el nuevo tamaño. | f.write('datos') |
| Cerrar | close(fd) |
Libera la entrada en la tabla de archivos. Si era la última referencia, hace flush de buffers pendientes. | f.close() |
Cuando un programa abre un archivo, el SO le asigna un descriptor de archivo: un entero pequeño que identifica esa conexión abierta. Por convención, todo proceso comienza con tres descriptores ya abiertos: 0 (entrada estándar — teclado), 1 (salida estándar — pantalla) y 2 (salida de error). Los archivos que el programa abre explícitamente reciben los números 3, 4, etc. En Python, el with gestiona automáticamente la apertura y el cierre, pero detrás de escena opera sobre estos descriptores.
El SO mantiene en RAM una caché de bloques de disco (buffer cache o page cache) que actúa como memoria intermedia entre los programas y el almacenamiento físico. Esta caché es fundamental para el rendimiento:
La caché de buffer aplica el mismo principio de localidad que la caché del procesador, pero a escala de disco. Si un programa realiza búsquedas repetidas sobre un archivo de datos, la primera lectura trae los bloques del disco a la caché en RAM; las búsquedas siguientes los encuentran en RAM, evitando accesos a disco. Esto es especialmente relevante para la búsqueda binaria sobre archivos: aunque el algoritmo accede a posiciones dispersas, la cantidad total de bloques que necesita es O(log n) —un conjunto pequeño que la caché puede retener completamente—.
La lectura y escritura de archivos en Python se desarrollará en profundidad en la Semana 6 (junto con los algoritmos de ordenamiento). Aquí anticipamos la idea central: Python abstrae las operaciones de E/S del sistema operativo mediante el context manager with, que garantiza el cierre correcto del archivo incluso si ocurre un error.
with open(...)?La sentencia with invoca open(), que a su vez ejecuta la syscall del SO para abrir el archivo. El SO resuelve la ruta (recorriendo el árbol de directorios), consulta el inodo del archivo (una estructura de datos del sistema de archivos que contiene los metadatos: tamaño, permisos, punteros a los bloques de datos), verifica los permisos del usuario y, si todo es correcto, crea el descriptor de archivo. Al salir del bloque with —incluso si ocurre una excepción— se ejecuta automáticamente close(), liberando el descriptor y sincronizando los buffers. Para más detalles sobre inodos, descriptores y el ciclo completo de vida de un archivo, consultar la sección 6 del documento «Sistema Operativo: Funciones y Administración de Archivos».
Cuando nuestro programa de búsqueda binaria accede a datos[medio], ocurre una cadena de eventos invisible:
Cada salto a un nivel inferior de la jerarquía multiplica el tiempo de acceso. Por esto, los algoritmos que acceden a posiciones contiguas de memoria (localidad espacial) son favorecidos por el hardware.
Aplicando el modelo de programa de las semanas anteriores, un programa completo que utiliza búsqueda tiene la siguiente estructura:
Nótese que el programa principal invoca busqueda_binaria(datos, clave) sin preocuparse por los detalles internos del algoritmo. Si más adelante descubrimos un algoritmo aún mejor, basta con reemplazar la función —el resto del programa no cambia—. Esto es la abstracción funcional en acción (Semana 4).
Esta semana hemos formalizado los algoritmos de búsqueda y la herramienta teórica para medir su eficiencia. La búsqueda lineal —simple y sin precondiciones— es la opción universal, pero su crecimiento lineal O(n) la hace inviable para grandes volúmenes de datos con búsquedas frecuentes. La búsqueda binaria —dramáticamente más eficiente con O(log n)— exige el precio de mantener los datos ordenados. La búsqueda por interpolación lleva la eficiencia aún más lejos —O(log log n) cuando la distribución es favorable—, pero a cambio requiere presunciones sobre los datos que, si no se cumplen, la degradan hasta O(n). La elección entre estas opciones es un ejemplo paradigmático de decisión de diseño algorítmico: no hay una respuesta universalmente correcta, sino un análisis de compromisos que depende del problema concreto.
Las heurísticas de optimización de la búsqueda lineal (Move-to-Front, Transposición) muestran que incluso un algoritmo simple puede mejorarse cuando se conocen patrones de uso. El anticipo de la versión recursiva de la búsqueda binaria conecta con la pila de ejecución estudiada en la Semana 4 y prepara el terreno para el estudio sistemático de la recursividad. La idea de adaptar el algoritmo al contexto reaparecerá a lo largo de la carrera.
La eficiencia de un algoritmo de búsqueda no se mide solo por la cantidad de comparaciones (modelo teórico), sino también por cómo interactúa con la jerarquía de memoria. La búsqueda lineal recorre posiciones contiguas, aprovechando la localidad espacial y la caché. La búsqueda binaria salta posiciones distantes, generando más cache misses. En el nivel del sistema operativo, cuando los datos residen en disco, cada acceso implica una operación de E/S que es órdenes de magnitud más lenta que un acceso a RAM —y aquí la búsqueda binaria, con sus O(log n) accesos, supera ampliamente a la lineal con O(n) accesos a disco.
El principio de localidad de referencia —que aprovechan la caché, el sistema operativo y las heurísticas de búsqueda— es un ejemplo de cómo una misma idea se manifiesta en todos los niveles de abstracción de un sistema de computación.
Algoritmos de Búsqueda y Complejidad Algorítmica — Semana 5
Desarrollo de Contenidos — Algoritmia y Programación — Carrera de Informática