Skip to content

Défi de codage de Bentley : k mots les plus fréquents

Nous avons besoin de votre soutien pour étendre nos revues concernant l'informatique.

Solution :

C++ (à la Knuth)

J'étais curieux de savoir comment le programme de Knuth se comporterait, j'ai donc traduit son programme (originellement en Pascal) en C++.

Même si le but premier de Knuth n'était pas la vitesse mais d'illustrer son système WEB de programmation lettrée, le programme est étonnamment compétitif, et conduit à une solution plus rapide que toutes les réponses ici jusqu'à présent. Voici ma traduction de son programme (les numéros de "section" correspondants du programme WEB sont mentionnés dans des commentaires tels que "...".{§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;
}

Différences par rapport au programme de Knuth :

  • J'ai combiné les 4 tableaux de Knuth link, sibling, count et ch dans un tableau de struct Node (c'est plus facile à comprendre de cette façon).
  • J'ai changé la transclusion textuelle de sections en programmation littérale (style WEB) en appels de fonctions plus conventionnels (et quelques macros).
  • Nous n'avons pas besoin d'utiliser les conventions/restrictions d'entrée/sortie bizarres du Pascal standard, donc en utilisant la fonction fread et data[i] | 32 - 'a' comme dans les autres réponses ici, au lieu de la solution de contournement de Pascal.
  • Dans le cas où nous dépassons les limites (manque d'espace) pendant que le programme est en cours d'exécution, le programme original de Knuth s'en occupe gracieusement en laissant tomber les mots suivants, et en imprimant un message à la fin. (Il n'est pas tout à fait juste de dire que McIlroy "a critiqué la solution de Knuth comme n'étant même pas capable de traiter un texte complet de la Bible" ; il faisait seulement remarquer que parfois des mots fréquents peuvent apparaître très tard dans un texte, comme le mot "Jésus" dans la Bible, de sorte que la condition d'erreur n'est pas anodine). J'ai adopté l'approche plus bruyante (et de toute façon plus facile) consistant à simplement terminer le programme.
  • Le programme déclare une constante TRIE_SIZE pour contrôler l'utilisation de la mémoire, que j'ai augmentée. (La constante de 32767 avait été choisie pour les exigences initiales -- "un utilisateur devrait être capable de trouver les 100 mots les plus fréquents dans un document technique de vingt pages (en gros un fichier de 50K octets)" et parce que Pascal traite bien les types entiers rangés et les empaquette de manière optimale. Nous avons dû l'augmenter de 25x à 800 000 car les entrées de test sont maintenant 20 millions de fois plus grandes).
  • Pour l'impression finale des chaînes de caractères, nous pouvons simplement marcher sur la trie et faire un append de chaîne de caractères stupide (peut-être même quadratique).

En dehors de cela, c'est à peu près exactement le programme de Knuth (en utilisant sa structure de données hash trie / packed trie et bucket sort), et fait à peu près les mêmes opérations (comme le ferait le programme Pascal de Knuth) tout en bouclant sur tous les caractères de l'entrée ; notez qu'il n'utilise aucune bibliothèque externe d'algorithme ou de structure de données, et aussi que les mots de fréquence égale seront imprimés par ordre alphabétique.

Chronométrage

Compilé avec

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

Lorsqu'il est exécuté sur le plus grand testcase ici (giganovel avec 100 000 mots demandés), et comparé au programme le plus rapide posté ici jusqu'à présent, je le trouve légèrement mais constamment plus rapide :

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 ligne supérieure est la solution Rust d'Anders Kaseorg ; la ligne inférieure est le programme ci-dessus. Ce sont des timings de 100 exécutions, avec moyenne, min, max, médiane et quartiles).

Analyse

Pourquoi est-ce plus rapide ? Ce n'est pas que C++ est plus rapide que Rust, ou que le programme de Knuth est le plus rapide possible -- en fait, le programme de Knuth est plus lent sur les insertions (comme il le mentionne) à cause du trie-packing (pour conserver la mémoire). La raison, je soupçonne, est liée à quelque chose dont Knuth s'est plaint en 2008 :

Une flamme à propos des pointeurs 64 bits

Il est absolument idiot d'avoir des pointeurs 64 bits lorsque je compile un programme qui utilise moins de 4 gigaoctets de RAM. Lorsque de telles valeurs de pointeurs apparaissent à l'intérieur d'un struct, elles ne gaspillent pas seulement la moitié de la mémoire, elles jettent effectivement la moitié du cache.

Le programme ci-dessus utilise des indices de tableau de 32 bits (et non des pointeurs de 64 bits), donc la struct "Node" occupe moins de mémoire, donc il y a plus de Nodes sur la pile et moins de ratés de cache. (En fait, il y a eu un certain travail sur ce point dans l'ABI x32, mais il semble qu'il ne soit pas en bon état même si l'idée est manifestement utile, voir par exemple l'annonce récente de la compression des pointeurs dans V8. Ah bon). Donc sur giganovelce programme utilise 12,8 Mo pour le trie (emballé), contre 32,18 Mo pour le trie du programme Rust. giganovel). Nous pourrions augmenter l'échelle de 1000x (de "giganovel" à "teranovel" disons) et ne pas dépasser les indices 32 bits, donc cela semble un choix raisonnable.

