Skip to content

La sfida di codifica di Bentley: k parole più frequenti

Esta es el arreglo más válida que te podemos aportar, sin embargo mírala detenidamente y valora si es compatible a tu trabajo.

Soluzione:

C++ (alla Knuth)

Ero curioso di sapere come sarebbe andato il programma di Knuth, così ho tradotto il suo programma (originariamente in Pascal) in C++.

Anche se l'obiettivo primario di Knuth non era la velocità, ma illustrare il suo sistema WEB di programmazione letterata, il programma è sorprendentemente competitivo e porta a una soluzione più veloce di tutte le risposte date finora. Ecco la mia traduzione del suo programma (i numeri delle "sezioni" corrispondenti del programma WEB sono citati in commenti come "{§24}"):

#include 
#include 

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

Differenze rispetto al programma di Knuth:

  • Ho combinato i 4 array di Knuth link, sibling, count e ch in una matrice di un struct Node (in questo modo è più facile da capire).
  • Ho cambiato la trascrizione testuale delle sezioni in stile WEB in chiamate di funzione più convenzionali (e in un paio di macro).
  • Non abbiamo bisogno di usare le strane convenzioni/restrizioni di I/O del Pascal standard, quindi usando fread e data[i] | 32 - 'a' come nelle altre risposte, invece del workaround Pascal.
  • Nel caso in cui si superino i limiti (si esaurisca lo spazio) durante l'esecuzione del programma, il programma originale di Knuth lo affronta con grazia, eliminando le parole successive e stampando un messaggio alla fine. (Non è corretto dire che McIlroy "ha criticato la soluzione di Knuth in quanto non è nemmeno in grado di elaborare un testo completo della Bibbia"; stava solo facendo notare che a volte parole frequenti possono comparire molto tardi in un testo, come la parola "Gesù" nella Bibbia, quindi la condizione di errore non è innocua). Ho scelto l'approccio più rumoroso (e comunque più semplice) di terminare semplicemente il programma.
  • Il programma dichiara una costante TRIE_SIZE per controllare l'uso della memoria, che ho aumentato. (La costante di 32767 era stata scelta per i requisiti originali: "un utente dovrebbe essere in grado di trovare le 100 parole più frequenti in un documento tecnico di venti pagine (all'incirca un file di 50K byte)" e perché il Pascal tratta bene i tipi interi variati e li impacchetta in modo ottimale. Abbiamo dovuto aumentarlo di 25 volte, portandolo a 800.000, poiché l'input di prova è ora 20 milioni di volte più grande).
  • Per la stampa finale delle stringhe, possiamo semplicemente percorrere il trie e fare un'appendice di stringhe stupida (forse anche quadratica).

A parte questo, questo è più o meno esattamente il programma di Knuth (che usa la sua struttura di dati hash trie / packed trie e il bucket sort), e fa più o meno le stesse operazioni (come farebbe il programma Pascal di Knuth) mentre scorre tutti i caratteri dell'input; si noti che non usa librerie esterne di algoritmi o strutture di dati, e anche che le parole di uguale frequenza saranno stampate in ordine alfabetico.

Temporizzazione

Compilato con

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

Quando viene eseguito il testcase più grande (giganovel con 100.000 parole richieste) e confrontato con il programma più veloce postato qui finora, lo trovo leggermente ma costantemente più veloce:

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 linea superiore è la soluzione Rust di Anders Kaseorg; quella inferiore è il programma di cui sopra. Questi sono i tempi di 100 esecuzioni, con media, minimo, massimo, mediana e quartili).

Analisi

Perché è più veloce? Non è che il C++ sia più veloce di Rust o che il programma di Knuth sia il più veloce possibile: in effetti, il programma di Knuth è più lento negli inserimenti (come lui stesso afferma) a causa del trie-packing (per conservare la memoria). La ragione, sospetto, è legata a qualcosa di cui Knuth si è lamentato nel 2008:

Una fiamma sui puntatori a 64 bit

È assolutamente idiota avere puntatori a 64 bit quando compilo un programma che usa meno di 4 gigabyte di RAM. Quando tali valori di puntatori appaiono all'interno di una struct, non solo sprecano metà della memoria, ma di fatto buttano via metà della cache.

