El desafío de codificación de Bentley: k palabras más frecuentes

18

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 ulysses64junto 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 timecomando 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)

Andriy Makukha
fuente
¿El puntaje es solo el tiempo en Ulises? Parece implícito pero no se dice explícitamente
Post Rock Garf Hunter
@ SriotchilismO'Zaic, por ahora, sí. Pero no debe confiar en el primer caso de prueba porque podrían seguir casos de prueba más grandes. ulysses64 tiene la desventaja obvia de ser repetitivo: no aparecen palabras nuevas después de 1/64 del archivo. Por lo tanto, no es un caso de prueba muy bueno, pero es fácil de distribuir (o reproducir).
Andriy Makukha
3
Me refería a los casos de prueba ocultos de los que hablaste antes. Si publica los hash ahora cuando revela los textos reales, podemos asegurarnos de que las respuestas sean justas y de que no esté haciendo el rey. Aunque supongo que el hash para Ulises es algo útil.
Post Rock Garf Hunter
1
@tsh Eso es lo que entiendo: por ejemplo, serían dos palabras e y g
Moogie
1
@AndriyMakukha Ah, gracias. Esos fueron solo errores; Los arreglé
Anders Kaseorg

Respuestas:

5

[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.

// comment out TIMING if using external program timing mechanism
#define TIMING 1

// may need to increase if the source text has many unique words
#define MAX_LETTER_INSTANCES 1000000

// increase this if needing to output more top frequent words
#define MAX_TOP_FREQUENT_WORDS 1000

#define false 0
#define true 1
#define null 0

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef TIMING
#include <sys/time.h>
#endif

struct Letter
{
    char mostFrequentWord;
    struct Letter* parent;
    char asciiCode;
    unsigned int count;
    struct Letter* nextLetters[26];
};
typedef struct Letter Letter;

int main(int argc, char *argv[]) 
{
#ifdef TIMING
    struct timeval tv1, tv2;
    gettimeofday(&tv1, null);
#endif

    int k;
    if (argc !=3 || (k = atoi(argv[2])) <= 0 || k> MAX_TOP_FREQUENT_WORDS)
    {
        printf("Usage:\n");
        printf("      WordCount <input file path> <number of most frequent words to find>\n");
        printf("NOTE: upto %d most frequent words can be requested\n\n",MAX_TOP_FREQUENT_WORDS);
        return -1;
    }

    long  file_size;
    long dataLength;
    char* data;

    // read in file contents
    FILE *fptr;
    size_t read_s = 0;  
    fptr = fopen(argv[1], "rb");
    fseek(fptr, 0L, SEEK_END);
    dataLength = ftell(fptr);
    rewind(fptr);
    data = (char*)malloc((dataLength));
    read_s = fread(data, 1, dataLength, fptr);
    if (fptr) fclose(fptr);

    unsigned int chr;
    unsigned int i;

    // working memory of letters
    Letter* letters = (Letter*) malloc(sizeof(Letter) * MAX_LETTER_INSTANCES);
    memset(&letters[0], 0, sizeof( Letter) * MAX_LETTER_INSTANCES);

    // the index of the next unused letter
    unsigned int letterMasterIndex=0;

    // pesudo letter representing the starting point of any word
    Letter* root = &letters[letterMasterIndex++];

    // the current letter in the word being processed
    Letter* currentLetter = root;
    root->mostFrequentWord = false;
    root->count = 0;

    // the next letter to be processed
    Letter* nextLetter = null;

    // store of the top most frequent words
    Letter* topWords[MAX_TOP_FREQUENT_WORDS];

    // initialise the top most frequent words
    for (i = 0; i<k; i++)
    {
        topWords[i]=root;
    }

    unsigned int lowestWordCount = 0;
    unsigned int lowestWordIndex = 0;
    unsigned int highestWordCount = 0;
    unsigned int highestWordIndex = 0;

    // main loop
    for (int j=0;j<dataLength;j++)
    {
        chr = data[j]|0x20; // convert to lower case

        // is a letter?
        if (chr > 96 && chr < 123)
        {
            chr-=97; // translate to be zero indexed
            nextLetter = currentLetter->nextLetters[chr];

            // this is a new letter at this word length, intialise the new letter
            if (nextLetter == null)
            {
                nextLetter = &letters[letterMasterIndex++];
                nextLetter->parent = currentLetter;
                nextLetter->asciiCode = chr;
                currentLetter->nextLetters[chr] = nextLetter;
            }

            currentLetter = nextLetter;
        }
        // not a letter so this means the current letter is the last letter of a word (if any letters)
        else if (currentLetter!=root)
        {

            // increment the count of the full word that this letter represents
            ++currentLetter->count;

            // ignore this word if already identified as a most frequent word
            if (!currentLetter->mostFrequentWord)
            {
                // update the list of most frequent words
                // by replacing the most infrequent top word if this word is more frequent
                if (currentLetter->count> lowestWordCount)
                {
                    currentLetter->mostFrequentWord = true;
                    topWords[lowestWordIndex]->mostFrequentWord = false;
                    topWords[lowestWordIndex] = currentLetter;
                    lowestWordCount = currentLetter->count;

                    // update the index and count of the next most infrequent top word
                    for (i=0;i<k; i++)
                    {
                        // if the topword  is root then it can immediately be replaced by this current word, otherwise test
                        // whether the top word is less than the lowest word count
                        if (topWords[i]==root || topWords[i]->count<lowestWordCount)
                        {
                            lowestWordCount = topWords[i]->count;
                            lowestWordIndex = i;
                        }
                    }
                }
            }

            // reset the letter path representing the word
            currentLetter = root;
        }
    }

    // print out the top frequent words and counts
    char string[256];
    char tmp[256];

    while (k > 0 )
    {
        highestWordCount = 0;
        string[0]=0;
        tmp[0]=0;

        // find next most frequent word
        for (i=0;i<k; i++)
        {
            if (topWords[i]->count>highestWordCount)
            {
                highestWordCount = topWords[i]->count;
                highestWordIndex = i;
            }
        }

        Letter* letter = topWords[highestWordIndex];

        // swap the end top word with the found word and decrement the number of top words
        topWords[highestWordIndex] = topWords[--k];

        if (highestWordCount > 0)
        {
            // construct string of letters to form the word
            while (letter != root)
            {
                memmove(&tmp[1],&string[0],255);
                tmp[0]=letter->asciiCode+97;
                memmove(&string[0],&tmp[0],255);
                letter=letter->parent;
            }

            printf("%u %s\n",highestWordCount,string);
        }
    }

    free( data );
    free( letters );

#ifdef TIMING   
    gettimeofday(&tv2, null);
    printf("\nTime Taken: %f seconds\n", (double) (tv2.tv_usec - tv1.tv_usec)/1000000 + (double) (tv2.tv_sec - tv1.tv_sec));
#endif
    return 0;
}

Para la Prueba 1, y para las 10 palabras más frecuentes y con el tiempo habilitado, debe imprimir:

 968832 the
 528960 of
 466432 and
 421184 a
 322624 to
 320512 in
 270528 he
 213120 his
 191808 i
 182144 s

 Time Taken: 1.549155 seconds
Moogie
fuente
¡Impresionante! El uso de la lista supuestamente lo convierte en O (Nk) en el peor de los casos, por lo que se ejecuta más lentamente que el programa C ++ de referencia para giganovel con k = 100,000. Pero para k << N es un claro ganador.
Andriy Makukha
1
@AndriyMakukha ¡Gracias! Me sorprendió un poco que una implementación tan simple produjera una gran velocidad. Podría mejorarlo para valores mayores de k al ordenar la lista. (la clasificación no debería ser demasiado costosa ya que el orden de la lista cambiaría lentamente), pero eso agrega complejidad y probablemente afectaría la velocidad para valores más bajos de k. Tendrá que experimentar
Moogie
Sí, también me sorprendió. Puede deberse a que el programa de referencia utiliza muchas llamadas de función y el compilador no puede optimizarlo correctamente.
Andriy Makukha
Otro beneficio de rendimiento probablemente proviene de la asignación semiestática de la lettersmatriz, mientras que la implementación de referencia asigna nodos de árbol dinámicamente.
Andriy Makukha
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 con int 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);
NGN
4

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

