Jest to być może jedno z klasycznych wyzwań związanych z kodowaniem, które zyskało pewien rezonans w 1986 r., Kiedy felietonista Jon Bentley poprosił Donalda Knutha o napisanie programu, który znalazłby k najczęściej występujących słów w pliku. Knuth zaimplementował szybkie rozwiązanie za pomocą prób skrótu w 8-stronicowym programie, aby zilustrować swoją umiejętność programowania. Douglas McIlroy z Bell Labs skrytykował rozwiązanie Knutha jako nawet niezdolnego do przetworzenia pełnego tekstu Biblii i odpowiedział jednokierunkowym tekstem, który nie jest tak szybki, ale wykonuje zadanie:

tr -cs A-Za-z '\n' | tr A-Z a-z | sort | uniq -c | sort -rn | sed 10q

W 1987 r. Opublikowano artykuł uzupełniający z jeszcze innym rozwiązaniem, tym razem autorstwa profesora z Princeton. Ale nie mogło nawet zwrócić wyniku dla jednej Biblii!

Opis problemu

Oryginalny opis problemu:

Biorąc pod uwagę plik tekstowy i liczbę całkowitą k, należy wydrukować k najczęstszych słów w pliku (i liczbę ich występowania) ze zmniejszającą się częstotliwością.

Dodatkowe wyjaśnienia problemów:

• Knuth zdefiniował słowa jako ciąg liter łacińskich: [A-Za-z]+
• wszystkie inne postacie są ignorowane
• wielkie i małe litery są uważane za równoważne ( WoRd== word)
• brak limitu rozmiaru pliku i długości słowa
• odległości między kolejnymi słowami mogą być dowolnie duże
• najszybszy program to taki, który zużywa najmniej łącznego czasu procesora (wielowątkowość prawdopodobnie nie pomoże)

Przykładowe przypadki testowe

Test 1: Ulissesa Jamesa Joyce'a połączony 64 razy (plik 96 MB).

• Pobierz Ulysses z projektu Gutenberg:wget http://www.gutenberg.org/files/4300/4300-0.txt
• Połącz to 64 razy: for i in {1..64}; do cat 4300-0.txt >> ulysses64; done
• Najczęstszym słowem jest „the” z 968832 występami.

Test 2: Specjalnie generowany losowy tekst giganovel(około 1 GB).

• Skrypt generatora Python 3 tutaj .
• Tekst zawiera 148391 różnych wyrazów przypominających języki naturalne.
• Najczęstsze słowa: „e” (11309 występów) i „ihit” (11290 występów).

Test ogólności: dowolnie duże słowa z dowolnie dużymi przerwami.

Referencyjne implementacje

Po spojrzeniu w Kodeksie Rosetta tego problemu i zdając sobie sprawę, że wiele implementacji są bardzo powolne, przetestowałem kilka dobrych implementacje (wolniej niż w skrypcie!) Tutaj . Poniżej przedstawiamy wydajność ulysses64wraz ze złożonością czasową:

                                     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)

Czy potrafisz to pokonać?

Testowanie

Wydajność zostanie oceniona przy użyciu 13-calowego MacBooka Pro ze standardowym timepoleceniem uniksowym (czas „użytkownika”). Jeśli to możliwe, użyj nowoczesnych kompilatorów (np. Użyj najnowszej wersji Haskell, a nie starszej).

Dotychczasowe rankingi

Terminy, w tym programy referencyjne:

                                              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

