Estudiante universitario refuta conjetura de 40 años e inventa un nuevo tipo de tabla hash [ENG]

Andrew Krapivin, un estudiante de pregrado de la Universidad de Rutgers, revoluciona la ciencias de la computación al refutar una conjetura de hace 40 años: Creó una tabla hash más rápida de lo que se creía posible. Mientras trabajaba en un proyecto sobre "punteros pequeños" (para optimizar el uso de memoria), Krapivin diseñó una nueva estructura de datos que reduce drásticamente el tiempo de búsqueda y almacenamiento de información.

[#1 Laro__]

Aquí el paper:

arxiv.org/abs/2501.02305

[#28 KaisserSozze]

#1 y #2 Gracias, por que mira que es largo el artículo y no explican como funciona.

[#40 hipernes]

#1 aquí el resumen, traducido: Un joven informático y dos colegas muestran que las búsquedas dentro de las estructuras de datos llamadas mesas de hachís pueden ser mucho más rápidas de lo que se consideraba posible.

Drogadictos!

[#4 Estoeslaostia]

#1 paper es el documento, no?
O sea, escribir: "Aquí el documento" no es tan costoso.
Pero bueno, oye, cada uno se alieniza como quiere.

[#9 Laro__]

#4 Un "paper" (término utilizado en el ámbito académico) es un artículo científico o académico que presenta los resultados de una investigación, un estudio teórico, una revisión crítica o un avance en un campo específico del conocimiento. Su objetivo principal es comunicar de manera formal y estructurada hallazgos, metodologías, análisis y conclusiones a la comunidad académica o científica.

Antes de ser publicado, en una revista especializada, es evaluado por otros científicos o investigadores expertos en el área (peer review) para garantizar su calidad y validez.

Para saber más, sobre lo nos está pasando (a ti, y a mi, por intentar no dejarte en la ignorancia), estudiemos:

- El efecto Dunning-Kruger: Quien corrige puede estar tan seguro de su conocimiento que no verifica detalles clave, cayendo en errores por exceso de confianza.

- Complejidad del contexto: Muchos temas (científicos, históricos, técnicos) tienen matices. Una corrección simplista puede omitir excepciones o detalles cruciales.

- El tono importa (y mucho): En Internet, sin señales no verbales, una corrección bienintencionada puede sonar arrogante o condescendiente, desviando la atención del mensaje al tono.

- La paradoja de Brandolini: "La energía requerida para refutar una tontería es un orden de magnitud mayor que la necesaria para producirla". Corregir exige tiempo y precisión; equivocarse en el intento es casi inevitable.

_{---y sí: Este comentario seguramente también caerá en alguna de esos}

[#23 Leovigildo]

#9 #4 Positivo a los dos. A uno por la defensa del castellano, que me parece estupenda. Y a ti por darle sopas por las formas.
@Estoeslaostia, como consejo: algo de laxante por las mañanas para estar de mejor humor.

[#64 carlesm]

#23 Si el problema es el anglicismo (paper) la traducción correcta sería artículo, no documento.

[#65 Leovigildo]

#64 Gracias.

[#12 Estoeslaostia]

#9 #6 Documento.
(_{Muy interesante})

[#16 Marco_Pagot]

#12 ibas a por lana y saliste trasquilado.

Paper está aceptado comúnmente, pero si nos ponemos nazis, documento es una opción aún peor que Paper.

Ensayo, comunicación, ponencia, informe o, entre estudiantes, trabajo.

[#18 Templetonpeck]

#16 #12 #4 Pero ninguno de esos términos corresponde a lo que es un paper y documento es demasiado genérico. El diccionario WordReference propone artículo, que en castellano, si fuera necesario, podría llevar el adjetivo científico, para concretar o distinguirlo del periodístico.  

[#26 KaisserSozze]

#18 Existe una que si corresponde a paper, que es estudio. Según la rae: "Obra de cierta extensión en que se expone y analiza una cuestión determinada."

[#50 sxentinel]

#16 #18 Papiro. Pensadlo bien, no me digas que no seria un termino adecuado a la par de molón para lo mismo.

[#55 Templetonpeck]

#50

[#56 sxentinel]

#55 Tu piensatelo bien, que hasta te llena la boca de sabiduría solo de nombrarlo.

[#25 Ainhoa_96]

#16 Te has dejado la que yo creo que probablemente más se usa: artículo (científico), aunque es cierto que muchos en la uni decimos simplemente paper

[#24 PortgasDAce]

#12 te han dado para el pelo

En todo caso podrías haberte pasado por la RAE al menos para buscar una buena adaptación

www.rae.es/dpd/paper

Pero la realidad es que paper es más específico que todas esas alternativas que lista la RAE.

El más similar sería ensayo y paper en este contexto lleva una connotación extra, ensayo tiene una connotación de subjetividad. Sería como "Ensayo riguroso sobre un tema específico basado en una investigación bien estructurada y referenciada para…   

[#32 Estoeslaostia]

#24 que me han dado para el pelo...eh?
A lo mejor lo confundes con echar un rato.
Vamos, que si. Que documento.

[#37 PortgasDAce]

#32 no uses paella, usa arroz, no uses sushi di pescado crudo, no uses tortilla di huevo cuajado, para que vas a evolucionar el idioma y crear nuevos términos "tú quitar comida, yo abrir tú cabeza", imagino que hablas tal que así

Demuestra inteligencia aceptar los errores, por mucho que lo repitas y pongas emojis sonriendo seguirás siendo el de la imagen, no te engañas ni a ti mismo  

[#29 toche]

#12 El futuro al final resultó ser un lugar lleno de gente con acceso al conocimiento en su bolsillo pero que prefiere regodearse en su ignorancia. Y ufanarse de ello

[#30 Estoeslaostia]

#29 como?... qué?
Conocimiento?
Aixó qui es?
Visca Valensia!

[#47 --670242--]

#12 paper o artículo científico.

[#48 Estoeslaostia]

#47 documento de artículo centífico.
Hasta que el macho de Pérez Reverte, diga lo contrario, esto es.

[#59 --670242--]

#48 menudo cuñado estás hecho

[#60 Estoeslaostia]

#59 y un tío fenomenal de tres sobrines.
Me quieren más que ha sus madres.

[#63 --670242--]

#60 haaaa!!!!. mis hojos!!

[#22 bartolin]

#12 no, no se llama documento...se usan las palabras que todo el mundo utiliza comúnmente, aunque que sean sinónimos. Nadie usa documento

[#21 Miguel_Diaz_2]

#12 Huye hacia adelante, venga. A ver si por reconocer tu error y aprender algo te va a dar urticaria.

Muy de nuestros días.

[#35 DabbaDoo]

#9 "La paradoja de Brandolini..."

I see what you did there!  

[#38 abogado_del_diablo]

#9 Alternativas de Fundéu:
www.fundeu.es/recomendacion/articulo-o-publicacion-alternativas-a-pape

De acuerdo en que puede ser aquí más preciso el término paper, pero ¿cómo lo pronuncias: páper, peiper...?
Escojamos una palabra españolizada para referirnos a paper o añadamos la palabra páper (con tilde) al diccionario.

Pero en mi opinión la peor solución es destrozar como hacemos habitualmente la mayor ventaja del español, su facilidad de lectura (al tener casi todas las letras una única pronunciación), introduciendo anglicismos a menudo por pura pedantería.

[#6 --670242--]

#4 en el mundo de la investigación se denomina paper al documento en formato científico.
Es un formato standard con una estructura común.

[#11 DatosOMientes]

#6 *Estándar.

[#49 sxentinel]

#4 Yo mas que documento, usaría Papiro, suena como mas místico, mas profundo, mas erudito que documento, que esta muy manido.

Eso si, apoyo tu castellanización del termino paper.

[#51 Estoeslaostia]

#49 papiro me gusta.
Venga, que sea papiro.
Eeeehh!! Vosotres!!
Que no es paper!
Que es papiro!

[#52 sxentinel]

#51 Yo estoy ya tratando de evangelizar, pero me siento como profeta en tierra propia.

[#20 totope]

#4 madre mia, pues cuando sepas que las soluciones de los CTF se les denominan writeups.... ????????????????

[#14 Echenique29A]

#4 paper es más corto (eonomía del lenguaje), pero que puede saber un progre/chairo/mamerto amante de la verborrea.

[#2 Pulgencio]

El video donde Andrew lo explica para los que no se quieren bajar el paper de sci-hub
www.youtube.com/watch?v=ArQNyOU1hyE

[#7 --670242--]

#2 pero si está en arxiv!

[#45 alhambre]

#7 se piratea igual.

[#3 alcama]

Me espero al a análisis de MatesMike

[#5 aironman]

Básicamente, el limite máximo teórico antes de llegar a un degradamiento del rendimiento era un 91%. Este investigador ha demostrado que en realidad es un 81%.

Sin más.

[#8 rogerius]

#5 dle.rae.es/?w=degradamiento

[#10 aironman]

#8 ya.

“El rendimiento del sistema se degrada drásticamente a partir del 80% de uso de memoria.”

“El rendimiento del sistema se desploma cuando se llega al 80% del uso de memoria .”

“El rendimiento del sistema colapsa cuando el uso de la memoria llega al 80%“

Mejor ahora? Se entiende mejor ahora?

[#19 Templetonpeck]

#10 Siento entrometerme, pero la palabra que buscas es degradación.
P. Ej. La degradación del rendimiento

[#31 haprendiz]

#10 #19 O también "la pérdida/disminución del rendimiento".

[#42 Fer_3439]

#19 La que busca es "reducimiento"

P.Ej. El reducimiento del rendimiento.

Suena como el culo, pero vuestra querida RAE recoge reducción y reducimiento, pero no le sale de las bolas recoger degradamiento cuando es perfectamente válido de cara a una comunicación efectiva del significado.

#8

Se ve que no la ha utilizado todavía Pérez-Reverte y por eso la RAE no se atreve a recogerla.
No te preocupes #10 yo te apoyo, no todos los de letras somos talibanes de causas perdidas, se les olvida que las lenguas están vivas y la RAE sólo puede recoger lo que a los hablantes nos da la gana de decir o crear, sólo que es demasiado lenta en el proceso.

Si fuera por ellos hablaríamos todavía en latín.

[#46 Templetonpeck]

#42 Como talibán de la lengua, te agradezco tu magnanimidad (Por cierto, me la petan Reverte y la RAE )

[#41 Fer_3439]

#8 .

[#13 Toranks]

#5 ¿Y eso en qué mejora? Más bien parece que pone las cosas peor que ya eran

[#34 aironman]

#13 No solo mejorar los LLM. Las tablas hash son ampliamente usadas en sistemas empotrados, es decir, sistemas críticos aquí y allá. Saber que ese es el límite, te prepara para crear mejores estructuras que complementen a las tablas hash, por ejemplo tablas hash junto con árboles B.

Lo que ha hecho este investigador es hacernos saber como crear software de mayor calidad.

[#53 kaotan]

#34 La mejora propuesta es muy marginal. Solo aplica cuando la tabla hash está casi llena.

[#58 aironman]

#53 yo entiendo que la noticia es que ahora el rendimiento será mayor porque procuraremos no llenar tanto las tablas hash.

[#61 kaotan]

#58 Bueno, esto siempre se ha podido hacer.

[#15 WcPC]

#13 Mayor eficiencia en el uso de RAM, por ejemplo.
Recordemos que el principal problema que ha mantenido a los LLM (lo que la gente llama IA) para evolucionar hasta hace poco es el uso excesivo de la RAM, puede no ser nada, que valga solo para tener una RAM mejor, o ser algo revolucionario, depende de lo que afecte o el tipo de algoritmos nuevos que podamos usar de manera más eficiente.
Realmente conocer los límites de cualquier cosa si es tela de útil.

[#43 LuigiR]

#13 saber que la estructura que estás usando deja de ser eficiente en un umbral más bajo te da información para evitar escenarios en los que estas tablas dejan de ser rápidas.

Supongo que si antes no se sabía que el límite era tan bajo habría bastante software yendo más lento de la cuenta en determinadas circunstancias, ahora se podrá optimizar.

[#17 slepo]

Entiendo que un estudiante de pregrado en las universidades americanas, es un estudiante de grado en España, ¿no? alguien que todavía está estudiando una licenciatura (no sé si eso existe) o un grado o una ingeniería.

¡Vaya crack!

[#27 tyrrelco]

#17 En el Reino Unido, a los estudiantes de un grado se les llamaba undergraduate, estudiando el grado, todavía sin haber obtenido el grado. Así que supongo que sí, es un estudiante de grado.

[#33 Find]

Meanwhile, en España, la gente se queja de por qué no enseñan 'ponga aquí la última tecnología' en la universidad, ya que no se sale preparado para trabajar

[#36 euacca]

Se puede deducir del artículo pero creo que no lo dice claramente: Que yo sepa nunca se manejan tablas hash tan llenas. Cuando alcanzan un umbral se amplían (se rehacen pero más grandes) y eso cuesta tiempo y es un desperdicio de memoria. Creo que este logro va más por el ahorro de memoria que por el tiempo de búsqueda, en la práctica. A lo mejor se ahorra un 30% de memoria. No de la memoria total, que los datos ocupan lo que ocupan, sino de la memoria extra empleada en tener los datos organizados. Con esta logro quizá no se amplíen las tablas hash de nueva generación hasta que no estén llenas casi del todo. Lo malo es que ampliarlas sigue siendo costoso, por lo que se ampliarán de más para no tener que hacerlo cada poco, igualmente.

[#39 cantarranas]

#36 También me parece entender que el rendimiento de esta nueva tabla se degrada cuando está un 10% más llena que las anteriores.
Si es así, significa que se podrá almacenar un 10% más de datos antes de regenerar la tabla, es decir, que habrá que regenerarla menos veces que las anteriores, en concreto un 10% menos. Y también parece que mejora bastante el tiempo medio de inserción de nuevos elementos.

[#54 kaotan]

#36 Un 30% es muchísimo. Una tabla con un 30% libre no tiene ningún problema en alocar colisiones sin apenas ningún degradamiento.

[#57 euacca]

#54 en alocar no, pero si no me equivoco, o quizá depende de la implementación, al leer si tú encuentras un elemento en la posición que indica la función hash y ese elemento no es en que buscas te toca mirar en otros sitios y eso implica comparar más elementos, y compararlos tiene un coste. Las colisiones tienen un coste en lectura también. Lo ideal es que no las haya o tener las ventajas de este nuevo sistema que hace que te penalicen menos.

[#62 kaotan]

#57 Sí, eso es lo que yo he entendido también. Aunque no lo he leido hasta el final.

[#44 Bourée]

#0 te has adelantado a #mr_b
Un saludo para cada uno.