use memmap::MmapOptions;
use pdqselect::select_by_key;
use std::cmp::Reverse;
use std::default::Default;
use std::env::args;
use std::fs::File;
use std::io::{self, Write};
use typed_arena::Arena;

#[derive(Default)]
struct Trie<'a> {
    nodes: [Option<&'a mut Trie<'a>>; 26],
    count: u64,
}

fn main() -> io::Result<()> {
    // Parse arguments
    let mut args = args();
    args.next().unwrap();
    let filename = args.next().unwrap();
    let size = args.next().unwrap().parse().unwrap();

    // Open input
    let file = File::open(filename)?;
    let mmap = unsafe { MmapOptions::new().map(&file)? };

    // Build trie
    let arena = Arena::new();
    let mut num_words = 0;
    let mut root = Trie::default();
    {
        let mut node = &mut root;
        for byte in &mmap[..] {
            let letter = (byte | 32).wrapping_sub(b'a');
            if let Some(child) = node.nodes.get_mut(letter as usize) {
                node = child.get_or_insert_with(|| {
                    num_words += 1;
                    arena.alloc(Default::default())
                });
            } else {
                node.count += 1;
                node = &mut root;
            }
        }
        node.count += 1;
    }

    // Extract all counts
    let mut index = 0;
    let mut counts = Vec::with_capacity(num_words);
    let mut stack = vec![root.nodes.iter()];
    'a: while let Some(frame) = stack.last_mut() {
        while let Some(child) = frame.next() {
            if let Some(child) = child {
                if child.count != 0 {
                    counts.push((child.count, index));
                    index += 1;
                }
                stack.push(child.nodes.iter());
                continue 'a;
            }
        }
        stack.pop();
    }

    // Find frequent counts
    select_by_key(&mut counts, size, |&(count, _)| Reverse(count));
    // Or, in nightly Rust:
    //counts.partition_at_index_by_key(size, |&(count, _)| Reverse(count));

    // Extract frequent words
    let size = size.min(counts.len());
    counts[0..size].sort_by_key(|&(_, index)| index);
    let mut out = Vec::with_capacity(size);
    let mut it = counts[0..size].iter();
    if let Some(mut next) = it.next() {
        index = 0;
        stack.push(root.nodes.iter());
        let mut word = vec![b'a' - 1];
        'b: while let Some(frame) = stack.last_mut() {
            while let Some(child) = frame.next() {
                *word.last_mut().unwrap() += 1;
                if let Some(child) = child {
                    if child.count != 0 {
                        if index == next.1 {
                            out.push((word.to_vec(), next.0));
                            if let Some(next1) = it.next() {
                                next = next1;
                            } else {
                                break 'b;
                            }
                        }
                        index += 1;
                    }
                    stack.push(child.nodes.iter());
                    word.push(b'a' - 1);
                    continue 'b;
                }
            }
            stack.pop();
            word.pop();
        }
    }
    out.sort_by_key(|&(_, count)| Reverse(count));

    // Print results
    let stdout = io::stdout();
    let mut stdout = io::BufWriter::new(stdout.lock());
    for (word, count) in out {
        stdout.write_all(&word)?;
        writeln!(stdout, " {}", count)?;
    }

    Ok(())
}

Cargo.toml

[package]
name = "frequent"
version = "0.1.0"
authors = ["Anders Kaseorg <[email protected]>"]
edition = "2018"

[dependencies]
memmap = "0.7.0"
typed-arena = "1.4.1"
pdqselect = "0.1.0"

[profile.release]
lto = true
opt-level = 3

Uso

cargo build --release
time target/release/frequent ulysses64 10
Anders Kaseorg
fuente
1
¡Soberbio! Muy buen rendimiento en las tres configuraciones. Estaba literalmente en medio de una charla reciente de Carol Nichols sobre Rust :) Sintaxis algo inusual, pero estoy emocionado de aprender el idioma: parece ser el único idioma de los idiomas del sistema post-C ++ que no funciona. sacrifica mucho rendimiento al tiempo que facilita la vida del desarrollador.
Andriy Makukha
¡Muy rápido! ¡estoy impresionado! Me pregunto si la mejor opción del compilador para C (árbol + bin) dará un resultado similar.
Moogie
@Moogie Ya estaba probando el tuyo -O3, y -Ofastno hace una diferencia apreciable.
Anders Kaseorg
@ Moogie, estaba compilando tu código como gcc -O3 -march=native -mtune=native program.c.
Andriy Makukha
@Andriy Makukha ah. Eso explicaría la gran diferencia de velocidad entre los resultados que obtiene frente a mis resultados: ya estaba aplicando indicadores de optimización. No creo que queden muchas optimizaciones de código grandes. No puedo probar usando el mapa como lo sugieren otros, ya que mingw dies no tiene una implementación ... Y solo daría un aumento del 5%. Creo que tendré que ceder ante la impresionante entrada de Anders. ¡Bien hecho!
Moogie
3

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:

⎕{m[⍺↑⍒⊢/m←{(⊂⎕UCS⊃⍺),≢⍵}⌸(⊢⊆⍨96∘<∧<∘123)83⎕DR 819⌶80 ¯1⎕MAP⍵;]}⍞

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 dyalogejecutable (para las diez palabras más frecuentes):

⎕{m[⍺↑⍒⊢/m←{(⊂⎕UCS⊃⍺),≢⍵}⌸(⊢⊆⍨96∘<∧<∘123)83⎕DR 819⌶80 ¯1⎕MAP⍵;]}⍞
/tmp/ulysses64
10
⎕OFF

