Introducción
- Un nuevo algoritmo propone una forma de resolver el problema de ordenamiento en bibliotecas.
- Este problema no solo se aplica a ordenar libros, sino también a la disposición de archivos en discos duros y bases de datos.
- El nuevo enfoque combina el contenido histórico del estante y la aleatoriedad para producir resultados cercanos al ideal teórico.
Reduciendo los límites
- Una forma común de medir qué tan bien está ordenado un estante es observar el tiempo que toma insertar elementos individuales.
- Un artículo de 1981 planteó la pregunta de si era posible diseñar un algoritmo cuyo tiempo promedio de inserción fuera mucho menor que n.
- Una investigación de 2004 encontró que el límite inferior óptimo para el problema de ordenamiento en bibliotecas es log n.
- También mostró que con algoritmos suaves o deterministas no se puede lograr un tiempo promedio de inserción mejor que (log n)².
La historia secreta
- En 2022, Bender y sus colegas probaron un algoritmo aleatorio y no suave, reduciendo el tiempo promedio de inserción a (log n)¹.⁵.
- Este algoritmo no depende del historial previo del estante, lo que puede ser útil por razones de seguridad.
Cerrando la brecha
- Bender y Kuszmaul redujeron la cota superior a (log n) × (log log n)³, acercándose mucho al límite inferior teórico.
- Este algoritmo usa un grado limitado de dependencia del historial para planificar eventos futuros.
- Este resultado se basa en investigaciones anteriores y utiliza la aleatoriedad de una forma completamente distinta.
Conclusión
- Esta investigación representa una mejora importante desde el punto de vista teórico y también tiene potencial para grandes mejoras en aplicaciones prácticas.
- Aún queda el término log log n como obstáculo para una solución completa, y la respuesta podría estar en bajar la cota superior o subir la cota inferior.
1 comentarios
Comentarios de Hacker News
Es interesante que se pueda usar la criptografía para mejorar el rendimiento. El rendimiento no se trata simplemente de ejecutar más instrucciones, sino de elegir cómo hacer menos trabajo. La propiedad de seguridad llamada "independencia del historial" implica no realizar trabajo para rastrear el pasado
Fue difícil encontrar los artículos principales mencionados en el texto. Sería útil para los lectores que Quanta listara todas las referencias al final del artículo
Existen algoritmos complejos para resolver el problema de ubicar elementos arbitrariamente en una tabla de base de datos. Pero una solución simple para este problema es usar valores fraccionarios y reordenar la lista de vez en cuando
Recuerdo haber planteado este problema a estudiantes basándome en el algoritmo 'Library Sort'. El título del artículo original es 'Insertion Sort is O(n log n)'
Me pregunto si realmente hay una razón para que esto sea más rápido que los algoritmos usados actualmente. En el arreglo de nodos de un B-tree, usar
memmove()podría ser más rápido. Para arreglos grandes, usar árboles B puede ser más fácilMe pregunto si el planteamiento del problema asume un arreglo preasignado de longitud fija
Sorprende la forma en que la Biblioteca Británica gestiona los libros. Cuando llega un libro, el catálogo electrónico se encarga del resto, así que no hace falta reubicar los libros
Quiero convertir la animación de la parte superior del artículo en un salvapantallas
Un enlace limpio para usuarios móviles
Es cierto que el límite superior se reduce a (log n) multiplicado por (log log n)^3. Es interesante que los logaritmos aporten un valor infinitesimal en la complejidad big-O cuando se usan clases de referencia polinómicas