Un nuevo algoritmo para clasificar los libros que casi alcanza la perfección

Imagen vía Depositphotos.

Cualquiera que tenga una cantidad considerable de libros sabe lo complicado que puede ser organizarlos, de forma que se simplifique al máximo el acto de añadir libros nuevos a la colección. Imaginemos, por ejemplo, que utilizando un orden alfabético se mantienen los libros agrupados desde la izquierda, dejando un espacio vacío en el extremo derecho de la última balda ocupada. Si añadimos un libro cuyo autor empiece por la «A», se tendrían que mover prácticamente todos los libros. Una idea para evitar moverlos todos es ir dejando espacios desocupados distribuidos por todas las baldas, pero entonces la pregunta sería ¿cómo se deberían distribuir exactamente?

Este problema se planteó por primera vez en un artículo de 1981 y tiene consecuencias más allá del simple orden de una biblioteca. Esta situación, en realidad, también podría darse con archivos de bases de datos donde los elementos que hay que ordenar pueden ascender a miles de millones. Un sistema de organización poco eficiente puede suponer tiempos de espera muy elevados y como consecuencia un mayor gasto. Es por eso que desde hace décadas se ha intentado determinar la mejor y más eficiente manera posible para almacenar elementos.

El año pasado, en un estudio presentado en la conferencia Foundations of Computer Science de Chicago, un equipo de siete investigadores describió una forma de organizar elementos que se acerca mucho a una especie de ideal teórico. Este nuevo enfoque combina un poco de lo anterior con el sorprendente poder de la aleatoriedad.

¿Cómo se determina entonces si una estantería está bien ordenada? Una forma de medirlo es ver cuánto tiempo se tarda en introducir un nuevo elemento en ella. Naturalmente, eso depende de cuántos elementos haya previamente, un valor que normalmente se denomina n. En el ejemplo de introducir un libro de un autor cuyo apellido empiece por «A», cuando todos los libros tienen que moverse para dar cabida al nuevo, el tiempo que se tarda es proporcional a n. Cuanto mayor sea n, más tiempo se tarda. Eso hace que nunca se necesite más tiempo que un tiempo proporcional a n para añadir un libro a la estantería.

Los autores del artículo de 1981 que dio origen a este problema querían saber si era posible diseñar un algoritmo con un tiempo de inserción menor que n y, de hecho, demostraron que se podía. Crearon un algoritmo con dos propiedades: era «determinista», lo que significa que sus decisiones no dependían de ninguna aleatoriedad, y también era «suave», lo que significa que los libros debían estar distribuidos de manera uniforme dentro de las subsecciones del estante donde se realizan las inserciones (o eliminaciones). Los autores dejaron abierta la cuestión de si el límite superior podría mejorarse aún más. Durante más de cuatro décadas, nadie logró hacerlo.

Sin embargo, desde entonces se han producido mejoras en el límite inferior. Mientras que el límite superior especifica el tiempo máximo posible necesario para insertar un libro, el límite inferior proporciona el tiempo de inserción más rápido posible. Para encontrar una solución definitiva a este problema, los investigadores se han esforzado por reducir la distancia entre el límite superior y el inferior, tratando de que coincidan. Si esto sucede, el algoritmo se considera óptimo, sin dejar margen de mejora.

En 2022, Michael Bender, informático de la Universidad de Stony Brook, y otros cinco colegas decidieron probar un algoritmo aleatorio y no suave, solo para ver si podría ser mejor, y consiguieron reducir el límite superior de 1981, lo que reduce el tiempo de inserción de media. A continuación mejoraron todavía más el algoritmo teniendo en cuenta la tendencia de la colección para planificar el futuro, pero solo hasta cierto punto. Supongamos, por ejemplo, que se han incorporado muchos libros de autores cuyo apellido comienza con «A». El algoritmo asume que probablemente se añadan más, por lo que dejará un poco de espacio adicional en esa sección, pero solo un poco más, porque reservar demasiado espacio podría causar problemas si comienzan a aparecer muchos autores con otra letra. Este algoritmo representa, en palabras de Brian Wheatman, informático de la Universidad de Chicago, «una mejora significativa» desde el punto de vista teórico. Y añade: «En el ámbito aplicado, creo que también tienen potencial para una gran mejora».

Fuente.

The post Un nuevo algoritmo para clasificar los libros que casi alcanza la perfección appeared first on La piedra de Sísifo.