El programador políglota
La ciencia de la informática
Descargar el ejemplo de código
.jpg "Ted Neward")
Por muchos años, he oído a mis colegas describirse como "científicos informáticos". También he oído decir que "cualquier campo de estudio que debe poner la palabra "ciencia" en su nombre no es realmente una ciencia. Ciertamente una gran cantidad de personas en mi campo no han tenido estudios formales en la ciencia informática y otro gran porcentaje miran en menos el trabajo que se realiza en las universidades y en las oficinas de profesionales docentes; y tienen algo de razón. ¿Cuándo fue la última vez que un montón de símbolos griegos que pretenden describir un sistema de tipos le ayudó a implementar una aplicación de línea de negocios?
Conozco a varias personas tremendamente inteligentes y una de ellas es Joe Hummel, alguien que con toda legitimidad puede ostentar el título de científico informático, quién incluso posee un doctorado. Le pedí que me ayudara a escribir esta columna para explorar la ciencia informática. Pensé que sería interesante comenzar con algunas de las partes más sencillas de la ciencia informática y luego avanzar hacia cómo comprender que la teoría detrás de esas partes puede, de hecho, facilitar su vida como programador.
En esta entrega, analizamos el clásico debate "Gran O", que busca entregarnos una forma coherente para describir un concepto simple: ¿Cuántos recursos (tiempo, memoria, energía, etc.) necesitará la computadora para ejecutar un programa dado? Esta determinación se conoce como análisis de algoritmo, con el objetivo de colocar el algoritmo elegido en una categoría matemática en especial. ¿Por qué? Para que pueda seleccionar el mejor para cada situación. Existen muchas categorías, donde cada una de las categorías siguientes representa un salto en el consumo de recursos. Nos vamos a enfocar en el tiempo de ejecución y solo en las tres primeras categorías: O(1), O(lgN) y O(N). Como siempre, N denota el número de elementos de datos procesados por el algoritmo. A modo de resumen ejecutivo que explique hacia donde nos dirigimos con todo esto, consulte la Figura 1 que destaca el tiempo de ejecución que se puede esperar para cada categoría a medida que N aumenta.
.png)
Figura 1 Tiempos de ejecución a medida que el número de elementos procesados (N) aumenta
Un algoritmo de orden N se escribe O(N), se pronuncia “Gran O de N” y también se conoce como “lineal”. Dados N elementos de datos, un algoritmo O(N) se encarga del orden de N pasos de tiempo. Un algoritmo de registro de orden N se escribe O(lgN), se pronuncia “Gran O de registro N” y también se conoce como “logarítmico”. Dados N elementos de datos, un algoritmo O(lgN) se encarga del orden de log2(N) pasos de tiempo (muchos menos). Finalmente, un algoritmo de orden 1 se escribe O(1), se pronuncia “Gran O de 1” y también se conoce como “constante”. Para N elementos de datos, un algoritmo O(1) toma un número constante de pasos de tiempo (todavía menos). Tómese un momento para volver a revisar la Figura1. ¿Qué más puede transmitir este gráfico? Por ejemplo, observe que cuando N se dobla, un algoritmo lineal toma el doble de tiempo.
Veamos un ejemplo de cómo esto se aplica a la vida real y observemos que saber apenas un poco de análisis de algoritmos puede hacer una gran diferencia. Supongamos que se le proporciona un archivo de registro para buscar coincidencias en una lista de direcciones IP sospechosas. Bastante simple:
List<string> suspicious = BuildList(); /* step 0 */
foreach (string line in logfile)
{
string ipaddr = parse(line); /* step 1 */
if (suspicious.Contains(ipaddr)) /* step 2 */
matches++; /* step 3 */
}
¿Cómo categorizamos la complejidad de tiempo de este enfoque? Supongamos que existen M líneas en el archivo de registro y N direcciones IP sospechosas. Crear una lista no ordenada de los elementos N (paso 0) incurrirá en un costo de un tiempo de O(N). El bucle realizará M iteraciones, por lo que el costo del bucle es O(M * costo de una iteración). Cada iteración realiza tres pasos básicos:
- Analiza la línea
- Busca en la lista
- Incrementa coincidencias si se encuentra una coincidencia
Comencemos el análisis
El aspecto intelectual del análisis de algoritmos consiste en aprender qué contar y qué no hay que contar. Por ejemplo, mientras que analizar una línea (tal vez al aplicar una expresión normal o al dividir la línea en tokens) puede ser costoso, se requiere de una cantidad constante de tiempo relativo a los datos. En otras palabras, el tiempo requerido para analizar la línea se mantiene sin cambio, mientras que hay M o 2M líneas en el archivo. Tampoco cambia si hay N o 2N direcciones IP sospechosas. De esta forma, decimos que los pasos 1 y 3 toman un tiempo c (constante). Sin embargo, el paso 2, que realiza la búsqueda en la lista, sí cambia de acuerdo con el número de direcciones IP sospechosas.
if (suspicious.Contains(ipaddr))
El método Contains realiza una búsqueda lineal, comenzando con el primer elemento y busca hasta que encuentra una coincidencia o hasta llegar al final de la lista. (¿Cómo podemos saber esto? Existen tres formas: lo probamos, buscamos en el código fuente o la documentación de MSDN Library nos lo dice).
Con datos aleatorios, en promedio se busca en la mitad de la lista, lo que requiere N/2 pasos. Esto se aplica a la mayoría de los casos, pero en este caso en especial, una instrucción más sólida es que la mayoría de las direcciones IP en el archivo de registro son confiables, porque nuestro servidor web no es un banco ni el sitio web de un candidato presidencial. Esto significa que en vez de que exista incluso una posibilidad de que un cliente no sea de confianza, la gran mayoría de las búsquedas completarán la lista sin encontrar una coincidencia, lo que requiere N pasos.
Debido a que las constantes se terminan cuando se calcula el orden de las cosas, la búsqueda es O(N) en cualquier caso, lo que da paso a una complejidad de O(M * N) para el bucle. A su vez, esto da paso a una complejidad algorítmica total de:
= O(build + loop)
= O(N + M * N)
= O( (1 + M) * N )
= O(M * N)
De este modo, la versión 1 de nuestra solución requiere un tiempo de O(MN).
"¡Datos, datos, datos! ¡No puedo fabricar ladrillos sin arcilla!"
La primera pregunta que se debe hacer es: "¿Necesitamos un mejor algoritmo?" Por lo general M es grande, alrededor de los millones (posiblemente miles de millones) de líneas. No hay mucho que pueda hacer al respecto, porque tiene que tocar cada línea para buscarla. Si N, el número de direcciones IP sospechosas, es pequeña (digamos, N < 100), entonces el trabajo está hecho. Con las veloces máquinas actuales, existe muy poca diferencia medible entre pasos de tiempo M y pasos de tiempo 100M. Sin embargo, a medida que N aumenta de tamaño (por ejemplo, N >> 100, o mucho mayor que 100), vale la pena considerar otros algoritmos de búsqueda.
A menos que disponga de un gran presupuesto para hardware, claro está. (Algunas veces, ni siquiera eso alcanza).
Un algoritmo más eficaz es la búsqueda binaria, que salta hasta la mitad y luego busca hacia la izquierda o derecha según si el elemento que está buscando es menor o mayor que el elemento medio. Al cortar el espacio de búsqueda en la mitad cada vez, el algoritmo exhibe el comportamiento O(lgN). ¿Qué significa esto en la práctica? Dados N=1.000 elementos, en el peor de los casos la búsqueda binaria toma el orden de 10 pasos de tiempo (210 ≈ 1.000), mientras que la opción lineal tomaría 1.000. Para N = 1 millón, la diferencia es incluso más drástica; en el orden de 20 pasos de tiempo contra 1 millón. La compensación clave es que la búsqueda binaria requiere que los datos estén en orden. Aquí aparece el programa de búsqueda del archivo de búsqueda vuelto a escribir para usar la búsqueda binaria:
List<string> suspicious = BuildList(); /* step 0 */
suspicious.Sort(); /* step 0.5 */
foreach (string line in logfile)
{
string ipaddr = parse(line); /* step 1 */
if (suspicious.BinarySearch(ipaddr) >= 0) /* step 2 */
matches++; /* step 3 */
}
Organizar la lista sospechosa (paso 0.5) representa un costo de un tiempo de O(NlgN), mientras que el costo por iteración se reduce de O(N) a O(lgN) dada la búsqueda binaria más eficaz (paso 2). Esto da paso a una complejidad algorítmica total de:
= O(build + sort + loop)
= O(N + N * lgN + M * lgN)
= O(N * (1 + lgN) + M * lgN)
= O(N * lgN + M * lgN)
= O((N + M) * lgN)
En nuestro escenario, donde M >> N, la N actúa más como una constante pequeña cuando se agrega a M y así la versión 2 de nuestra solución requiere aproximadamente un tiempo de O(MlgN). ¿Entonces? Para N = 1.000 direcciones IP sospechosas, simplemente reducimos el tiempo de ejecución de un orden de 1.000M pasos de tiempo a 10M, que es 100x más rápido. El tiempo de organización de aproximadamente 10.000 pasos de tiempo (O(NlgN)) se compensa con los ahorros repetidos en el tiempo de búsqueda.
Usemos los hash
Cuando sabe algo sobre los datos que está buscando, puede (y debe) crear una tabla hash. El uso de hash reduce el tiempo promedio de búsqueda a O(1) y eso es lo mejor que se puede alcanzar. Lo realiza al crear una asignación de un valor único a los elementos almacenados en la tabla, donde el valor se produce por la función hash. El requisito clave para el uso de hash es la existencia de una buena función hash que asigne los datos de búsqueda en un intervalo de enteros, con algunas colisiones (asignaciones duplicadas). Nuestro programa de archivo de registro revisado (versión 3) aprovecha la compatibilidad integrada eficaz para el uso de hash en cadenas en Microsoft .NET Framework:
Dictionary<string, int> suspicious = BuildHashTable(); /* step 0 */
foreach (string line in logfile)
{
string ipaddr = parse(line); /* step 1 */
if (suspicious.ContainsKey(ipaddr)) /* step 2 */
matches++; /* step 3 */
}
Crear la tabla hash (paso 0) incurre en un costo por adelantado de un tiempo de O(N). Esto da paso a una complejidad algorítmica total de:
= O(build + loop)
= O(N + M * 1)
= O(N + M)
Si suponemos nuestro escenario de M >> N, las versión 3 es nuestra solución más rápida, con un tiempo aproximado de O(M). Para N = 1.000 direcciones IP sospechosas, simplemente reducimos el tiempo de ejecución por otro factor de 10, que es 1.000x más rápido que nuestra versión original. Y lo más destacable sobre este enfoque es que para incluso valores mayores que N (por ejemplo, 10.000 o incluso 100.000) el tiempo de ejecución es el mismo, en el orden de M pasos de tiempo.
Entonces, ¿dónde está el truco? Con la versión 2 y la búsqueda binaria, es simple: Primero se debe ordenar la lista de direcciones IP. En esta versión con el uso de hash, existen tres problemas que hay que considerar: crear una función de hash eficaz, el costo de construcción por adelantado y un gran consumo de memoria. La clave es la función hash. Una función hash eficaz distribuye los datos a lo largo de la tabla con una cantidad mínima de colisiones, lo que elimina la necesidad de búsquedas adicionales después del uso inicial de hash en la tabla. Tal función ofrece un costo de construcción por adelantado de O(1) por dato, o O(N), lo mismo que en la búsqueda lineal. Sin embargo, tal eficacia por lo general involucra un factor de carga cercano al 10%, lo que significa que los datos ocupan solo 10% de la tabla. Así que el uso de has requiere un consumo de memoria 10x mayor que las búsquedas lineales y binarias, aunque sigue siendo formalmente O(N) al igual que el resto.
¿Por qué estábamos haciendo esto?
Después de toda esa seudomatemática, es posible que un científico titulado en un área no relacionada con la informática note que realizamos bastante manipulación teórica y si bien creemos que encontramos una solución eficaz, dejamos de lado bastantes constantes en el camino. Y esto nos lleva a la pregunta del millón de dólares: "¿Nuestro análisis teórico realmente funciona en la práctica?" Es una pregunta justa, especialmente cuando consideramos el objetivo final de este artículo, que consisten en animarlo a usar el análisis de algoritmos (si todavía no los usa) para evaluar enfoques interesantes antes de comprometerse con el código.
Muchas veces me he sentado a observar a ingenieros que debaten por horas, incluso días, sobre si el enfoque A es mejor que el enfoque B. Es muy poco común ver que tomen una servilleta y realicen un rápido análisis algorítmico.
Por lo tanto, ahora que realizamos el análisis, llevemos a cabo algunas pruebas y veamos qué sucede en la práctica. Para hacer eso, generamos archivos aleatorios de registro con M entradas y luego buscamos estos archivos en listas generadas aleatoriamente de N direcciones IP. (La fuente completa y los archivos de entrada están disponibles en bit.ly/srchlogfiles.)
Para recapitular, si suponemos que M >> N, derivamos las complejidades algorítmicas que aparecen en la Figura 2.
Figura 2 Complejidades algorítmicas si suponemos queM >> N
| Tiempo (t) | |
| Versión 1: Con búsqueda lineal | O(M * N) |
| Versión 2: Con búsqueda binaria | O(M * lgN) |
| Versión 3: Con el uso de hash | O(M) |
Para nuestras pruebas, configuramos M en 1 millón y doble N para cada prueba: 128, 256, 512 y así sucesivamente. El duplicado de N destaca las características de rendimiento de los algoritmos de búsqueda. Si nuestro análisis es preciso, cada vez que N se dobla, el tiempo de ejecución debiera cambiar, como aparece en la Figura 3.
Figura 3 Cambio predicho en el tiempo de ejecución cuandoNse duplica
| Tiempo para 2N | |
| Versión 1 | O(M * 2 * N) => 2 * O(M * N) => 2t |
| Versión 2 | O(M * lg(2N)) => O(M * (lg2 + lgN)) => O(M * (1 + lgN) => O(M + M * lgN) => M + O(M * lgN) => M + t |
| Versión 3 | O(M) => t |
En otras palabras, la versión 1 debe doblar en tiempo (2t), la versión 2 debe tomar otro M pasos de tiempo (t+M) y la versión 3 no debe tomar tiempo adicional (t). La Figura 4 muestra los tiempos reales registrados (en segundos).
Figura 4 Tiempos de ejecución reales (en segundos)
| M | N | Versión 1 | Versión 2 | Versión 3 |
| 1,000,000 | 128 | 3.81 | 2.88 | 2.15 |
| 256 | 5.65 | 2.98 | 2.15 | |
| 512 | 9.39 | 3.11 | 2.17 | |
| 1,024 | 16.78 | 3.23 | 2.19 | |
| 2,048 | 31.52 | 3.36 | 2.19 | |
| 4,096 | 61.18 | 3.49 | 2.28 | |
| 8,192 | 120.63 | 3.68 | 2.39 | |
| 16,384 | 238.86 | 3.95 | 2.54 | |
| 32,768 | 473.91 | 4.34 | 2.89 |
Como puede ver en la Figura 4, la versión 1 (basada en la búsqueda lineal) realmente se duplica en tiempo cuando N se duplica. Eso es probablemente algo malo en la mayoría de los casos.
La versión 2 (basada en la búsqueda binaria) ejecuta órdenes de magnitud más rápido que la versión 1 y crece mucho más lentamente. La tasa de crecimiento es más difícil de cuantificar porque depende del tiempo TM para ejecutar M operaciones, que aparenta estar entre 0,1 y 0,3 segundos. De acuerdo con nuestro análisis, la versión 2 debería crecer a una tasa constante de TM a medida que N se duplica, pero este no parece ser el caso; esto puede ser el resultado de una presión de caché aumentada (y, por lo tanto, no coincidencias de caché) a medida que N crece.
Finalmente, la Figura 4 confirma que la versión 3 es efectivamente el algoritmo más rápido, con prácticamente el mismo tiempo de ejecución, sin importar N (aunque, nuevamente, no es realmente una constante).
Buscar el equilibrio
Desde una perspectiva pragmática, no está claro que la mejora desde la versión 2 a la versión 3 valga más que una cantidad trivial de esfuerzo, a pesar del ahorro en más de un segundo. El ahorro potencia realmente no va a hacer una gran diferencia, a menos que comencemos a ver valores realmente grandes de M o N (sin dejar de considerar que el uso de hash puede requerir 10x más memoria para almacenar las direcciones IP). Y esto nos lleva al último punto: saber cuándo hay que dejar de buscar la optimización. Puede resultar emocionante y atrayente para un programador el encontrar el algoritmo completamente más rápido en realizar algún tipo de operación, pero a menos que esa operación esté de forma explícita frente al usuario, el tiempo usado para intentar optimizar ese último segundo se puede usar mucho mejor para trabajar en alguna otra cosa. Claramente el salto desde la versión 1 a la versión 2 vale la pena el tiempo (corresponde a un ahorro de un 10.000%), pero al igual que todas las cosas, el programador debe buscar el equilibrio. Algunas veces la teoría debe darle paso a la práctica, pero otras veces, la teoría nos ayuda a determinar dónde debemos poner nuestros esfuerzos en la práctica.
¡Feliz codificación!
Ted Neward es asesor arquitectónico en Neudesic LLC. Ha escrito más de 100 artículos y ha sido autor y coautor de docenas de libros, incluido el próximo “Professional F# 2.0” (Wrox, 2010). Es un MVP de C# y orador en conferencias alrededor del mundo. Regularmente asesora y asiste como mentor. Puede comunicarse con él en ted@tedneward.com o Ted.Neward@neudesic.com si le interesa que trabaje con su equipo o leer su blog en http://blogs.tedneward.com.
Joe Hummel es un consultor privado, miembro del personal técnico en Pluralsight LLC, instructor para MVP-Training.net e investigador invitado en el Departamento de ciencias informáticas de la Universidad de California, Irvine. Tiene un doctorado de UC Irvine en el campo de informática de alto rendimiento y se interesa en todo lo que se le relacione. Vive en el área de Chicago y cuando no está navegando, puede ponerse en contacto con él en joe@joehummel.net.