Ranking skumulowany * (%, najlepszy możliwy wynik - 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 wydajności czasowej w stosunku do najlepszych programów w każdym z trzech testów.

Najlepszy program do tej pory: tutaj (drugie rozwiązanie)

[DO]

Następujące przebiega w czasie poniżej 1,6 sekundy dla testu 1 na moim 2.8 GHz Xeon W3530. Zbudowany przy użyciu MinGW.org GCC-6.3.0-1 w systemie Windows 7:

Przyjmuje dwa argumenty jako dane wejściowe (ścieżka do pliku tekstowego i dla liczby k najczęściej używanych słów na liście)

Po prostu tworzy rozgałęzienie drzewa na literach słów, a następnie na listach liści zwiększa licznik. Następnie sprawdza, czy bieżący licznik liści jest większy niż najmniejsze najczęstsze słowo na liście najczęstszych słów. (rozmiar listy to liczba określona za pomocą argumentu wiersza poleceń). Jeśli tak, wypromuj słowo reprezentowane przez literę liścia jako jedno z najczęstszych. Wszystko to powtarza się, dopóki nie zostaną wczytane kolejne litery. Po czym lista najczęstszych słów jest wyprowadzana przez nieefektywne iteracyjne wyszukiwanie najczęstszych słów z listy najczęstszych słów.

Obecnie domyślnie jest wyświetlany czas przetwarzania, ale w celu zachowania spójności z innymi zgłoszeniami wyłącz definicję TIMING w kodzie źródłowym.

Ponadto przesłałem to z komputera roboczego i nie udało mi się pobrać tekstu testu 2. Powinien działać z tym testem 2 bez modyfikacji, jednak może być konieczne zwiększenie wartości 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;
}

W przypadku testu 1 oraz dla 10 najczęściej używanych słów i przy włączonym taktowaniu należy wydrukować:

 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

Rdza

Na moim komputerze działa to giganovel 100000 około 42% szybciej (10,64 s vs. 18,24 s) niż rozwiązanie C „drzewa prefiksów + pojemników” Moogie C. Ponadto nie ma żadnych zdefiniowanych limitów (w przeciwieństwie do rozwiązania C, które określa ograniczenia długości słowa, słów unikalnych, słów powtarzanych itp.).

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

Stosowanie

cargo build --release
time target/release/frequent ulysses64 10

APL (Dyalog Unicode)

Następujące działa w mniej niż 8 sekund na moim 2,6 Ghz i7-4720HQ przy użyciu 64-bitowego programu Dyalog APL 17.0 w systemie Windows 10:

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

Najpierw wyświetla monit o podanie nazwy pliku, a następnie o k. Zauważ, że znaczna część czasu działania (około 1 sekundy) to tylko wczytywanie pliku.

Aby to zrobić, powinieneś być w stanie przesłać następujące elementy do swojego dyalog pliku wykonywalnego (dla dziesięciu najczęstszych słów):

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

Powinien wydrukować:

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

[C] Drzewo prefiksów + kosze

UWAGA: Używany kompilator ma znaczący wpływ na szybkość wykonywania programu! Użyłem gcc (MinGW.org GCC-8.2.0-3) 8.2.0. Podczas korzystania zprzełącznika -Ofast program działa prawie 50% szybciej niż normalnie skompilowany program.

Złożoność algorytmu

Od tego czasu zdałem sobie sprawę, że sortowanie bin, które wykonuję, jest formą sortowania Pigeonhost, co oznacza, że ​​mogę pozbyć się złożoności tego rozwiązania.

Obliczam to jako:

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

Złożoność konstrukcji drzewa jest równoważna przechodzeniu przez drzewo, ponieważ na każdym poziomie prawidłowym węzłem do przejścia jest O (1) (ponieważ każda litera jest mapowana bezpośrednio do węzła, a my zawsze przechodzimy tylko o jeden poziom drzewa dla każdej litery)

Sortowanie gołębi otworów to O (N + n), gdzie n jest zakresem kluczowych wartości, jednak w przypadku tego problemu nie musimy sortować wszystkich wartości, tylko liczbę k, więc najgorszym przypadkiem byłoby O (N + k).

Połączenie razem daje O (1 + N + k).

Złożoność przestrzeni dla konstrukcji drzewa wynika z faktu, że najgorszym przypadkiem jest 26 * węzłów M, jeśli dane składają się z jednego słowa z liczbą M liter i że każdy węzeł ma 26 węzłów (tj. Dla liter alfabetu). Zatem O (26 * M) = O (M)

Ponieważ sortowanie otworów w gołębiach ma złożoność przestrzenną O (N + n)

Po połączeniu daje O (26 * M + N + n) = O (M + N + n)

Algorytm

Przyjmuje dwa argumenty jako dane wejściowe (ścieżka do pliku tekstowego i dla liczby k najczęściej używanych słów na liście)

