Nuevo algoritmo de ordenamiento de libros logra un rendimiento casi perfecto
(quantamagazine.org)- El problema del ordenamiento en bibliotecas no solo trata de acomodar estantes: también determina el costo del almacenamiento secuencial en discos duros y bases de datos, y una nueva investigación reduce el tiempo promedio de inserción muy cerca del límite teórico
- Un algoritmo de 1981 garantizaba un tiempo promedio de inserción de ((log n)^2) de forma determinista y suave (smooth), pero durante más de 40 años no apareció una cota superior más baja
- Estudios posteriores de cotas inferiores mostraron que el mejor resultado posible para algoritmos generales es (log n), mientras que el límite para algoritmos suaves y deterministas es ((log n)^2), por lo que se volvió necesario un enfoque aleatorio y no suave
- En 2022, Bender, Kuszmaul y otros redujeron la cota superior a ((log n)^{1.5}) con un algoritmo aleatorio de historial independiente (history independent), y la investigación más reciente alcanza ((log n)(log log n)^3) aprovechando información limitada del pasado
- La diferencia restante está en el término (log log n), y este avance podría acelerar aplicaciones como el almacenamiento y procesamiento de grafos dinámicos basado en etiquetado de listas
Qué plantea el problema del ordenamiento en bibliotecas
- El problema del ordenamiento en bibliotecas consiste en minimizar el tiempo de movimiento necesario al insertar un nuevo elemento mientras se mantiene el orden
- Si todos los libros están amontonados hacia un lado, insertar un libro nuevo en medio obliga a mover muchos libros otra vez
- Al agregar un libro de Isabel Allende, podría ser necesario mover toda la colección
- Después, si se agrega un libro de Douglas Adams, el mismo trabajo puede repetirse
- Si se distribuye espacio vacío de manera adecuada por todo el estante, se puede reducir el costo de inserción, pero la clave está en decidir dónde y cuánto espacio dejar
- De manera más formal, esto se conoce como el problema de etiquetado de listas (list labeling), introducido en un artículo de 1981
- Su alcance va más allá de los estantes: también se aplica a la colocación de archivos y registros en discos duros y bases de datos
- La cantidad de elementos puede llegar a miles de millones
- Una disposición ineficiente puede traducirse en largas esperas y altos costos computacionales
Rendimiento visto desde cotas superiores e inferiores
- El rendimiento de una disposición ordenada suele evaluarse por el tiempo que tarda insertar un solo elemento nuevo
- Si hay (n) elementos y hubiera que mover todos los libros, el tiempo de inserción sería proporcional a (n)
- Eso puede verse como una cota superior del tiempo que podría tomar agregar un elemento nuevo
- El artículo de 1981 preguntó si era posible reducir el tiempo promedio de inserción mucho más allá de (n), y presentó un algoritmo que garantiza ((log n)^2)
- Es un algoritmo determinista que no depende de aleatoriedad
- Tiene la propiedad suave (smooth), según la cual los elementos deben quedar distribuidos uniformemente dentro del intervalo donde ocurren inserciones o eliminaciones
- Los investigadores buscan cerrar la brecha entre cotas superiores e inferiores; cuando ambas coinciden, se considera que el algoritmo es óptimo
Restricciones impuestas por resultados previos de cotas inferiores
- Un estudio de 2004 mostró una cota inferior definitiva: en la versión más general del problema del ordenamiento en bibliotecas, ningún algoritmo puede mejorar (log n)
- En 1990 se confirmó que la cota inferior para algoritmos suaves es ((log n)^2)
- En 2012 apareció un resultado que muestra que los algoritmos deterministas, es decir, sin aleatoriedad, también tienen la misma cota inferior ((log n)^2)
- Estos resultados implican que solo con algoritmos suaves o deterministas es difícil mejorar la cota superior de ((log n)^2) obtenida en 1981
- Michael Bender concluyó que para lograr algo mejor se necesitaban algoritmos aleatorios y no suaves
- Un enfoque no suave parecía intuitivamente arriesgado, porque no mantiene los elementos espaciados de manera uniforme
- Tampoco estaba claro por qué las elecciones aleatorias ayudarían
2022: bajar la cota superior con historial independiente
- En 2022, Bender, William Kuszmaul y otros seis investigadores desarrollaron un algoritmo de historial independiente, no suave y aleatorio
- Un algoritmo de historial independiente no revela estados pasados del estante
- Kuszmaul dio el ejemplo de sacar un libro del estante sin que otra persona pueda darse cuenta de que antes estuvo ahí
- Esa propiedad puede aprovecharse por motivos de privacidad o seguridad
- Este algoritmo redujo por primera vez la cota superior de 1981 y bajó el tiempo promedio de inserción a ((log n)^{1.5})
- A Kuszmaul le sorprendió que una herramienta normalmente usada para privacidad pudiera hacer más rápido un algoritmo
- Helen Xu, del Georgia Institute of Technology, consideró que la idea de usar historial independiente por motivos distintos a la seguridad podría influir en otros problemas
Investigación más reciente: combinación de información limitada del pasado y aleatoriedad
- En su artículo más reciente, Bender, Kuszmaul y sus coautores volvieron a reducir la cota superior y lograron ((log n)(log log n)^3)
- Ese valor equivale a ((log n)^{1.000…1}), muy cerca de la cota inferior definitiva (log n)
- El nuevo enfoque también es no suave y aleatorio, pero esta vez usa una forma limitada de dependencia del historial (history dependence)
- El algoritmo observa parcialmente las tendencias pasadas para prepararse para inserciones futuras
- Si entraron muchos libros de autores cuyos apellidos empiezan con N, como Nabokov, Neruda o Ng, deja un poco más de espacio libre en la zona de la N
- Pero si reserva demasiado espacio, puede causar problemas cuando luego entren muchos libros de autores con apellido que empieza con A
- Bender explicó que volvió útil este enfoque al aleatorizar estratégicamente cuánta parte del pasado observar al tomar decisiones
- Seth Pettie señaló que este trabajo usa la aleatoriedad de una manera completamente distinta a la del artículo de 2022
La brecha restante y sus posibles aplicaciones
- La brecha restante es el pequeño término (log log n)
- Bender dijo que todavía no se sabe si hay que bajar más la cota superior o subir la cota inferior
- Pettie opinó que cuando la brecha es tan estrecha y una frontera parece natural mientras la otra luce artificial, normalmente la natural termina siendo la correcta
- Evaluó que futuras mejoras probablemente irán en la dirección de reducir la cota superior hasta (log n)
- Aun así, añadió que “el mundo está lleno de sorpresas extrañas”
- Brian Wheatman, de la University of Chicago, considera que estos artículos representan una mejora considerable en teoría, con posibilidades de grandes mejoras también en aplicaciones
- Helen Xu comentó que recientemente le interesaba usar estructuras de datos basadas en etiquetado de listas para almacenar y procesar grafos dinámicos, y cree que este avance casi con certeza los hará más rápidos
1 comentarios
Opiniones de Hacker News
A mí también me sorprendió que “una herramienta usada para proteger la privacidad pueda aportar otros beneficios”
Si uno lo piensa bien, gran parte del rendimiento no es literalmente una cuestión de “ejecutar más instrucciones por hora”, sino más bien de elegir una forma de hacer menos trabajo
Aquí, la propiedad de seguridad de independencia del historial también significa que “no hace falta hacer el trabajo de rastrear el historial y, literalmente, tampoco se puede”, así que se siente como un enfoque de rendimiento interesante: usar la criptografía como restricción para impedir trabajo innecesario
Según entiendo, es un modelo en el que se puede gastar tiempo de cómputo infinito
Por ejemplo, si sabes que una lista está ordenada, puedes usar búsqueda binaria. Pero quizá elegir cuánta información omitir también pueda ser clave. Eso sí, estos casos se ven con menos frecuencia y no se me ocurre enseguida un ejemplo simple
Me pregunto si soy el único que intentó encontrar los artículos principales que explica la nota, es decir, el paper del problema original y el del algoritmo casi óptimo [1], [2]
Ambos parecen estar enlazados muy adentro del artículo, pero creo que sería muy útil para los lectores que Quanta reuniera obligatoriamente todas las referencias al final de sus notas
[1] Nearly Optimal List Labeling:
https://arxiv.org/abs/2405.00807
[2] A sparse table implementation of priority queues:
https://link.springer.com/chapter/10.1007/3-540-10843-2_34
En “This problem was introduced in a 1981 paper”, “1981 paper” enlaza a https://link.springer.com/chapter/10.1007/3-540-10843-2_34, y en el párrafo siguiente, en “Last year, in a study that was presented at the Foundations of Computer Science conference in Chicago, a team of seven researchers”, “a study” enlaza a https://arxiv.org/abs/2405.00807
Ambos están en el tercer y cuarto párrafo de la introducción, antes de entrar en los detalles, la historia y el contexto. Si a eso se le llama “muy adentro del artículo”, entonces el criterio de muy adentro debe variar bastante
La semana pasada estaba viendo justamente este problema. Quería poner elementos de una tabla de base de datos en posiciones arbitrarias, pero, de ser posible, sin tocar el resto de la lista
Por ejemplo, si el usuario agrega un nuevo elemento después del elemento 5, ese nuevo elemento pasa a ser el 6, pero no se actualiza el elemento que ya estaba después del 5. En la práctica existen algoritmos muy sofisticados para gestionar este problema y minimizar sus límites teóricos
Sin embargo, para esta versión específica, usar índices fraccionarios y pagar de vez en cuando el costo de reubicar la lista parecía la solución más simple
Básicamente funciona bien si el espacio de etiquetas es grande en comparación con la cantidad de elementos. Cuando no lo es, hacen falta métodos más sofisticados. Por ejemplo, sería un problema si solo tienes 4 bytes para las etiquetas y 1.000 millones de elementos
Según recuerdo, la solución práctica era dejar espacios entre los elementos. Por ejemplo, usar 0, 100, 200 en vez de 0, 1, 2, y reindexar cuando haga falta. Parece que funcionaría bastante bien
Lo que se me ocurrió fue, como mencionas, indexación fraccionaria, pero como manejar decimales es molesto, se puede representar como un vector y expresarlo como una cadena numérica que se ordena lexicográficamente
Un elemento insertado entre 1 y 2 tendría índice 11. Puede ser cualquier cosa entre 11 y 19. Entre 1 y 11 sería 101; entre 11 y 2 sería 12, y así. Pero estos índices no son números, sino cadenas comparadas lexicográficamente
Seguramente también tiene desventajas. Por ejemplo, ordenar estos índices usaría mucha más memoria, porque las cadenas son mucho más grandes que los números. También se siente demasiado ingenioso como para no tener alguna desventaja inesperada
En la práctica, ese límite es muy acotado, pero si en vez de simplemente poner etiquetas de orden a una colección intentas usar esas etiquetas directamente como índices de un arreglo para almacenar los elementos, la diferencia se vuelve un problema real. Ese es el modelo más literal del problema de ordenar una biblioteca
Recuerdo haberles presentado a mis estudiantes hace unos años un problema basado en el algoritmo Library Sort
Todavía recuerdo con claridad el título del paper original: “Insertion Sort is O(n log n)”
El título se siente bastante clickbait
Me pregunto si este algoritmo tiene alguna razón para ser realmente más rápido en la práctica que los métodos que se usan actualmente.
Donde más me he encontrado con este problema es en arreglos de nodos de B-tree, y ahí dudo que sea más rápido que simplemente usar
memmove(); si el arreglo fuera realmente grande, probablemente sería más fácil usar un B-tree.Entonces este algoritmo también entraría en la categoría de los que son asintóticamente más rápidos, pero paradójicamente más lentos que los algoritmos usados en la práctica. Un ejemplo son los algoritmos rápidos de multiplicación de matrices, que son más lentos que una buena implementación del algoritmo clásico O(n^3) (GEMM).
El primer ejemplo de la página incluye una cita que explica bien su utilidad:
“Como ejemplo de galactic algorithm, el método conocido más rápido para multiplicar dos números se basa en una transformada de Fourier de 1729 dimensiones. Solo requiere O(n log n) operaciones de bits, pero la constante oculta en la notación Big O es tan grande que en la práctica no se usa. Aun así, muestra por qué estos algoritmos pueden ser útiles. Los autores dicen que ‘esperan que, con mejoras adicionales, se vuelva práctico incluso con números de miles de millones o billones de dígitos’”.
La afirmación de que
baja la cota superior a (log n) × (log log n)^3 — equivalente a (log n)^(1.000...1)es cierta.Una de las cosas interesantes de ver la complejidad Big O en familias con base polinómica es que los logaritmos dan valores infinitesimales. Es un buen golpe para quienes dicen que “los infinitesimales no existen en realidad”.
Me sorprendió saber cómo la British Library gestiona millones de libros y una enorme cantidad de novedades cada semana.
El primer libro que llegó a principios de este año se colocó en la posición 2025.0000001 del estante, y el siguiente justo al lado, en 2025.0000002. Del resto se encarga el catálogo electrónico.
No hace falta volver a mezclar los libros, pero es una solución que no encaja con la forma de buscar libros recorriendo las estanterías.
Más bien evita deliberadamente la similitud para que el picker no tome un producto parecido pero equivocado.
En casa también suelo olvidar dónde dejé cosas que uso de vez en cuando. Cosas como en qué armario y en qué contenedor puse los repuestos de hojas para el x-acto. Como intento agrupar cosas parecidas, un contenedor termina desbordado y otro queda medio vacío.
A veces imagino que, si llevara el registro de todas mis pertenencias en una hoja de cálculo y anotara en qué contenedor están, no perdería cosas y podría usar el espacio de almacenamiento con la máxima eficiencia. Pero es obvio que olvidaría actualizarlo al guardar algo nuevo, y se siente como una forma extrañamente inhumana de hacerlo, más propia de un robot que de una persona.
La animación al principio del artículo me dio ganas de hacer un protector de pantalla con ella.
Estoy tratando de entender la restricción clave. ¿La definición del problema asume un arreglo preasignado de longitud fija?
insert(X),delete(X),label(X)labeldevuelve la etiqueta del elemento X, que fue insertado previamente y aún no ha sido eliminado. La etiqueta es un número de 0 a n-1, donde n es la cantidad de elementos almacenados actualmente.