Este es quizás uno de los desafíos de codificación clásicos que tuvieron cierta resonancia en 1986, cuando el columnista Jon Bentley le pidió a Donald Knuth que escribiera un programa que encontrara las palabras más frecuentes en un archivo. Knuth implementó una solución rápida utilizando pruebas hash en un programa de 8 páginas para ilustrar su técnica de programación alfabetizada. Douglas McIlroy, de Bell Labs, criticó la solución de Knuth porque ni siquiera podía procesar un texto completo de la Biblia, y respondió con una sola frase, que no es tan rápido, pero hace el trabajo:
tr -cs A-Za-z '\n' | tr A-Z a-z | sort | uniq -c | sort -rn | sed 10q
En 1987, se publicó un artículo de seguimiento con otra solución más, esta vez por un profesor de Princeton. ¡Pero tampoco podía devolver el resultado para una sola Biblia!
Descripción del problema
Descripción original del problema:
Dado un archivo de texto y un entero k, debe imprimir las k palabras más comunes en el archivo (y el número de sus ocurrencias) en frecuencia decreciente.
Aclaraciones adicionales del problema:
- Knuth definió una palabra como una cadena de letras latinas:
[A-Za-z]+
- todos los otros personajes son ignorados
- las letras mayúsculas y minúsculas se consideran equivalentes (
WoRd
==word
) - sin límite en el tamaño del archivo ni en la longitud de la palabra
- las distancias entre palabras consecutivas pueden ser arbitrariamente grandes
- el programa más rápido es el que usa menos tiempo total de CPU (el subprocesamiento múltiple probablemente no ayudará)
Muestra de casos de prueba
Prueba 1: Ulises de James Joyce concatenado 64 veces (archivo de 96 MB).
- Descargar Ulysses del Proyecto Gutenberg:
wget http://www.gutenberg.org/files/4300/4300-0.txt
- Concatenarlo 64 veces:
for i in {1..64}; do cat 4300-0.txt >> ulysses64; done
- La palabra más frecuente es "el" con 968832 apariciones.
Prueba 2: Texto aleatorio especialmente generado giganovel
(alrededor de 1 GB).
- Script generador de Python 3 aquí .
- El texto contiene 148391 palabras distintas que aparecen de manera similar a los lenguajes naturales.
- Palabras más frecuentes: "e" (11309 apariciones) y "ihit" (11290 apariciones).
Prueba de generalidad: palabras arbitrariamente grandes con espacios arbitrariamente grandes.
Implementaciones de referencia
Después de investigar el Código de Rosetta para este problema y darme cuenta de que muchas implementaciones son increíblemente lentas (¡más lento que el script de shell!), Probé algunas implementaciones buenas aquí . A continuación se muestra el rendimiento ulysses64
junto con la complejidad del tiempo:
ulysses64 Time complexity
C++ (prefix trie + heap) 4.145 O((N + k) log k)
Python (Counter) 10.547 O(N + k log Q)
AWK + sort 20.606 O(N + Q log Q)
McIlroy (tr + sort + uniq) 43.554 O(N log N)
¿Puedes vencer eso?
Pruebas
El rendimiento se evaluará utilizando 2017 13 "MacBook Pro con el time
comando estándar de Unix (tiempo" usuario "). Si es posible, utilice compiladores modernos (por ejemplo, use la última versión de Haskell, no la versión anterior).
Rankings hasta ahora
Tiempos, incluidos los programas de referencia:
k=10 k=100K
ulysses64 giganovel giganovel
C++ (trie) by ShreevatsaR 0.671 4.227 4.276
C (trie + bins) by Moogie 0.704 9.568 9.459
C (trie + list) by Moogie 0.767 6.051 82.306
C++ (hash trie) by ShreevatsaR 0.788 5.283 5.390
C (trie + sorted list) by Moogie 0.804 7.076 x
Rust (trie) by Anders Kaseorg 0.842 6.932 7.503
J by miles 1.273 22.365 22.637
C# (trie) by recursive 3.722 25.378 24.771
C++ (trie + heap) 4.145 42.631 72.138
APL (Dyalog Unicode) by Adám 7.680 x x
Python (dict) by movatica 9.387 99.118 100.859
Python (Counter) 10.547 102.822 103.930
Ruby (tally) by daniero 15.139 171.095 171.551
AWK + sort 20.606 213.366 222.782
McIlroy (tr + sort + uniq) 43.554 715.602 750.420
Clasificación acumulada * (%, mejor puntaje posible - 300):
# Program Score Generality
1 C++ (trie) by ShreevatsaR 300 Yes
2 C++ (hash trie) by ShreevatsaR 368 x
3 Rust (trie) by Anders Kaseorg 465 Yes
4 C (trie + bins) by Moogie 552 x
5 J by miles 1248 Yes
6 C# (trie) by recursive 1734 x
7 C (trie + list) by Moogie 2182 x
8 C++ (trie + heap) 3313 x
9 Python (dict) by movatica 6103 Yes
10 Python (Counter) 6435 Yes
11 Ruby (tally) by daniero 10316 Yes
12 AWK + sort 13329 Yes
13 McIlroy (tr + sort + uniq) 40970 Yes
* Suma de rendimiento de tiempo en relación con los mejores programas en cada una de las tres pruebas.
El mejor programa hasta ahora: aquí (segunda solución)
fuente
Respuestas:
[C]
Lo siguiente se ejecuta en menos de 1.6 segundos para la Prueba 1 en mi 2.8 Ghz Xeon W3530. Creado con MinGW.org GCC-6.3.0-1 en Windows 7:
Toma dos argumentos como entrada (ruta al archivo de texto y para k el número de palabras más frecuentes para enumerar)
Simplemente crea un árbol que se ramifica en letras de palabras, luego, en las letras de las hojas, incrementa un contador. Luego verifica si el contador de hojas actual es mayor que la palabra más frecuente más pequeña en la lista de palabras más frecuentes. (el tamaño de la lista es el número determinado mediante el argumento de la línea de comando) Si es así, promueva la palabra representada por la letra de la hoja como una de las más frecuentes. Todo esto se repite hasta que no se leen más letras. Después de lo cual se genera la lista de palabras más frecuentes a través de una búsqueda iterativa ineficaz de la palabra más frecuente de la lista de palabras más frecuentes.
Actualmente, el tiempo de procesamiento predeterminado es el de salida, pero para fines de coherencia con otras presentaciones, deshabilite la definición de TIMING en el código fuente.
Además, lo he enviado desde una computadora del trabajo y no he podido descargar el texto de la Prueba 2. Debería funcionar con esta Prueba 2 sin modificación, sin embargo, es posible que sea necesario aumentar el valor de MAX_LETTER_INSTANCES.
Para la Prueba 1, y para las 10 palabras más frecuentes y con el tiempo habilitado, debe imprimir:
fuente
letters
matriz, mientras que la implementación de referencia asigna nodos de árbol dinámicamente.mmap
-ing debe ser más rápido (~ 5% en mi portátil Linux):#include<sys/mman.h>
,<sys/stat.h>
,<fcntl.h>
, reemplazar el archivo de lectura conint d=open(argv[1],0);struct stat s;fstat(d,&s);dataLength=s.st_size;data=mmap(0,dataLength,1,1,d,0);
y comentefree(data);
Oxido
En mi computadora, esto ejecuta giganovel 100000 aproximadamente un 42% más rápido (10.64 s frente a 18.24 s) que la solución C de C "prefijo árbol + contenedores" de Moogie. Además, no tiene límites predefinidos (a diferencia de la solución C que define los límites de longitud de palabra, palabras únicas, palabras repetidas, etc.).
src/main.rs
Cargo.toml
Uso
fuente
-O3
, y-Ofast
no hace una diferencia apreciable.gcc -O3 -march=native -mtune=native program.c
.APL (Dyalog Unicode)
Lo siguiente se ejecuta en menos de 8 segundos en mi 2.6 Ghz i7-4720HQ usando Dyalog APL 17.0 de 64 bits en Windows 10:
Primero solicita el nombre del archivo, luego k. Tenga en cuenta que una parte importante del tiempo de ejecución (aproximadamente 1 segundo) es solo leer el archivo.
Para cronometrarlo, debe poder canalizar lo siguiente en su
dyalog
ejecutable (para las diez palabras más frecuentes):Debería imprimir:
fuente
export MAXWS=4096M
. ¿Supongo que usa tablas hash? Porque reducir el tamaño del espacio de trabajo a 2 GB lo hace más lento en 2 segundos completos.∊
usa una tabla hash según esto , y estoy bastante seguro de⌸
que también lo hace internamente.WS FULL
, aunque aumenté el espacio de trabajo a 6 GB.[C] Árbol de prefijo + contenedores
NOTA: ¡El compilador utilizado tiene un efecto significativo en la velocidad de ejecución del programa! He usado gcc (MinGW.org GCC-8.2.0-3) 8.2.0. Cuando se usa elinterruptor -Ofast , el programa se ejecuta casi un 50% más rápido que el programa compilado normalmente.
Complejidad Algoritmo
Desde entonces me di cuenta de que la clasificación de Bin que estoy realizando es una forma de clasificación de Pigeonhost, lo que significa que puedo superar la complejidad de Big O de esta solución.
Lo calculo para ser:
La complejidad de la construcción del árbol es equivalente a la transversal del árbol, por lo que, en cualquier nivel, el nodo correcto para atravesar es O (1) (ya que cada letra se asigna directamente a un nodo y siempre atravesamos solo un nivel del árbol para cada letra)
La clasificación de Pigeon Hole es O (N + n) donde n es el rango de valores clave, sin embargo, para este problema, no necesitamos ordenar todos los valores, solo el número k, por lo que el peor de los casos sería O (N + k).
La combinación de juntos produce O (1 + N + k).
La complejidad espacial para la construcción de árboles se debe al hecho de que el peor de los casos es 26 * M nodos si los datos consisten en una palabra con M número de letras y que cada nodo tiene 26 nodos (es decir, para las letras del alfabeto). Así O (26 * M) = O (M)
Para el Pigeon Hole la clasificación tiene una complejidad espacial de O (N + n)
La combinación de todos produce O (26 * M + N + n) = O (M + N + n)
Algoritmo
Toma dos argumentos como entrada (ruta al archivo de texto y para k el número de palabras más frecuentes para enumerar)
Según mis otras entradas, esta versión tiene una rampa de costo de tiempo muy pequeña con valores crecientes de k en comparación con mis otras soluciones. Pero es notablemente más lento para valores bajos de k, sin embargo, debería ser mucho más rápido para valores mayores de k.
Crea un árbol que se ramifica en letras de palabras, luego, en las letras de las hojas, incrementa un contador. Luego agrega la palabra a un contenedor de palabras del mismo tamaño (después de eliminar primero la palabra del contenedor en el que ya residía). Todo esto se repite hasta que no se leen más letras. Después de lo cual, los contenedores se repiten en iteración k veces comenzando desde el contenedor más grande y se emiten las palabras de cada contenedor.
Actualmente, el tiempo de procesamiento predeterminado es el de salida, pero para fines de coherencia con otras presentaciones, deshabilite la definición de TIMING en el código fuente.
EDITAR: ahora diferiendo los contenedores de población hasta que se haya construido el árbol y optimizando la construcción de la salida.
EDIT2: ahora utiliza la aritmética del puntero en lugar del acceso a la matriz para la optimización de la velocidad.
fuente
ulysses64
una vez, por lo que ahora es un líder actual.J
Ejecutar como un script con
jconsole <script> <input> <k>
. Por ejemplo, la salida degiganovel
conk=100K
:No hay límite, excepto por la cantidad de memoria disponible del sistema.
fuente
...
ocurre debido al truncamiento de salida por línea. Agregué una línea al inicio para deshabilitar todo el truncamiento. Se ralentiza en giganovel ya que usa mucha más memoria ya que hay más palabras únicas.C ++ (a la Knuth)
Tenía curiosidad por saber cómo le iría al programa de Knuth, así que traduje su programa (originalmente Pascal) a C ++.
Aunque el objetivo principal de Knuth no era la velocidad, sino ilustrar su sistema WEB de programación alfabetizada, el programa es sorprendentemente competitivo y lleva a una solución más rápida que cualquiera de las respuestas hasta ahora. Aquí está mi traducción de su programa (los números de "sección" correspondientes del programa WEB se mencionan en comentarios como "
{§24}
"):Diferencias con el programa de Knuth:
link
,sibling
,count
ych
en una matriz de unstruct Node
(resulta más fácil de entender de esta manera).fread
ydata[i] | 32 - 'a'
como en las otras respuestas aquí, en lugar de la solución alternativa de Pascal.Aparte de eso, este es más o menos exactamente el programa de Knuth (usando su estructura de datos hash trie / empaquetado trie y tipo de cubeta), y realiza prácticamente las mismas operaciones (como lo haría el programa Knuth's Pascal) mientras recorre todos los caracteres en la entrada; tenga en cuenta que no utiliza algoritmos externos o bibliotecas de estructura de datos, y también que las palabras de igual frecuencia se imprimirán en orden alfabético.
Sincronización
Compilado con
Cuando se ejecuta en el caso de prueba más grande aquí (
giganovel
con 100,000 palabras solicitadas), y se compara con el programa más rápido publicado aquí hasta ahora, lo encuentro un poco, pero consistentemente más rápido:(La línea superior es la solución Rust de Anders Kaseorg; la inferior es el programa anterior. Estos son tiempos de 100 ejecuciones, con medias, mínimas, máximas, medianas y cuartiles).
Análisis
¿Por qué es esto más rápido? No es que C ++ sea más rápido que Rust, o que el programa de Knuth sea el más rápido posible; de hecho, el programa de Knuth es más lento en las inserciones (como él menciona) debido al empaquetado de trie (para conservar la memoria). Sospecho que la razón está relacionada con algo de lo que Knuth se quejó en 2008 :
El programa anterior utiliza índices de matriz de 32 bits (no punteros de 64 bits), por lo que la estructura "Nodo" ocupa menos memoria, por lo que hay más nodos en la pila y menos errores de caché. (De hecho, hubo algo de trabajo en esto como el x32 ABI , pero parece que no está en buen estado a pesar de que la idea es obviamente útil, por ejemplo, vea el reciente anuncio de compresión de puntero en V8 . Oh, bueno).
giganovel
, este programa usa 12.8 MB para el trie (empaquetado), en comparación con los 32.18MB del programa Rust para su trie (activadogiganovel
). Podríamos escalar 1000x (desde "giganovel" hasta "teranovel", por ejemplo) y aún no superar los índices de 32 bits, por lo que esta parece una opción razonable.Variante más rápida
Podemos optimizar la velocidad y renunciar al empaque, por lo que en realidad podemos usar el trie (no empaquetado) como en la solución Rust, con índices en lugar de punteros. Esto da algo que es más rápido y no tiene límites preestablecidos en el número de palabras distintas, caracteres, etc.
Este programa, a pesar de hacer algo mucho más difícil de ordenar que las soluciones aquí, utiliza (para
giganovel
) solo 12.2MB para su trie y logra ser más rápido. Tiempos de este programa (última línea), en comparación con los tiempos anteriores mencionados:Estaría ansioso por ver qué le gustaría a este (o al programa hash-trie) si se tradujera a Rust . :-)
Más detalles
Acerca de la estructura de datos utilizada aquí: en el ejercicio 4 de la Sección 6.3 (Búsqueda digital, es decir, intentos) en el Volumen 3 de TAOCP, y en la tesis del alumno de Knuth Frank Liang sobre la separación silábica en TeX, se ofrece una explicación de los intentos de "empaquetamiento". : Palabra Hy-phen-a-ción por Com-put-er .
El contexto de las columnas de Bentley, el programa de Knuth y la revisión de McIlroy (solo una pequeña parte de la cual era sobre la filosofía de Unix) es más claro a la luz de las columnas anteriores y posteriores. , y la experiencia previa de Knuth incluyendo compiladores, TAOCP y TeX.
Hay un libro completo Ejercicios en estilo de programación , que muestra diferentes enfoques para este programa en particular, etc.
Tengo una publicación de blog inacabada que explica los puntos anteriores; podría editar esta respuesta cuando esté hecho. Mientras tanto, publicar esta respuesta aquí de todos modos, en la ocasión (10 de enero) del cumpleaños de Knuth. :-)
fuente
Segmentation fault: 11
para casos de prueba con palabras y espacios arbitrariamente grandes; 2) aunque pueda parecer que simpatizo con la "crítica" de McIlroy, soy muy consciente de que la intención de Knuth era solo mostrar su técnica de programación alfabetizada, mientras que McIlroy la criticó desde la perspectiva de la ingeniería. El propio McIlroy más tarde admitió que no era justo hacerlo.word_for
; Lo arregló ahora. Sí, McIlroy, como inventor de las tuberías Unix, aprovechó la oportunidad para evangelizar la filosofía Unix de componer pequeñas herramientas. Es una buena filosofía, en comparación con el enfoque monolítico frustrante de Knuth (si está tratando de leer sus programas), pero en el contexto fue un poco injusto, también por otra razón: hoy en día, la forma Unix está ampliamente disponible, pero en 1986 estaba confinado a Bell Labs, Berkeley, etc. ("su empresa fabrica los mejores prefabricados en el negocio")Python 3
Esta implementación con un diccionario simple es ligeramente más rápida que la que usa
Counter
uno en mi sistema.fuente
heapq
no agrega ningún rendimiento alCounter.most_common
método, oenumerate(sorted(...))
también lo usaheapq
internamente.Counter.most_common
.[C] Árbol de prefijos + Lista vinculada ordenada
Toma dos argumentos como entrada (ruta al archivo de texto y para k el número de palabras más frecuentes para enumerar)
Basado en mi otra entrada, esta versión es mucho más rápida para valores más grandes de k pero a un costo menor de rendimiento a valores más bajos de k.
Crea un árbol que se ramifica en letras de palabras, luego, en las letras de las hojas, incrementa un contador. Luego verifica si el contador de hojas actual es mayor que la palabra más frecuente más pequeña en la lista de palabras más frecuentes. (el tamaño de la lista es el número determinado mediante el argumento de la línea de comando) Si es así, promueva la palabra representada por la letra de la hoja como una de las más frecuentes. Si ya es una palabra más frecuente, cambie con la siguiente más frecuente si el recuento de palabras ahora es más alto, manteniendo así la lista ordenada. Todo esto se repite hasta que no se leen más letras. Después de lo cual se emite la lista de palabras más frecuentes.
Actualmente, el tiempo de procesamiento predeterminado es el de salida, pero para fines de coherencia con otras presentaciones, deshabilite la definición de TIMING en el código fuente.
fuente
12 eroilk 111 iennoa 10 yttelen 110 engyt
.C#
Este debería funcionar con los últimos SDK de .net .
Aquí hay una muestra de salida.
Al principio, traté de usar un diccionario con teclas de cadena, pero eso fue demasiado lento. Creo que se debe a que las cadenas .net están representadas internamente con una codificación de 2 bytes, lo que es un desperdicio para esta aplicación. Entonces, simplemente cambié a bytes puros y a una máquina de estado fea y goto-style. La conversión de mayúsculas y minúsculas es un operador bit a bit. La verificación del rango de caracteres se realiza en una sola comparación después de la resta. No pasé ningún esfuerzo optimizando la clasificación final ya que descubrí que está usando menos del 0.1% del tiempo de ejecución.
Solución: el algoritmo era esencialmente correcto, pero informaba en exceso las palabras totales, contando todos los prefijos de palabras. Como el recuento total de palabras no es un requisito del problema, eliminé esa salida. Para generar todas las k palabras, también ajusté la salida. Finalmente decidí usar
string.Join()
y luego escribir toda la lista de una vez. Sorprendentemente, esto es aproximadamente un segundo más rápido en mi máquina que escribir cada palabra por separado para 100k.fuente
tolower
trucos de comparación bit a bit y únicos. Sin embargo, no entiendo por qué su programa informa más palabras distintas de lo esperado. Además, de acuerdo con la descripción original del problema, el programa necesita generar todas las k palabras en orden decreciente de frecuencia, por lo que no conté su programa para la última prueba, que necesita generar 100,000 palabras más frecuentes.Ruby 2.7.0-preview1 con
tally
La última versión de Ruby tiene un nuevo método llamado
tally
. De las notas de la versión :Esto casi resuelve toda la tarea para nosotros. Solo necesitamos leer el archivo primero y encontrar el máximo después.
Aquí está todo:
editar: agregado
k
como argumento de línea de comandoSe puede ejecutar con
ruby k filename.rb input.txt
la versión 2.7.0-preview1 de Ruby. Esto se puede descargar desde varios enlaces en la página de notas de la versión, o instalar con rbenv usandorbenv install 2.7.0-dev
.Ejemplo ejecutado en mi propia computadora vieja y destartalada:
fuente