W oparciu o moje inne wpisy, ta wersja ma bardzo mały czasowy wzrost kosztu przy rosnących wartościach k w porównaniu do moich innych rozwiązań. Ale jest zauważalnie wolniejszy dla niskich wartości k, jednak powinien być znacznie szybszy dla większych wartości k.

Tworzy drzewo rozgałęziające się na literach słów, a następnie na listach liści zwiększa licznik. Następnie dodaje słowo do kosza słów tego samego rozmiaru (po pierwszym usunięciu słowa z kosza, w którym już się znajdowało). Wszystko to powtarza się, dopóki nie zostaną wczytane kolejne litery. Po czym pojemniki są iterowane w odwrotnej kolejności k razy, zaczynając od największego przedziału i wyprowadzane są słowa z każdego przedziału.

Obecnie domyślnie jest wyświetlany czas przetwarzania, ale w celu zachowania spójności z innymi zgłoszeniami wyłącz definicję TIMING w kodzie źródłowym.

// 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;
}

EDYCJA: teraz odkłada zapełnianie pojemników do czasu po zbudowaniu drzewa i optymalizuje konstrukcję wyników.

EDYCJA 2: teraz używa arytmetyki wskaźnika zamiast dostępu do tablicy w celu optymalizacji prędkości.

jot

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

Uruchom jako skrypt za pomocą jconsole <script> <input> <k>. Na przykład dane wyjściowe giganovelz 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

Nie ma limitu, z wyjątkiem ilości dostępnej pamięci systemowej.

C ++ (a la Knuth)

Byłem ciekawy, jak sobie poradzi program Knutha, więc przetłumaczyłem jego (pierwotnie Pascal) program na C ++.