Il programma precedente utilizza indici di array a 32 bit (non puntatori a 64 bit), quindi la struct "Node" occupa meno memoria, quindi ci sono più Nodi sullo stack e meno mancanze di cache. (In effetti, c'è stato del lavoro su questo aspetto nell'ABI x32, ma sembra che non sia in uno stato buono anche se l'idea è ovviamente utile, ad esempio si veda il recente annuncio della compressione dei puntatori nella V8. Oh, beh). Quindi su giganovelquesto programma utilizza 12,8 MB per il trie (impacchettato), contro i 32,18 MB del programma Rust (su giganovel). Potremmo scalare di 1000 volte (da "giganovel" a "teranovel", per esempio) e comunque non superare gli indici a 32 bit, quindi questa sembra una scelta ragionevole.

Variante più veloce

Possiamo ottimizzare per la velocità e rinunciare all'impacchettamento, in modo da usare il trie (non impacchettato) come nella soluzione di Rust, con gli indici al posto dei puntatori. In questo modo si ottiene qualcosa di più veloce e non ha limiti prefissati sul numero di parole distinte, caratteri ecc:

#include 
#include 
#include 
#include 

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; // Our "arena" for Node allocation.

std::string word_for(Pointer p) {
  std::vector 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> counts_words;
  for (Pointer i = 1; i < static_cast(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(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;
}

Questo programma, nonostante faccia qualcosa di molto più stupido per l'ordinamento rispetto alle soluzioni qui riportate, utilizza (per giganovel) solo 12,2 MB per il suo trie, e riesce a essere più veloce. I tempi di questo programma (ultima riga), confrontati con i tempi precedenti:

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

Sarei ansioso di vedere come sarebbe questo (o il programma hash-trie) se tradotto in Rust. 🙂

Ulteriori dettagli

  1. Per quanto riguarda la struttura dei dati utilizzata qui: una spiegazione dei tentativi di "impacchettamento" è fornita in modo sommario nell'Esercizio 4 della Sezione 6.3 (Ricerca digitale, cioè tentativi) del Volume 3 di TAOCP, e anche nella tesi di Frank Liang, studente di Knuth, sulla sillabazione in TeX: Word Hy-phen-a-tion by Com-put-er.

  2. Il contesto delle rubriche di Bentley, del programma di Knuth e della recensione di McIlroy (di cui solo una piccola parte riguardava la filosofia Unix) è più chiaro alla luce delle rubriche precedenti e successive e della precedente esperienza di Knuth, tra cui compilatori, TAOCP e TeX.

  3. C'è un intero libro Esercizi di stile di programmazione che mostra diversi approcci a questo particolare programma, ecc.

Ho un post sul blog non ancora terminato che elabora i punti sopra citati.e; potrei modificare questa risposta quando sarà terminata. Nel frattempo, pubblico comunque questa risposta qui, in occasione del compleanno di Knuth (10 gennaio). 🙂

Ruggine

Sul mio computer, questo esegue giganovel 100000 circa il 42% più velocemente (10,64 s contro 18,24 s) rispetto alla soluzione C "prefix tree + bins" di Moogie. Inoltre, non ha limiti predefiniti (a differenza della soluzione C, che prevede limiti sulla lunghezza delle parole, sulle parole uniche, sulle parole ripetute e così via).

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

Utilizzo

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

[Rust] Versione ottimizzata del codice di test9753

Ho cambiato alcuni dettagli (per esempio, la pre-elaborazione dei dati e la divisione dei link padre da quelli figlio) e ho reso il codice un po' più idiomatico.

Sulla mia macchina questo fa girare giganovel circa il 20% più velocemente.

use std::env;
use std::io::{Error, ErrorKind};

type Pointer = i32;
type Count = i32;
type Char = u8;

#[derive(Copy, Clone)]
struct Node {
    link: Pointer,
    count: Count,
}

fn word_for(parents: &[Pointer], mut p: Pointer) -> String {
    let mut drow = Vec::with_capacity(25); // sane max length
    while p != -1 {
        let c = p % 26;
        p = parents[(p / 26) as usize];
        drow.push(b'a' + (c as Char));
    }
    drow.reverse();
    String::from_utf8(drow).unwrap()
}

fn create_child(
    parents: &mut Vec,
    children: &mut Vec,
    p: Pointer,
    c: Char,
) -> Pointer {
    let h = children.len();
    children[p as usize].link = h as Pointer;
    children.resize(children.len() + 26, Node { link: -1, count: 0 });
    parents.push(p);
    (h as u32 + c as u32) as Pointer
}

fn find_child(
    parents: &mut Vec,
    children: &mut Vec,
    p: Pointer,
    c: Char,
) -> Pointer {
    let elem = children[p as usize];
    if elem.link == -1 {
        create_child(parents, children, p, c)
    } else {
        (elem.link as u32 + c as u32) as Pointer
    }
}

fn error(msg: &str) -> Error {
    Error::new(ErrorKind::Other, msg)
}

fn main() -> std::io::Result<()> {
    let args = env::args().collect::>();
    if args.len() != 3 {
        return Err(error(&format!(
            "Usage: {} file-path limit-num",
            env::args().next().unwrap()
        )));
    }
    let mut data: Vec = std::fs::read(&args[1])?;
    for d in &mut data {
        *d = (*d | 32) - b'a';
    }

    let mut children: Vec = Vec::with_capacity(data.len() / 600);
    let mut parents: Vec = Vec::with_capacity(data.len() / 600 / 26);
    parents.push(-1);
    for _ in 0..26 {
        children.push(Node { link: -1, count: 0 });
    }

    let mut data = data.iter();

    while let Some(&c) = data.next() {
        if c < 26 {
            let mut p = c as Pointer;

            while let Some(&c) = data.next() {
                if c < 26 {
                    p = find_child(&mut parents, &mut children, p, c);
                } else {
                    break;
                }
            }
            children[p as usize].count += 1;
        }
    }

    let mut counts_words: Vec<(i32, String)> = Vec::new();
    for (i, e) in children.iter().enumerate() {
        if e.count != 0 {
            counts_words.push((-e.count, word_for(&parents, i as Pointer)));
        }
    }

    counts_words.sort();

    let limit = args[2]
        .parse()
        .map_err(|_| error("ARGV[2] must be in range: [1, usize_max]"))?;

    for (count, word) in counts_words.iter().take(limit) {
        println!("{word} {count}", word = word, count = -count);
    }

    Ok(())
}

Puedes ayudar nuestra faena mostrando un comentario y valorándolo te damos las gracias.



Utilizzate il nostro motore di ricerca

Ricerca
Generic filters

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.