Variante plus rapide

Nous pouvons optimiser la vitesse et renoncer à l'empaquetage, de sorte que nous pouvons effectivement utiliser le trie (non empaqueté) comme dans la solution Rust, avec des indices au lieu de pointeurs. Cela donne quelque chose qui est plus rapide et n'a pas de limites préétablies sur le nombre de mots distincts, de caractères, etc :

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

Ce programme, bien que faisant quelque chose de beaucoup plus bête pour le tri que les solutions proposées ici, utilise (pour giganovel) seulement 12.2MB pour sa trie, et parvient à être plus rapide. Timings de ce programme (dernière ligne), comparés aux timings précédents mentionnés :

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

Je serais impatient de voir à quoi ressemblerait ce programme (ou le programme hash-trie) s'il était traduit en Rust. 🙂

Autres détails

  1. À propos de la structure de données utilisée ici : une explication de l'"empaquetage" des essais est donnée de manière laconique dans l'exercice 4 de la section 6.3 (Recherche numérique, c'est-à-dire les essais) du volume 3 de TAOCP, et aussi dans la thèse de Frank Liang, étudiant de Knuth, sur la césure dans TeX : Word Hy-phen-a-tion by Com-put-er.

  2. Le contexte des chroniques de Bentley, du programme de Knuth et de la critique de McIlroy (dont une petite partie seulement concernait la philosophie d'Unix) est plus clair à la lumière des chroniques précédentes et ultérieures, et de l'expérience antérieure de Knuth, notamment les compilateurs, TAOCP et TeX.

  3. Il y a un livre entier Exercices sur le style de programmation, montrant différentes approches de ce programme particulier, etc.

J'ai un article de blog inachevé élaborant sur les points abov...e; Je pourrais éditer cette réponse quand elle sera terminée. En attendant, poster cette réponse ici de toute façon, à l'occasion (10 janvier) de l'anniversaire de Knuth. 🙂

Rust

Sur mon ordinateur, cela exécute giganovel 100000 environ 42% plus rapidement (10,64 s contre 18,24 s) que la solution C "arbre préfixe + bacs" de Moogie. En outre, il n'a pas de limites prédéfinies (contrairement à la solution C qui prédéfinit des limites sur la longueur des mots, les mots uniques, les mots répétés, 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

Utilisation

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

[Rust] Version optimisée du code de test9753.

J'ai modifié quelques détails (par exemple, le prétraitement des données et la séparation des liens parents des liens enfants) tout en rendant le code un peu plus idiomatique.

Sur ma machine, cela exécute le giganovel environ 20% plus rapidement.

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(())
}

Section des critiques et des évaluations

Si vous faites défiler, vous pouvez trouver les commentaires des autres utilisateurs, vous avez également le pouvoir de laisser le vôtre si vous en avez envie.



Utilisez notre moteur de recherche

Ricerca
Generic filters

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.