Lunes, 16 de noviembre de 2026
Portada de las 21:50
Todos los periódicos y la radio, en unoEscrito por IA a partir de Hacker News · Cómo se hace
Hacker News
Programación · wiredream.com

11 nanosegundos por palabra: sobreoptimizar la búsqueda de anagramas

Dave Andersen cuenta cómo aceleró la construcción de un diccionario de anagramas en Rust, de 173 a 11 ns por palabra. El truco central es asignar primos a las letras para que el producto de cada palabra del diccionario Scrabble quepa en un entero de 64 bits sin colisiones.

Foto: vía wiredream.com

Leer el artículo aquíArtículo original (wiredream.com) 3 comentarios en Hacker News

Escucha la noticia3 min

Andersen parte de un juego de word ladder en el que se puede cambiar una letra, quitarla, añadirla o reordenar la palabra. Los caminos con anagramas son difíciles de ver, así que escribió un solucionador y, al tardar más de un segundo, se puso a optimizarlo. Aquí solo trata la parte de encontrar todos los anagramas de un diccionario; el solucionador completo queda para otro post.

La versión base usa como clave la palabra con las letras ordenadas y un HashMap<String, Vec<String>>. Con el diccionario Scrabble (178.690 entradas) tarda 31 ms, unos 173 ns por palabra. Después elimina las asignaciones de Vec: como hay unas 161.000 claves para 178.000 palabras, casi todas son únicas. Guarda los casos únicos directamente y encadena el resto con una lista enlazada sobre arrays de u32, usando el bit alto para distinguir ambos casos. Baja a 20 ms.

El siguiente paso sustituye el ordenado de cadenas por un vector de recuentos de letras, con 4 bits por letra empaquetados en un u128 (26 × 4 = 104 bits). Baja a 5,6 ms (31 ns por palabra). Cambiar el hash por defecto de Rust por FxHashMap, de rustc_hash, lo deja en 4,1 ms (23 ns por palabra).

Para pasar a 64 bits usa una numeración de Gödel: un primo por letra y, como identificador de cada palabra, el producto de sus primos. Con la asignación ingenua (a=2, b=3, c=5…) hay desbordamiento ya en la palabra 365, «ABORTIVENESSES». Andersen optimizó la asignación mirando las 3.157 palabras de 15 letras: E=2, I=3, S=17, N=19, T=29 y J=101, porque la palabra más larga con dos J solo tiene 12 letras. Un programa partía del orden por frecuencia y, ante cada palabra que desbordaba, cambiaba primos por otros menores. El resultado es una tabla que no desborda con ninguna palabra del diccionario Scrabble y da un identificador canónico sin colisiones. El texto se corta antes de mostrar los tiempos finales de esta versión.

En Hacker News

«11 Nanoseconds per Word: Over-Optimizing Anagrams» · puesto 29 · 19 puntos · enviado por ColinWright

Lo que dicen los comentarios

El post aún no tiene comentarios en Hacker News, así que todavía no hay conversación que resumir.

Pregunta sobre esta noticia

Respuestas automáticas a partir de las noticias de El Autómata, sus fuentes y la radio. Pueden contener errores: comprueba los enlaces.

Esta noticia la ha redactado una inteligencia artificial a partir de las fuentes citadas, con el criterio editorial de El Autómata (equilibrio, atribución y solo hechos publicados). Puede contener errores: consulta las fuentes originales. Modelo: claude-sonnet-5.5.