Mimo że głównym celem Knutha nie była szybkość, ale zilustrowanie jego internetowego systemu czytania i pisania, program jest zaskakująco konkurencyjny i prowadzi do szybszego rozwiązania niż jakakolwiek z dotychczasowych odpowiedzi. Oto moje tłumaczenie jego programu (odpowiednie numery „sekcji” programu WEB są wymienione w komentarzach takich jak „ {§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;
}

Różnice w stosunku do programu Knutha:

• I w połączeniu 4 tablice Knutha link, sibling, countich w tablicy Astruct Node (łatwiej zrozumieć w ten sposób).
• Zmieniłem tekstową transkluzję programowania (w stylu WEB) na bardziej konwencjonalne wywołania funkcji (i kilka makr).
• Nie musimy używać standardowych dziwnych konwencji / ograniczeń Pascala, więc używamy freadidata[i] | 32 - 'a' jak w innych odpowiedziach tutaj, zamiast obejścia Pascala.
• W przypadku przekroczenia limitów (braku miejsca) podczas działania programu, oryginalny program Knutha radzi sobie z tym z wdziękiem, usuwając późniejsze słowa i drukując wiadomość na końcu. (Nie jest słuszne stwierdzenie, że McIlroy „skrytykował rozwiązanie Knutha, ponieważ nie był nawet w stanie przetworzyć pełnego tekstu Biblii”; wskazał jedynie, że czasami w tekście mogą pojawić się bardzo częste słowa, takie jak słowo „Jezus „w Biblii, więc warunek błędu nie jest nieszkodliwy.) Przyjąłem głośniejsze (i tak łatwiejsze) podejście po prostu kończąc program.
• Program deklaruje stałą wartość TRIE_SIZE do kontrolowania użycia pamięci, co spowodowało wzrost. (Stała 32767 została wybrana dla oryginalnych wymagań - „użytkownik powinien być w stanie znaleźć 100 najczęstszych słów w dwudziestostronicowym dokumencie technicznym (około 50 KB)” i ponieważ Pascal dobrze radzi sobie z liczbą całkowitą na odległość optymalizuje typy i pakuje je. Musieliśmy go zwiększyć 25x do 800 000, ponieważ dane wejściowe do testu są teraz 20 milionów razy większe).
• W celu ostatecznego wydrukowania łańcuchów możemy po prostu przejść się po trie i zrobić głupi (być może nawet kwadratowy) łańcuch.

Poza tym jest to właściwie program Knutha (wykorzystujący jego strukturę danych mieszania / upakowanej struktury danych i sortowanie kubełkowe) i wykonuje prawie takie same operacje (jak zrobiłby to program Knutha Pascala), jednocześnie zapętlając wszystkie znaki na wejściu; zwróć uwagę, że nie używa on żadnych zewnętrznych algorytmów ani bibliotek struktury danych, a także, że słowa o równej częstotliwości będą drukowane w kolejności alfabetycznej.

wyczucie czasu

Kompilowany z

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

Po uruchomieniu na największej teście tutaj ( giganovelz żądaniem 100 000 słów) i porównaniu z najszybszym opublikowanym tutaj programem, znajduję ją nieco, ale konsekwentnie szybciej:

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

(Górna linia to rozwiązanie Rust Andersa Kaseorga; dolna część to powyższy program. Są to czasy od 100 przebiegów, ze średnią, min, maks., Medianą i kwartylami.)

Analiza

Dlaczego to jest szybsze? Nie chodzi o to, że C ++ jest szybszy niż Rust, ani że program Knutha jest najszybszy z możliwych - w rzeczywistości program Knutha jest wolniejszy przy wstawianiu (jak wspomina) z powodu trie-upakowania (w celu oszczędzania pamięci). Podejrzewam, że przyczyna jest związana z czymś, na co narzekał Knuth w 2008 roku :

Płomień o 64-bitowych wskaźnikach

Absolutnie idiotyczne jest posiadanie 64-bitowych wskaźników, kiedy kompiluję program, który wykorzystuje mniej niż 4 gigabajty pamięci RAM. Kiedy takie wartości wskaźnika pojawiają się wewnątrz struktury, nie tylko marnują połowę pamięci, ale skutecznie wyrzucają połowę pamięci podręcznej.

Powyższy program używa 32-bitowych wskaźników tablicowych (nie wskaźników 64-bitowych), więc struktura „Węzła” zajmuje mniej pamięci, więc na stosie jest więcej Węzłów i mniej braków pamięci podręcznej. (W rzeczywistości, nie było pewne prace na ten temat jako x32 ABI , ale wydaje się, że nie jest w stanie dobrym , chociaż pomysł jest oczywiście przydatne, np patrz niedawne oświadczenie o kompresji wskaźnika w V8 . No cóż.) Więc na giganovel, ten program zużywa 12,8 MB dla (spakowanego) trie, w porównaniu do 32,18 MB z programu Rust dla jego trie (on giganovel). Możemy zwiększyć skalę o 1000x (powiedzmy „giganovel” do „teranovel”) i nadal nie przekraczać 32-bitowych indeksów, więc wydaje się to rozsądnym wyborem.

Szybszy wariant

Możemy zoptymalizować szybkość i zrezygnować z pakowania, dzięki czemu możemy faktycznie używać (niezapakowanego) trie jak w rozwiązaniu Rust, z indeksami zamiast wskaźników. Daje to coś, co jest szybsze i nie ma ustalonych limitów liczby różnych słów, znaków itp .:

#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;
}

Ten program, mimo że robi coś znacznie głupszego do sortowania niż rozwiązania tutaj, używa ( giganoveltylko) 12,2 MB dla swojej wersji i jest szybszy. Czasy działania tego programu (ostatnia linia) w porównaniu z wcześniejszymi wymienionymi czasami:

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

Chciałbym zobaczyć, co by to (lub program hash-trie) przełożyło na Rust . :-)

Dalsze szczegóły

1. O użytej tutaj strukturze danych: wyjaśnienie „prób pakowania” podano zwięźle w ćwiczeniu 4 w sekcji 6.3 (Wyszukiwanie cyfrowe, tj. Próby) w tomie 3 TAOCP, a także w pracy studenta Knutha, Franka Lianga, na temat dzielenia wyrazów w TeX : Słowo Hy-phen-a-tion autorstwa Com-put-er .

2. Kontekst kolumn Bentleya, programu Knutha i recenzji McIlroy'a (tylko niewielka część dotyczyła filozofii uniksowej) jest jaśniejszy w świetle poprzednich i późniejszych kolumn oraz poprzednich doświadczeń Knutha, w tym kompilatorów, TAOCP i TeX.

