Investigación de un estudiante de pregrado demuestra una mejora en la velocidad de búsqueda dentro de una tabla hash

Introducción

• En el otoño de 2021, Andrew Krapivin, estudiante de pregrado en Rutgers University, se encontró con un artículo que cambiaría su vida.
• El artículo trataba sobre "punteros pequeños" que apuntan a información en la memoria de una computadora.
• Krapivin ideó una forma de hacer más pequeños los punteros para reducir el consumo de memoria.

Descubrimiento de una nueva tabla hash

• Krapivin realizó experimentos usando tablas hash, un método común para almacenar datos.
• Durante los experimentos, Krapivin terminó inventando un nuevo tipo de tabla hash que funciona más rápido que las existentes.
• Este hallazgo produjo un resultado que derriba una conjetura de 40 años en ciencia de datos.

La importancia de las tablas hash

• Las tablas hash son una de las estructuras de datos más antiguas en ciencias de la computación y ofrecen eficiencia para el almacenamiento de datos.
• Las tablas hash están diseñadas para poder realizar tres funciones: buscar, eliminar e insertar elementos.

La conjetura de Yao y su refutación

• En 1985, el científico computacional Andrew Yao propuso una conjetura sobre cómo encontrar elementos en el peor caso dentro de tablas hash con ciertas propiedades.
• La nueva tabla hash de Krapivin refuta la conjetura de Yao y demuestra que el tiempo necesario para consultas e inserciones en el peor caso es proporcional a (log x)².

Nuevo hallazgo sobre el tiempo promedio de consulta

• Krapivin y su equipo mostraron que, en tablas hash no codiciosas, el tiempo promedio de consulta no depende de x.
• Esto significa que se puede lograr un tiempo promedio de consulta constante sin importar qué tan llena esté la tabla hash.

Conclusión

• Esta investigación profundiza la comprensión de las tablas hash y podría conducir a aplicaciones prácticas.
• Este entendimiento de las estructuras de datos puede convertirse en la base de futuras mejoras prácticas.

[GN⁺]

Comentarios en Hacker News

• Krapivin logró un avance sin conocer la conjetura de Yao

  • El desarrollador de Balatro creó un premiado juego de construcción de mazos sin conocer los deck builders existentes
  • La mejor forma de abordar un problema podría ser hacerlo sin conocer o ignorando esfuerzos similares previos
  • El mundo actual está demasiado interconectado, así que es fácil quedar atrapado en marcos de pensamiento previos
  • Internet es maravilloso, pero tiende a homogeneizar el mundo de las ideas

• Es un gran resultado, pero parece que debería llamarse una conjetura de ciencias de la computación

• Me pregunto si alguien conoce un repositorio de GitHub con esta implementación

• Está bien, pero el estilo de "celebrificación" de este artículo me incomoda un poco

  • Me pregunto si realmente hacía falta ver varias fotos de una persona joven posando de distintas maneras en un entorno universitario
  • Parece que hace falta una versión de La La Land para glorificar a los sobrevivientes del éxito en computación y así incentivar una mayor participación

• En la nueva tabla hash, el tiempo requerido en el peor caso para consultas e inserciones es proporcional a (log x)²

  • Puede que el resultado del equipo no lleve a aplicaciones inmediatas
  • No entiendo por qué no llevaría a aplicaciones inmediatas
  • Me pregunto si hay casos donde analizar usos reales permita ajustar mejor una implementación de hash que un enfoque puramente matemático

• Leer este artículo es como leer una explicación del problema de Monty Hall

  • La conclusión parece ir en contra del sentido común, pero puede demostrarse
  • Ni siquiera los autores esperaban que fuera posible lograr un tiempo promedio constante de consulta sin importar qué tan llena esté la tabla hash

• Es una buena prueba reciente

  • Veamos si la investigación profunda puede producir este resultado sin copiarlo
  • gpt4, Gemini 2 y Claude no tuvieron suerte
  • La informática guiada por humanos sigue estando a salvo

• Me pregunto si alguien tiene una implementación sencilla de 'Tiny pointers'

  • Mi mente va antes al código/pseudocódigo que a la demostración

• Como siempre decía el villano de <i>Scooby Doo</i>:

  • <i>"¡Y lo habría logrado si no hubiera sido por esos chicos entrometidos!"</i>

• Hojeando el artículo, parece que la principal diferencia que usaron es que el algoritmo de inserción de la tabla hash busca más lejos en vez de llenar de forma codiciosa el primer espacio vacío

  • Lo combinan con un orden de búsqueda demostrablemente eficiente para encontrar espacios vacíos incluso cuando la tabla está muy llena
  • Cuando la tabla hash está menos llena, las inserciones se vuelven más lentas, pero se puede evitar el peor escenario de no encontrar el último espacio vacío restante

• Es un resultado teórico interesante, pero en la práctica parece que el "truco" actual de asignar una tabla más grande de la necesaria sería una mejor solución

  • Por ejemplo, hashbrown de Rust deja libre 1/8 de la tabla (12.5%), usa un poco más de memoria, pero hace que inserciones y búsquedas sean muy rápidas