Debería imprimir:

 the  968832
 of   528960
 and  466432
 a    421184
 to   322624
 in   320512
 he   270528
 his  213120
 i    191808
 s    182144
Adán
fuente
¡Muy agradable! Le gana a Python. Funcionó mejor después 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.
Andriy Makukha
@AndriyMakukha Sí, usa una tabla hash según esto , y estoy bastante seguro de que también lo hace internamente.
Adám
¿Por qué es O (N log N)? Se parece más a Python (k veces restaurando el montón de palabras únicas) o AWK (ordenando solo palabras únicas) para mí. A menos que ordene todas las palabras, como en el script de shell de McIlroy, no debería ser O (N log N).
Andriy Makukha
@AndriyMakukha It grados todos los cargos. Esto es lo que nuestro chico de rendimiento me escribió: la complejidad del tiempo es O (N log N), a menos que creas algunas cosas teóricamente dudosas sobre las tablas hash, en cuyo caso es O (N).
Adám
Bueno, cuando ejecuto su código contra 8, 16 y 32 Ulises, se ralentiza exactamente linealmente. Tal vez su chico de rendimiento necesite reconsiderar sus puntos de vista sobre la complejidad del tiempo de las tablas hash :) Además, este código no funciona para el caso de prueba más grande. Regresa WS FULL, aunque aumenté el espacio de trabajo a 6 GB.
Andriy Makukha
2

[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:

Worst Time complexity: O(1 + N + k)
Worst Space complexity: O(26*M + N + n) = O(M + N + n)

Where N is the number of words of the data
and M is the number of letters of the data
and n is the range of pigeon holes
and k is the desired number of sorted words to return
and N<=M

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.

// comment out TIMING if using external program timing mechanism
#define TIMING 1

// may need to increase if the source text has many unique words
#define MAX_LETTER_INSTANCES 1000000

// may need to increase if the source text has many repeated words
#define MAX_BINS 1000000

// assume maximum of 20 letters in a word... adjust accordingly
#define MAX_LETTERS_IN_A_WORD 20

// assume maximum of 10 letters for the string representation of the bin number... adjust accordingly
#define MAX_LETTERS_FOR_BIN_NAME 10

// maximum number of bytes of the output results
#define MAX_OUTPUT_SIZE 10000000

#define false 0
#define true 1
#define null 0
#define SPACE_ASCII_CODE 32

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef TIMING
#include <sys/time.h>
#endif

struct Letter
{
    //char isAWord;
    struct Letter* parent;
    struct Letter* binElementNext;
    char asciiCode;
    unsigned int count;
    struct Letter* nextLetters[26];
};
typedef struct Letter Letter;

struct Bin
{
  struct Letter* word;
};
typedef struct Bin Bin;


int main(int argc, char *argv[]) 
{
#ifdef TIMING
    struct timeval tv1, tv2;
    gettimeofday(&tv1, null);
#endif

    int k;
    if (argc !=3 || (k = atoi(argv[2])) <= 0)
    {
        printf("Usage:\n");
        printf("      WordCount <input file path> <number of most frequent words to find>\n\n");
        return -1;
    }

    long  file_size;
    long dataLength;
    char* data;

    // read in file contents
    FILE *fptr;
    size_t read_s = 0;  
    fptr = fopen(argv[1], "rb");
    fseek(fptr, 0L, SEEK_END);
    dataLength = ftell(fptr);
    rewind(fptr);
    data = (char*)malloc((dataLength));
    read_s = fread(data, 1, dataLength, fptr);
    if (fptr) fclose(fptr);

    unsigned int chr;
    unsigned int i, j;

    // working memory of letters
    Letter* letters = (Letter*) malloc(sizeof(Letter) * MAX_LETTER_INSTANCES);
    memset(&letters[0], null, sizeof( Letter) * MAX_LETTER_INSTANCES);

    // the memory for bins
    Bin* bins = (Bin*) malloc(sizeof(Bin) * MAX_BINS);
    memset(&bins[0], null, sizeof( Bin) * MAX_BINS);

    // the index of the next unused letter
    unsigned int letterMasterIndex=0;
    Letter *nextFreeLetter = &letters[0];

    // pesudo letter representing the starting point of any word
    Letter* root = &letters[letterMasterIndex++];

    // the current letter in the word being processed
    Letter* currentLetter = root;

    // the next letter to be processed
    Letter* nextLetter = null;

    unsigned int sortedListSize = 0;

    // the count of the most frequent word
    unsigned int maxCount = 0;

    // the count of the current word
    unsigned int wordCount = 0;

////////////////////////////////////////////////////////////////////////////////////////////
// CREATING PREFIX TREE
    j=dataLength;
    while (--j>0)
    {
        chr = data[j]|0x20; // convert to lower case

        // is a letter?
        if (chr > 96 && chr < 123)
        {
            chr-=97; // translate to be zero indexed
            nextLetter = currentLetter->nextLetters[chr];

            // this is a new letter at this word length, intialise the new letter
            if (nextLetter == null)
            {
                ++letterMasterIndex;
                nextLetter = ++nextFreeLetter;
                nextLetter->parent = currentLetter;
                nextLetter->asciiCode = chr;
                currentLetter->nextLetters[chr] = nextLetter;
            }

            currentLetter = nextLetter;
        }
        else
        {
            //currentLetter->isAWord = true;

            // increment the count of the full word that this letter represents
            ++currentLetter->count;

            // reset the letter path representing the word
            currentLetter = root;
        }
    }

////////////////////////////////////////////////////////////////////////////////////////////
// ADDING TO BINS

    j = letterMasterIndex;
    currentLetter=&letters[j-1];
    while (--j>0)
    {

      // is the letter the leaf letter of word?
      if (currentLetter->count>0)
      {
        i = currentLetter->count;
        if (maxCount < i) maxCount = i;

        // add to bin
        currentLetter->binElementNext = bins[i].word;
        bins[i].word = currentLetter;
      }
      --currentLetter;
    }

////////////////////////////////////////////////////////////////////////////////////////////
// PRINTING OUTPUT

    // the memory for output
    char* output = (char*) malloc(sizeof(char) * MAX_OUTPUT_SIZE);
    memset(&output[0], SPACE_ASCII_CODE, sizeof( char) * MAX_OUTPUT_SIZE);
    unsigned int outputIndex = 0;

    // string representation of the current bin number
    char binName[MAX_LETTERS_FOR_BIN_NAME];
    memset(&binName[0], SPACE_ASCII_CODE, MAX_LETTERS_FOR_BIN_NAME);


    Letter* letter;
    Letter* binElement;

    // starting at the bin representing the most frequent word(s) and then iterating backwards...
    for ( i=maxCount;i>0 && k>0;i--)
    {
      // check to ensure that the bin has at least one word
      if ((binElement = bins[i].word) != null)
      {
        // update the bin name
        sprintf(binName,"%u",i);

        // iterate of the words in the bin
        while (binElement !=null && k>0)
        {
          // stop if we have reached the desired number of outputed words
          if (k-- > 0)
          {
              letter = binElement;

              // add the bin name to the output
              memcpy(&output[outputIndex],&binName[0],MAX_LETTERS_FOR_BIN_NAME);
              outputIndex+=MAX_LETTERS_FOR_BIN_NAME;

              // construct string of letters to form the word
               while (letter != root)
              {
                // output the letter to the output
                output[outputIndex++] = letter->asciiCode+97;
                letter=letter->parent;
              }

              output[outputIndex++] = '\n';

              // go to the next word in the bin
              binElement = binElement->binElementNext;
          }
        }
      }
    }

    // write the output to std out
    fwrite(output, 1, outputIndex, stdout);
   // fflush(stdout);

   // free( data );
   // free( letters );
   // free( bins );
   // free( output );

#ifdef TIMING   
    gettimeofday(&tv2, null);
    printf("\nTime Taken: %f seconds\n", (double) (tv2.tv_usec - tv1.tv_usec)/1000000 + (double) (tv2.tv_sec - tv1.tv_sec));
#endif
    return 0;
}

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.

Moogie
fuente
¡Guauu! 100,000 palabras más frecuentes de un archivo de 1 GB en 11 segundos ... Esto parece una especie de truco de magia.
Andriy Makukha
Sin trucos ... Simplemente intercambiando tiempo de CPU por un uso eficiente de la memoria. Estoy sorprendido por su resultado ... En mi PC anterior, lleva más de 60 segundos. Me di cuenta de que estoy haciendo comparaciones innecesarias y puedo diferir el binning hasta que el archivo haya sido procesado. Debería hacerlo aún más rápido. Lo intentaré pronto y actualizaré mi respuesta.
Moogie
@AndriyMakukha Ahora he aplazado llenar los contenedores hasta que se hayan procesado todas las palabras y se haya construido el árbol. Esto evita comparaciones innecesarias y manipulación de elementos bin. ¡También cambié la forma en que se construye la salida ya que descubrí que la impresión tomaba una cantidad significativa de tiempo!
Moogie
En mi máquina, esta actualización no hace ninguna diferencia notable. Sin embargo, funcionó muy rápido ulysses64una vez, por lo que ahora es un líder actual.
Andriy Makukha
Debe ser un problema único con mi PC entonces :) Noté una velocidad de 5 segundos al usar este nuevo algoritmo de salida
Moogie
2