3. Jest cała książka Ćwiczenia w stylu programowania , pokazująca różne podejścia do tego konkretnego programu itp.

Mam niedokończony post na blogu opisujący powyższe punkty; może edytować tę odpowiedź po jej zakończeniu. Tymczasem i tak zamieszczam tutaj tę odpowiedź, przy okazji (10 stycznia) urodzin Knutha. :-)

Python 3

Ta implementacja z prostym słownikiem jest nieco szybsza niż ta, która korzysta z Counterjednego w moim systemie.

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)

[C] Drzewo prefiksów + posortowana lista połączona

Przyjmuje dwa argumenty jako dane wejściowe (ścieżka do pliku tekstowego i dla liczby k najczęściej używanych słów na liście)

Na podstawie mojego drugiego wpisu ta wersja jest znacznie szybsza dla większych wartości k, ale przy niewielkim koszcie wydajności przy niższych wartościach k.

Tworzy drzewo rozgałęziające się na literach słów, a następnie na listach liści zwiększa licznik. Następnie sprawdza, czy bieżący licznik liści jest większy niż najmniejsze najczęstsze słowo na liście najczęstszych słów. (rozmiar listy to liczba określona za pomocą argumentu wiersza poleceń). Jeśli tak, wypromuj słowo reprezentowane przez literę liścia jako jedno z najczęstszych. Jeśli jest to już najczęstsze słowo, zamień na następne najczęściej, jeśli liczba słów jest teraz wyższa, dzięki czemu lista będzie posortowana. Wszystko to powtarza się, dopóki nie zostaną wczytane żadne litery. Następnie wyświetlana jest lista najczęstszych słów.

Obecnie domyślnie jest wyświetlany czas przetwarzania, ale w celu zachowania spójności z innymi zgłoszeniami wyłącz definicję TIMING w kodzie źródłowym.

// 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;
}

DO#

Ten powinien działać z najnowszymi zestawami SDK .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);
    }
}

Oto przykładowy wynik.

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

Na początku próbowałem użyć słownika z kluczami łańcuchowymi, ale było to zbyt wolne. Myślę, że dzieje się tak, ponieważ ciągi .net są wewnętrznie reprezentowane przez 2-bajtowe kodowanie, co jest trochę marnotrawstwem dla tej aplikacji. Więc właśnie przełączyłem się na czyste bajty i brzydką maszynę stanu w stylu goto. Konwersja wielkości liter jest operatorem bitowym. Sprawdzanie zakresu znaków odbywa się w jednym porównaniu po odjęciu. Nie poświęciłem żadnego wysiłku na optymalizację ostatecznego sortowania, ponieważ odkryłem, że używa on mniej niż 0,1% czasu wykonywania.

Poprawka: algorytm był zasadniczo poprawny, ale nadmiernie raportował wszystkie słowa, licząc wszystkie prefiksy słów. Ponieważ całkowita liczba słów nie jest wymagana dla problemu, usunąłem ten wynik. Aby wypisać wszystkie k słów, dostosowałem również wynik. W końcu zdecydowałem się na używanie, string.Join()a następnie pisanie całej listy na raz. Zaskakujące jest to, że na mojej maszynie jest to około sekundy szybciej niż każde pisanie każdego słowa osobno na 100 000.

Ruby 2.7.0-Preview1 z tally

Najnowsza wersja Ruby ma nową metodę o nazwie tally. Z informacji o wersji :

Enumerable#tallyjest dodany. Liczy występowanie każdego elementu.

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

To prawie rozwiązuje dla nas całe zadanie. Musimy najpierw przeczytać plik, a później znaleźć maksimum.

Oto cała sprawa:

k = ARGV.shift.to_i

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

edycja: Dodano kjako argument wiersza poleceń

Można go uruchomić przy ruby k filename.rb input.txtużyciu wersji Ruby w wersji 2.7.0-Preview1. Można go pobrać z różnych łączy na stronie informacji o wersji lub zainstalować przy użyciu rbenv rbenv install 2.7.0-dev.

Przykład uruchamiany na moim starym, zniszczonym komputerze:

$ 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