J

9!:37 ] 0 _ _ _

'input k' =: _2 {. ARGV
k =: ". k

lower =: a. {~ 97 + i. 26
words =: ((lower , ' ') {~ lower i. ]) (32&OR)&.(a.&i.) fread input
words =: ' ' , words
words =: -.&(s: a:) s: words
uniq =: ~. words
res =: (k <. # uniq) {. \:~ (# , {.)/.~ uniq&i. words
echo@(,&": ' ' , [: }.@": {&uniq)/"1 res

exit 0

Ejecutar como un script con jconsole <script> <input> <k>. Por ejemplo, la salida de giganovelcon k=100K:

$ time jconsole solve.ijs giganovel 100000 | head 
11309 e
11290 ihit
11285 ah
11260 ist
11255 aa
11202 aiv
11201 al
11188 an
11187 o
11186 ansa

real    0m13.765s
user    0m11.872s
sys     0m1.786s

No hay límite, excepto por la cantidad de memoria disponible del sistema.

millas
fuente
¡Muy rápido para el caso de prueba más pequeño! ¡Agradable! Sin embargo, para palabras arbitrariamente grandes, trunca las palabras en la salida. No estoy seguro de si hay un límite en el número de caracteres en una palabra o si es solo para hacer que la salida sea más concisa.
Andriy Makukha
@AndriyMakukha Sí, esto ...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.
millas
¡Excelente! Ahora pasa la prueba de generalidad. Y no se ralentizó en mi máquina. De hecho, hubo una aceleración menor.
Andriy Makukha
2

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}"):

#include <iostream>
#include <cassert>

// Adjust these parameters based on input size.
const int TRIE_SIZE = 800 * 1000; // Size of the hash table used for the trie.
const int ALPHA = 494441;  // An integer that's approximately (0.61803 * TRIE_SIZE), and relatively prime to T = TRIE_SIZE - 52.
const int kTolerance = TRIE_SIZE / 100;  // How many places to try, to find a new place for a "family" (=bunch of children).

typedef int32_t Pointer;  // [0..TRIE_SIZE), an index into the array of Nodes
typedef int8_t Char;  // We only care about 1..26 (plus two values), but there's no "int5_t".
typedef int32_t Count;  // The number of times a word has been encountered.
// These are 4 separate arrays in Knuth's implementation.
struct Node {
  Pointer link;  // From a parent node to its children's "header", or from a header back to parent.
  Pointer sibling;  // Previous sibling, cyclically. (From smallest child to header, and header to largest child.)
  Count count;  // The number of times this word has been encountered.
  Char ch;  // EMPTY, or 1..26, or HEADER. (For nodes with ch=EMPTY, the link/sibling/count fields mean nothing.)
} node[TRIE_SIZE + 1];
// Special values for `ch`: EMPTY (free, can insert child there) and HEADER (start of family).
const Char EMPTY = 0, HEADER = 27;

const Pointer T = TRIE_SIZE - 52;
Pointer x;  // The `n`th time we need a node, we'll start trying at x_n = (alpha * n) mod T. This holds current `x_n`.
// A header can only be in T (=TRIE_SIZE-52) positions namely [27..TRIE_SIZE-26].
// This transforms a "h" from range [0..T) to the above range namely [27..T+27).
Pointer rerange(Pointer n) {
  n = (n % T) + 27;
  // assert(27 <= n && n <= TRIE_SIZE - 26);
  return n;
}

// Convert trie node to string, by walking up the trie.
std::string word_for(Pointer p) {
  std::string word;
  while (p != 0) {
    Char c = node[p].ch;  // assert(1 <= c && c <= 26);
    word = static_cast<char>('a' - 1 + c) + word;
    // assert(node[p - c].ch == HEADER);
    p = (p - c) ? node[p - c].link : 0;
  }
  return word;
}

// Increment `x`, and declare `h` (the first position to try) and `last_h` (the last position to try). {§24}
#define PREPARE_X_H_LAST_H x = (x + ALPHA) % T; Pointer h = rerange(x); Pointer last_h = rerange(x + kTolerance);
// Increment `h`, being careful to account for `last_h` and wraparound. {§25}
#define INCR_H { if (h == last_h) { std::cerr << "Hit tolerance limit unfortunately" << std::endl; exit(1); } h = (h == TRIE_SIZE - 26) ? 27 : h + 1; }

// `p` has no children. Create `p`s family of children, with only child `c`. {§27}
Pointer create_child(Pointer p, int8_t c) {
  // Find `h` such that there's room for both header and child c.
  PREPARE_X_H_LAST_H;
  while (!(node[h].ch == EMPTY and node[h + c].ch == EMPTY)) INCR_H;
  // Now create the family, with header at h and child at h + c.
  node[h]     = {.link = p, .sibling = h + c, .count = 0, .ch = HEADER};
  node[h + c] = {.link = 0, .sibling = h,     .count = 0, .ch = c};
  node[p].link = h;
  return h + c;
}

// Move `p`'s family of children to a place where child `c` will also fit. {§29}
void move_family_for(const Pointer p, Char c) {
  // Part 1: Find such a place: need room for `c` and also all existing children. {§31}
  PREPARE_X_H_LAST_H;
  while (true) {
    INCR_H;
    if (node[h + c].ch != EMPTY) continue;
    Pointer r = node[p].link;
    int delta = h - r;  // We'd like to move each child by `delta`
    while (node[r + delta].ch == EMPTY and node[r].sibling != node[p].link) {
      r = node[r].sibling;
    }
    if (node[r + delta].ch == EMPTY) break;  // There's now space for everyone.
  }

  // Part 2: Now actually move the whole family to start at the new `h`.
  Pointer r = node[p].link;
  int delta = h - r;
  do {
    Pointer sibling = node[r].sibling;
    // Move node from current position (r) to new position (r + delta), and free up old position (r).
    node[r + delta] = {.ch = node[r].ch, .count = node[r].count, .link = node[r].link, .sibling = node[r].sibling + delta};
    if (node[r].link != 0) node[node[r].link].link = r + delta;
    node[r].ch = EMPTY;
    r = sibling;
  } while (node[r].ch != EMPTY);
}

// Advance `p` to its `c`th child. If necessary, add the child, or even move `p`'s family. {§21}
Pointer find_child(Pointer p, Char c) {
  // assert(1 <= c && c <= 26);
  if (p == 0) return c;  // Special case for first char.
  if (node[p].link == 0) return create_child(p, c);  // If `p` currently has *no* children.
  Pointer q = node[p].link + c;
  if (node[q].ch == c) return q;  // Easiest case: `p` already has a `c`th child.
  // Make sure we have room to insert a `c`th child for `p`, by moving its family if necessary.
  if (node[q].ch != EMPTY) {
    move_family_for(p, c);
    q = node[p].link + c;
  }
  // Insert child `c` into `p`'s family of children (at `q`), with correct siblings. {§28}
  Pointer h = node[p].link;
  while (node[h].sibling > q) h = node[h].sibling;
  node[q] = {.ch = c, .count = 0, .link = 0, .sibling = node[h].sibling};
  node[h].sibling = q;
  return q;
}

// Largest descendant. {§18}
Pointer last_suffix(Pointer p) {
  while (node[p].link != 0) p = node[node[p].link].sibling;
  return p;
}

// The largest count beyond which we'll put all words in the same (last) bucket.
// We do an insertion sort (potentially slow) in last bucket, so increase this if the program takes a long time to walk trie.
const int MAX_BUCKET = 10000;
Pointer sorted[MAX_BUCKET + 1];  // The head of each list.

// Records the count `n` of `p`, by inserting `p` in the list that starts at `sorted[n]`.
// Overwrites the value of node[p].sibling (uses the field to mean its successor in the `sorted` list).
void record_count(Pointer p) {
  // assert(node[p].ch != HEADER);
  // assert(node[p].ch != EMPTY);
  Count f = node[p].count;
  if (f == 0) return;
  if (f < MAX_BUCKET) {
    // Insert at head of list.
    node[p].sibling = sorted[f];
    sorted[f] = p;
  } else {
    Pointer r = sorted[MAX_BUCKET];
    if (node[p].count >= node[r].count) {
      // Insert at head of list
      node[p].sibling = r;
      sorted[MAX_BUCKET] = p;
    } else {
      // Find right place by count. This step can be SLOW if there are too many words with count >= MAX_BUCKET
      while (node[p].count < node[node[r].sibling].count) r = node[r].sibling;
      node[p].sibling = node[r].sibling;
      node[r].sibling = p;
    }
  }
}

// Walk the trie, going over all words in reverse-alphabetical order. {§37}
// Calls "record_count" for each word found.
void walk_trie() {
  // assert(node[0].ch == HEADER);
  Pointer p = node[0].sibling;
  while (p != 0) {
    Pointer q = node[p].sibling;  // Saving this, as `record_count(p)` will overwrite it.
    record_count(p);
    // Move down to last descendant of `q` if any, else up to parent of `q`.
    p = (node[q].ch == HEADER) ? node[q].link : last_suffix(q);
  }
}

int main(int, char** argv) {
  // Program startup
  std::ios::sync_with_stdio(false);

  // Set initial values {§19}
  for (Char i = 1; i <= 26; ++i) node[i] = {.ch = i, .count = 0, .link = 0, .sibling = i - 1};
  node[0] = {.ch = HEADER, .count = 0, .link = 0, .sibling = 26};

  // read in file contents
  FILE *fptr = fopen(argv[1], "rb");
  fseek(fptr, 0L, SEEK_END);
  long dataLength = ftell(fptr);
  rewind(fptr);
  char* data = (char*)malloc(dataLength);
  fread(data, 1, dataLength, fptr);
  if (fptr) fclose(fptr);

  // Loop over file contents: the bulk of the time is spent here.
  Pointer p = 0;
  for (int i = 0; i < dataLength; ++i) {
    Char c = (data[i] | 32) - 'a' + 1;  // 1 to 26, for 'a' to 'z' or 'A' to 'Z'
    if (1 <= c && c <= 26) {
      p = find_child(p, c);
    } else {
      ++node[p].count;
      p = 0;
    }
  }
  node[0].count = 0;

  walk_trie();

  const int max_words_to_print = atoi(argv[2]);
  int num_printed = 0;
  for (Count f = MAX_BUCKET; f >= 0 && num_printed <= max_words_to_print; --f) {
    for (Pointer p = sorted[f]; p != 0 && num_printed < max_words_to_print; p = node[p].sibling) {
      std::cout << word_for(p) << " " << node[p].count << std::endl;
      ++num_printed;
    }
  }

  return 0;
}

Diferencias con el programa de Knuth:

  • Combiné 4 matrices de Knuth link, sibling, county chen una matriz de un struct Node(resulta más fácil de entender de esta manera).
  • Cambié la transclusión textual de secciones de programación alfabetizada (estilo WEB) en llamadas a funciones más convencionales (y un par de macros).
  • No necesitamos usar las convenciones / restricciones extrañas de E / S estándar de Pascal, por lo tanto, use fready data[i] | 32 - 'a'como en las otras respuestas aquí, en lugar de la solución alternativa de Pascal.
  • En caso de que excedamos los límites (sin espacio) mientras el programa se está ejecutando, el programa original de Knuth lo trata con gracia al soltar las palabras posteriores e imprimir un mensaje al final. (No es correcto decir que McIlroy "criticó la solución de Knuth porque ni siquiera podía procesar un texto completo de la Biblia"; solo estaba señalando que a veces pueden aparecer palabras frecuentes muy tarde en un texto, como la palabra "Jesús "en la Biblia, por lo que la condición de error no es inocuo.) He tomado el enfoque más ruidoso (y de todos modos más fácil) de simplemente terminar el programa.
  • El programa declara un TRIE_SIZE constante para controlar el uso de la memoria, que incrementé. (La constante de 32767 había sido elegida para los requisitos originales: "un usuario debería poder encontrar las 100 palabras más frecuentes en un documento técnico de veinte páginas (aproximadamente un archivo de 50K bytes)" y porque Pascal trata bien con el entero a rango los escribe y los empaqueta de manera óptima. Tuvimos que aumentarlo 25x a 800,000 ya que la entrada de prueba ahora es 20 millones de veces más grande).
  • Para la impresión final de las cadenas, podemos caminar por el trie y hacer un agregado de cadena tonto (posiblemente incluso cuadrático).

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

clang++ -std=c++17 -O2 ptrie-walktrie.cc 

Cuando se ejecuta en el caso de prueba más grande aquí ( giganovelcon 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:

target/release/frequent:   4.809 ±   0.263 [ 4.45.. 5.62]        [... 4.63 ...  4.75 ...  4.88...]
ptrie-walktrie:            4.547 ±   0.164 [ 4.35.. 4.99]        [... 4.42 ...   4.5 ...  4.68...]

(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 :

Una llama sobre punteros de 64 bits

Es absolutamente idiota tener punteros de 64 bits cuando compilo un programa que usa menos de 4 gigabytes de RAM. Cuando tales valores de puntero aparecen dentro de una estructura, no solo desperdician la mitad de la memoria, sino que también desechan la mitad de la memoria caché.

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 (activado giganovel). 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.

#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>

typedef int32_t Pointer;  // [0..node.size()), an index into the array of Nodes
typedef int32_t Count;
typedef int8_t Char;  // We'll usually just have 1 to 26.
struct Node {
  Pointer link;  // From a parent node to its children's "header", or from a header back to parent.
  Count count;  // The number of times this word has been encountered. Undefined for header nodes.
};
std::vector<Node> node; // Our "arena" for Node allocation.

std::string word_for(Pointer p) {
  std::vector<char> drow;  // The word backwards
  while (p != 0) {
    Char c = p % 27;
    drow.push_back('a' - 1 + c);
    p = (p - c) ? node[p - c].link : 0;
  }
  return std::string(drow.rbegin(), drow.rend());
}

// `p` has no children. Create `p`s family of children, with only child `c`.
Pointer create_child(Pointer p, Char c) {
  Pointer h = node.size();
  node.resize(node.size() + 27);
  node[h] = {.link = p, .count = -1};
  node[p].link = h;
  return h + c;
}

// Advance `p` to its `c`th child. If necessary, add the child.
Pointer find_child(Pointer p, Char c) {
  assert(1 <= c && c <= 26);
  if (p == 0) return c;  // Special case for first char.
  if (node[p].link == 0) return create_child(p, c);  // Case 1: `p` currently has *no* children.
  return node[p].link + c;  // Case 2 (easiest case): Already have the child c.
}

int main(int, char** argv) {
  auto start_c = std::clock();

  // Program startup
  std::ios::sync_with_stdio(false);

  // read in file contents
  FILE *fptr = fopen(argv[1], "rb");
  fseek(fptr, 0, SEEK_END);
  long dataLength = ftell(fptr);
  rewind(fptr);
  char* data = (char*)malloc(dataLength);
  fread(data, 1, dataLength, fptr);
  fclose(fptr);

  node.reserve(dataLength / 600);  // Heuristic based on test data. OK to be wrong.
  node.push_back({0, 0});
  for (Char i = 1; i <= 26; ++i) node.push_back({0, 0});

  // Loop over file contents: the bulk of the time is spent here.
  Pointer p = 0;
  for (long i = 0; i < dataLength; ++i) {
    Char c = (data[i] | 32) - 'a' + 1;  // 1 to 26, for 'a' to 'z' or 'A' to 'Z'
    if (1 <= c && c <= 26) {
      p = find_child(p, c);
    } else {
      ++node[p].count;
      p = 0;
    }
  }
  ++node[p].count;
  node[0].count = 0;

  // Brute-force: Accumulate all words and their counts, then sort by frequency and print.
  std::vector<std::pair<int, std::string>> counts_words;
  for (Pointer i = 1; i < static_cast<Pointer>(node.size()); ++i) {
    int count = node[i].count;
    if (count == 0 || i % 27 == 0) continue;
    counts_words.push_back({count, word_for(i)});
  }
  auto cmp = [](auto x, auto y) {
    if (x.first != y.first) return x.first > y.first;
    return x.second < y.second;
  };
  std::sort(counts_words.begin(), counts_words.end(), cmp);
  const int max_words_to_print = std::min<int>(counts_words.size(), atoi(argv[2]));
  for (int i = 0; i < max_words_to_print; ++i) {
    auto [count, word] = counts_words[i];
    std::cout << word << " " << count << std::endl;
  }

  return 0;
}

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:

target/release/frequent:   4.809 ±   0.263 [ 4.45.. 5.62]        [... 4.63 ...  4.75 ...  4.88...]
ptrie-walktrie:            4.547 ±   0.164 [ 4.35.. 4.99]        [... 4.42 ...   4.5 ...  4.68...]
itrie-nolimit:             3.907 ±   0.127 [ 3.69.. 4.23]        [... 3.81 ...   3.9 ...   4.0...]

Estaría ansioso por ver qué le gustaría a este (o al programa hash-trie) si se tradujera a Rust . :-)

Más detalles

  1. 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 .

  2. 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.

  3. 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. :-)

ShreevatsaR
fuente
¡Increíble! No solo alguien finalmente publicó la solución de Knuth (tenía la intención de hacerlo, sino en Pascal) con un gran análisis y rendimiento que supera algunos de los mejores anuncios anteriores, ¡sino que también estableció un nuevo récord de velocidad con otro programa de C ++! Maravilloso.
Andriy Makukha
Los únicos dos comentarios que tengo: 1) su segundo programa actualmente falla Segmentation fault: 11para 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.
Andriy Makukha
@AndriyMakukha Oh, vaya, eso fue lo recursivo 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")
ShreevatsaR
¡Trabajos! Felicidades al nuevo rey :-P En cuanto a Unix y Knuth, no parecía gustarle mucho el sistema, porque había y hay poca unidad entre diferentes herramientas (por ejemplo, muchas herramientas definen expresiones regulares de manera diferente).
Andriy Makukha hace
1

Python 3

Esta implementación con un diccionario simple es ligeramente más rápida que la que usa Counteruno en mi sistema.

def words_from_file(filename):
    import re

    pattern = re.compile('[a-z]+')

    for line in open(filename):
        yield from pattern.findall(line.lower())


def freq(textfile, k):
    frequencies = {}

    for word in words_from_file(textfile):
        frequencies[word] = frequencies.get(word, 0) + 1

    most_frequent = sorted(frequencies.items(), key=lambda item: item[1], reverse=True)

    for i, (word, frequency) in enumerate(most_frequent):
        if i == k:
            break

        yield word, frequency


from time import time

start = time()
print('\n'.join('{}:\t{}'.format(f, w) for w,f in freq('giganovel', 10)))
end = time()
print(end - start)
movatica
fuente
1
Solo pude probar con giganovel en mi sistema, y ​​me lleva bastante tiempo (~ 90 segundos). gutenbergproject está bloqueado en Alemania por razones legales ...
movatica
Interesante. O heapqno agrega ningún rendimiento al Counter.most_commonmétodo, o enumerate(sorted(...))también lo usa heapqinternamente.
Andriy Makukha
Probé con Python 2 y el rendimiento fue similar, así que supongo que la clasificación funciona tan rápido como Counter.most_common .
Andriy Makukha
Sí, tal vez solo estaba nervioso en mi sistema ... Al menos no es más lento :) Pero la búsqueda de expresiones regulares es mucho más rápida que iterar sobre los caracteres. Parece que se implementa bastante bien.
movatica
1

[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.

// comment out TIMING if using external program timing mechanism
#define TIMING 1

// may need to increase if the source text has many unique words
#define MAX_LETTER_INSTANCES 1000000

#define false 0
#define true 1
#define null 0

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef TIMING
#include <sys/time.h>
#endif

struct Letter
{
    char isTopWord;
    struct Letter* parent;
    struct Letter* higher;
    struct Letter* lower;
    char asciiCode;
    unsigned int count;
    struct Letter* nextLetters[26];
};
typedef struct Letter Letter;

int main(int argc, char *argv[]) 
{
#ifdef TIMING
    struct timeval tv1, tv2;
    gettimeofday(&tv1, null);
#endif

    int k;
    if (argc !=3 || (k = atoi(argv[2])) <= 0)
    {
        printf("Usage:\n");
        printf("      WordCount <input file path> <number of most frequent words to find>\n\n");
        return -1;
    }

    long  file_size;
    long dataLength;
    char* data;

    // read in file contents
    FILE *fptr;
    size_t read_s = 0;  
    fptr = fopen(argv[1], "rb");
    fseek(fptr, 0L, SEEK_END);
    dataLength = ftell(fptr);
    rewind(fptr);
    data = (char*)malloc((dataLength));
    read_s = fread(data, 1, dataLength, fptr);
    if (fptr) fclose(fptr);

    unsigned int chr;
    unsigned int i;

    // working memory of letters
    Letter* letters = (Letter*) malloc(sizeof(Letter) * MAX_LETTER_INSTANCES);
    memset(&letters[0], 0, sizeof( Letter) * MAX_LETTER_INSTANCES);

    // the index of the next unused letter
    unsigned int letterMasterIndex=0;

    // pesudo letter representing the starting point of any word
    Letter* root = &letters[letterMasterIndex++];

    // the current letter in the word being processed
    Letter* currentLetter = root;

    // the next letter to be processed
    Letter* nextLetter = null;
    Letter* sortedWordsStart = null;
    Letter* sortedWordsEnd = null;
    Letter* A;
    Letter* B;
    Letter* C;
    Letter* D;

    unsigned int sortedListSize = 0;


    unsigned int lowestWordCount = 0;
    unsigned int lowestWordIndex = 0;
    unsigned int highestWordCount = 0;
    unsigned int highestWordIndex = 0;

    // main loop
    for (int j=0;j<dataLength;j++)
    {
        chr = data[j]|0x20; // convert to lower case

        // is a letter?
        if (chr > 96 && chr < 123)
        {
            chr-=97; // translate to be zero indexed
            nextLetter = currentLetter->nextLetters[chr];

            // this is a new letter at this word length, intialise the new letter
            if (nextLetter == null)
            {
                nextLetter = &letters[letterMasterIndex++];
                nextLetter->parent = currentLetter;
                nextLetter->asciiCode = chr;
                currentLetter->nextLetters[chr] = nextLetter;
            }

            currentLetter = nextLetter;
        }
        // not a letter so this means the current letter is the last letter of a word (if any letters)
        else if (currentLetter!=root)
        {

            // increment the count of the full word that this letter represents
            ++currentLetter->count;

            // is this word not in the top word list?
            if (!currentLetter->isTopWord)
            {
                // first word becomes the sorted list
                if (sortedWordsStart == null)
                {
                  sortedWordsStart = currentLetter;
                  sortedWordsEnd = currentLetter;
                  currentLetter->isTopWord = true;
                  ++sortedListSize;
                }
                // always add words until list is at desired size, or 
                // swap the current word with the end of the sorted word list if current word count is larger
                else if (sortedListSize < k || currentLetter->count> sortedWordsEnd->count)
                {
                    // replace sortedWordsEnd entry with current word
                    if (sortedListSize == k)
                    {
                      currentLetter->higher = sortedWordsEnd->higher;
                      currentLetter->higher->lower = currentLetter;
                      sortedWordsEnd->isTopWord = false;
                    }
                    // add current word to the sorted list as the sortedWordsEnd entry
                    else
                    {
                      ++sortedListSize;
                      sortedWordsEnd->lower = currentLetter;
                      currentLetter->higher = sortedWordsEnd;
                    }

                    currentLetter->lower = null;
                    sortedWordsEnd = currentLetter;
                    currentLetter->isTopWord = true;
                }
            }
            // word is in top list
            else
            {
                // check to see whether the current word count is greater than the supposedly next highest word in the list
                // we ignore the word that is sortedWordsStart (i.e. most frequent)
                while (currentLetter != sortedWordsStart && currentLetter->count> currentLetter->higher->count)
                {
                    B = currentLetter->higher;
                    C = currentLetter;
                    A = B != null ? currentLetter->higher->higher : null;
                    D = currentLetter->lower;

                    if (A !=null) A->lower = C;
                    if (D !=null) D->higher = B;
                    B->higher = C;
                    C->higher = A;
                    B->lower = D;
                    C->lower = B;

                    if (B == sortedWordsStart)
                    {
                      sortedWordsStart = C;
                    }

                    if (C == sortedWordsEnd)
                    {
                      sortedWordsEnd = B;
                    }
                }
            }

            // reset the letter path representing the word
            currentLetter = root;
        }
    }

    // print out the top frequent words and counts
    char string[256];
    char tmp[256];

    Letter* letter;
    while (sortedWordsStart != null )
    {
        letter = sortedWordsStart;
        highestWordCount = letter->count;
        string[0]=0;
        tmp[0]=0;

        if (highestWordCount > 0)
        {
            // construct string of letters to form the word
            while (letter != root)
            {
                memmove(&tmp[1],&string[0],255);
                tmp[0]=letter->asciiCode+97;
                memmove(&string[0],&tmp[0],255);
                letter=letter->parent;
            }

            printf("%u %s\n",highestWordCount,string);
        }
        sortedWordsStart = sortedWordsStart->lower;
    }

    free( data );
    free( letters );

#ifdef TIMING   
    gettimeofday(&tv2, null);
    printf("\nTime Taken: %f seconds\n", (double) (tv2.tv_usec - tv1.tv_usec)/1000000 + (double) (tv2.tv_sec - tv1.tv_sec));
#endif
    return 0;
}
Moogie
fuente
No devuelve muy salida para k = 100.000 ordenadas: 12 eroilk 111 iennoa 10 yttelen 110 engyt.
Andriy Makukha
Creo que tengo una idea de la razón. Mi pensamiento es que tendré que repetir las palabras de intercambio en la lista cuando verifique si la siguiente palabra más alta de la palabra actual. Cuando tenga tiempo lo comprobaré
Moogie
hmm bueno, parece que la solución simple de cambiar un if a while funciona, sin embargo, también ralentiza significativamente el algoritmo para valores mayores de k. Puede que tenga que pensar en una solución más inteligente.
Moogie
1

C#

Este debería funcionar con los últimos SDK de .net .

using System;
using System.IO;
using System.Diagnostics;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Node {
    public Node Parent;
    public Node[] Nodes;
    public int Index;
    public int Count;

    public static readonly List<Node> AllNodes = new List<Node>();

    public Node(Node parent, int index) {
        this.Parent = parent;
        this.Index = index;
        AllNodes.Add(this);
    }

    public Node Traverse(uint u) {
        int b = (int)u;
        if (this.Nodes is null) {
            this.Nodes = new Node[26];
            return this.Nodes[b] = new Node(this, b);
        }
        if (this.Nodes[b] is null) return this.Nodes[b] = new Node(this, b);
        return this.Nodes[b];
    }

    public string GetWord() => this.Index >= 0 
        ? this.Parent.GetWord() + (char)(this.Index + 97)
        : "";
}

class Freq {
    const int DefaultBufferSize = 0x10000;

    public static void Main(string[] args) {
        var sw = Stopwatch.StartNew();

        if (args.Length < 2) {
            WriteLine("Usage: freq.exe {filename} {k} [{buffersize}]");
            return;
        }

        string file = args[0];
        int k = int.Parse(args[1]);
        int bufferSize = args.Length >= 3 ? int.Parse(args[2]) : DefaultBufferSize;

        Node root = new Node(null, -1) { Nodes = new Node[26] }, current = root;
        int b;
        uint u;

        using (var fr = new FileStream(file, FileMode.Open))
        using (var br = new BufferedStream(fr, bufferSize)) {
            outword:
                b = br.ReadByte() | 32;
                if ((u = (uint)(b - 97)) >= 26) {
                    if (b == -1) goto done; 
                    else goto outword;
                }
                else current = root.Traverse(u);
            inword:
                b = br.ReadByte() | 32;
                if ((u = (uint)(b - 97)) >= 26) {
                    if (b == -1) goto done;
                    ++current.Count;
                    goto outword;
                }
                else {
                    current = current.Traverse(u);
                    goto inword;
                }
            done:;
        }

        WriteLine(string.Join("\n", Node.AllNodes
            .OrderByDescending(count => count.Count)
            .Take(k)
            .Select(node => node.GetWord())));

        WriteLine("Self-measured milliseconds: {0}", sw.ElapsedMilliseconds);
    }
}

Aquí hay una muestra de salida.

C:\dev\freq>csc -o -nologo freq-trie.cs && freq-trie.exe giganovel 100000
e
ihit
ah
ist
 [... omitted for sanity ...]
omaah
aanhele
okaistai
akaanio
Self-measured milliseconds: 13619

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.

recursivo
fuente
1
¡Muy impresionante! Me gustan tus tolowertrucos 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.
Andriy Makukha
@AndriyMakukha: Puedo ver que también estoy contando prefijos de palabras que nunca ocurrieron en el conteo final. Evité escribir toda la salida porque la salida de la consola es bastante lenta en Windows. ¿Puedo escribir la salida en un archivo?
recursivo
Simplemente imprímalo salida estándar, por favor. Para k = 10, debería ser rápido en cualquier máquina. También puede redirigir la salida a un archivo desde una línea de comando. Me gusta esto .
Andriy Makukha
@AndriyMakukha: Creo que he abordado todos los problemas. Encontré una manera de producir toda la salida requerida sin mucho costo de tiempo de ejecución.
recursivo
¡Esta salida es increíblemente rápida! Muy agradable. Modifiqué su programa para imprimir también conteos de frecuencia, como lo hacen otras soluciones.
Andriy Makukha
1

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 :

Enumerable#tallyestá agregado. Cuenta la ocurrencia de cada elemento.

["a", "b", "c", "b"].tally
#=> {"a"=>1, "b"=>2, "c"=>1}

Esto casi resuelve toda la tarea para nosotros. Solo necesitamos leer el archivo primero y encontrar el máximo después.

Aquí está todo:

k = ARGV.shift.to_i

pp ARGF
  .each_line
  .lazy
  .flat_map { @1.scan(/[A-Za-z]+/).map(&:downcase) }
  .tally
  .max_by(k, &:last)

editar: agregado kcomo argumento de línea de comando

Se puede ejecutar con ruby k filename.rb input.txtla 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 usando rbenv install 2.7.0-dev.

Ejemplo ejecutado en mi propia computadora vieja y destartalada:

$ time ruby bentley.rb 10 ulysses64 
[["the", 968832],
 ["of", 528960],
 ["and", 466432],
 ["a", 421184],
 ["to", 322624],
 ["in", 320512],
 ["he", 270528],
 ["his", 213120],
 ["i", 191808],
 ["s", 182144]]

real    0m17.884s
user    0m17.720s
sys 0m0.142s
daniero
fuente
1
Instalé Ruby desde las fuentes. Funciona aproximadamente tan rápido como en su máquina (15 segundos frente a 17).
Andriy Makukha