39
\$\begingroup\$

This is perhaps one of the classical coding challenges that got some resonance in 1986, when columnist Jon Bentley asked Donald Knuth to write a program that would find k most frequent words in a file. Knuth implemented a fast solution using hash tries in an 8-pages-long program to illustrate his literate programming technique. Douglas McIlroy of Bell Labs criticized Knuth's solution as not even able to process a full text of the Bible, and replied with a one-liner, that is not as quick, but gets the job done:

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

In 1987, a follow up article was published with yet another solution, this time by a Princeton professor. But it also couldn't even return result for a single Bible!

Problem description

Original problem description:

Given a text file and an integer k, you are to print the k most common words in the file (and the number of their occurrences) in decreasing frequency.

Additional problem clarifications:

  • Knuth defined a words as a string of Latin letters: [A-Za-z]+
  • all other characters are ignored
  • uppercase and lowercase letters are considered equivalent (WoRd == word)
  • no limit on file size nor word length
  • distances between consecutive words can be arbitrarily large
  • fastest program is the one that uses least total CPU time (multithreading probably won't help)

Sample test cases

Test 1: Ulysses by James Joyce concatenated 64 times (96 MB file).

  • Download Ulysses from Project Gutenberg: wget http://www.gutenberg.org/files/4300/4300-0.txt
  • Concatenate it 64 times: for i in {1..64}; do cat 4300-0.txt >> ulysses64; done
  • Most frequent word is “the” with 968832 appearances.

Test 2: Specially generated random text giganovel (around 1 GB).

  • Python 3 generator script here.
  • The text contains 148391 distinct words appearing similarly to natural languages.
  • Most frequent words: “e” (11309 appearances) and “ihit” (11290 appearances).

Generality test: arbitrarily large words with arbitrarily large gaps.

Reference implementations

After looking into Rosetta Code for this problem and realizing that many implementations are incredibly slow (slower than the shell script!), I tested a few good implementations here. Below is the performance for ulysses64 together with time complexity:

                                     ulysses64      Time complexity
C++ (prefix trie + heap)             4.145          O((N + k) log k)
Python (Counter)                     10.547         O(N + k log Q)
GNU awk + sort                       20.606         O(N + Q log Q)
McIlroy (tr + sort + uniq)           43.554         O(N log N)

Can you beat that?

Testing

Performance will be evaluated using 2017 13" MacBook Pro with the standard Unix time command ("user" time). If possible, please, use modern compilers (e.g., use the latest Haskell version, not the legacy one).

Rankings so far

Timings, including the reference programs:

                                              k=10                  k=100K
                                     ulysses64      giganovel      giganovel
Rust (trie-32) by Tethys Svensson    0.524          3.576          3.593
Rust (trie-32) by test9753           0.622          4.139          4.157
C++ (trie-32) 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
mawk-2 + sort                        2.763          28.488         29.329
OCaml by test9753                    3.615          47.432         262.714
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
Scala (mutable.Map) by lprakashv     9.269          56.019         54.946
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
gawk + sort                          20.529         213.366        222.782
McIlroy (tr + sort + uniq)           43.554         715.602        750.420

Cumulative ranking* (%, best possible score – 300):

#     Program                           Score  Generality
 1  Rust (trie-32) by Tethys Svensson     300     Yes 
 2  Rust (trie-32) by test9753            350     Yes
 3  C++ (trie-32) by ShreevatsaR          365     Yes
 4  C++ (hash trie) by ShreevatsaR        448      x
 5  Rust (trie) by Anders Kaseorg         563     Yes
 6  C (trie + bins) by Moogie             665      x
 7  J by miles                           1498     Yes
 8  C# (trie) by recursive               2109      x
 9  mawk-2 + sort                        2140     Yes
10  C (trie + list) by Moogie            2606      x
11  C++ (trie + heap)                    3991      x
12  Scala (mutable.Map) by lprakashv     4865     Yes
13  Python (dict) by movatica            7370     Yes
14  Python (Counter)                     7781     Yes
15  OCaml by test9753                    9328     Yes
16  Ruby (tally) by daniero             12448     Yes
17  gawk + sort                         16085     Yes
18  McIlroy (tr + sort + uniq)          49209     Yes

*Sum of time performance relative to the best programs in each of the three tests.

Best program so far: here

\$\endgroup\$
15
  • \$\begingroup\$ The score is just the time on Ulysses? It seems implied but it is not explicitly said \$\endgroup\$
    – Wheat Wizard
    Jul 10, 2019 at 13:03
  • \$\begingroup\$ @SriotchilismO'Zaic, for now, yes. But you should not rely on the first test case because bigger test cases might follow. ulysses64 has the obvious disadvantage of being repetitive: no new words appear after 1/64 of the file. So, it's not a very good test case, but it is easy to distribute (or reproduce). \$\endgroup\$ Jul 10, 2019 at 13:22
  • 3
    \$\begingroup\$ I meant the hidden test cases you were talking about earlier. If you post the hashes now when you reveal the actual texts we can ensure that it is fair to the answers and you are not king-making. Although I suppose the hash for Ulysses is somewhat useful. \$\endgroup\$
    – Wheat Wizard
    Jul 10, 2019 at 13:49
  • 1
    \$\begingroup\$ @tsh That is my understanding: e.g. would be two words e and g \$\endgroup\$
    – Moogie
    Jul 12, 2019 at 4:20
  • 1
    \$\begingroup\$ @AndriyMakukha Ah, thanks. Those were just bugs; I fixed them. \$\endgroup\$ Jul 16, 2019 at 6:52

18 Answers 18

15
\$\begingroup\$

C++ (a la Knuth)

I was curious how Knuth's program would fare, so I translated his (originally Pascal) program into C++.

Even though Knuth's primary goal was not speed but to illustrate his WEB system of literate programming, the program is surprisingly competitive, and leads to a faster solution than any of the answers here so far. Here's my translation of his program (the corresponding "section" numbers of the WEB program are mentioned in comments like "{§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;
}

Differences from Knuth's program:

  • I combined Knuth's 4 arrays link, sibling, count and ch into an array of a struct Node (find it easier to understand this way).
  • I changed the literate-programming (WEB-style) textual transclusion of sections into more conventional function calls (and a couple of macros).
  • We don't need to use standard Pascal's weird I/O conventions/restrictions, so using fread and data[i] | 32 - 'a' as in the other answers here, instead of the Pascal workaround.
  • In case we exceed limits (run out of space) while the program is running, Knuth's original program deals with it gracefully by dropping later words, and printing a message at the end. (It's not quite right to say that McIlroy "criticized Knuth's solution as not even able to process a full text of the Bible"; he was only pointing out that sometimes frequent words may occur very late in a text, such as the word "Jesus" in the Bible, so the error condition is not innocuous.) I've taken the noisier (and anyway easier) approach of simply terminating the program.
  • The program declares a constant TRIE_SIZE to control the memory usage, which I bumped up. (The constant of 32767 had been chosen for the original requirements -- "a user should be able to find the 100 most frequent words in a twenty-page technical paper (roughly a 50K byte file)" and because Pascal deals well with ranged integer types and packs them optimally. We had to increase it 25x to 800,000 as test input is now 20 million times larger.)
  • For the final printing of strings, we can just walk the trie and do a dumb (possibly even quadratic) string append.

Apart from that, this is pretty much exactly Knuth's program (using his hash trie / packed trie data structure and bucket sort), and does pretty much the same operations (as Knuth's Pascal program would) while looping through all characters in the input; note that it uses no external algorithm or data structure libraries, and also that words of equal frequency will be printed in alphabetical order.

Timing

Compiled with

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

When run on the largest testcase here (giganovel with 100,000 words requested), and compared against the fastest program posted here so far, I find it slightly but consistently faster:

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

(The top line is Anders Kaseorg's Rust solution; the bottom is the above program. These are timings from 100 runs, with mean, min, max, median, and quartiles.)

Analysis

Why is this faster? It is not that C++ is faster than Rust, or that Knuth's program is the fastest possible -- in fact, Knuth's program is slower on insertions (as he mentions) because of the trie-packing (to conserve memory). The reason, I suspect, is related to something that Knuth complained about in 2008:

A Flame About 64-bit Pointers

It is absolutely idiotic to have 64-bit pointers when I compile a program that uses less than 4 gigabytes of RAM. When such pointer values appear inside a struct, they not only waste half the memory, they effectively throw away half of the cache.

The program above uses 32-bit array indices (not 64-bit pointers), so the "Node" struct occupies less memory, so there are more Nodes on the stack and fewer cache misses. (In fact, there was some work on this as the x32 ABI, but it seems to be not in a good state even though the idea is obviously useful, e.g. see the recent announcement of pointer compression in V8. Oh well.) So on giganovel, this program uses 12.8 MB for the (packed) trie, versus the Rust program's 32.18MB for its trie (on giganovel). We could scale up 1000x (from "giganovel" to "teranovel" say) and still not exceed 32-bit indices, so this seems a reasonable choice.

Faster variant

We can optimize for speed and forego the packing, so we can actually use the (non-packed) trie as in the Rust solution, with indices instead of pointers. This gives something that's faster and has no pre-fixed limits on number of distinct words, characters etc:

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

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

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

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

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

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

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

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

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

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

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

  return 0;
}

This program, despite doing something a lot dumber for sorting than the solutions here, uses (for giganovel) only 12.2MB for its trie, and manages to be faster. Timings of this program (last line), compared with the earlier timings mentioned:

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

I'd be eager to see what this (or the hash-trie program) would like if translated into Rust. :-)

Further details

  1. About the data structure used here: an explanation of "packing" tries is given tersely in Exercise 4 of Section 6.3 (Digital Searching, i.e. tries) in Volume 3 of TAOCP, and also in the thesis of Knuth's student Frank Liang about hyphenation in TeX: Word Hy-phen-a-tion by Com-put-er.

  2. The context of Bentley's columns, Knuth's program, and McIlroy's review (only a small part of which was about the Unix philosophy) is clearer in light of previous and later columns, and Knuth's previous experience including compilers, TAOCP, and TeX.

  3. There's an entire book Exercises in Programming Style, showing different approaches to this particular program, etc.

I have an unfinished blog post elaborating on the points above; might edit this answer when it's done. Meanwhile, posting this answer here anyway, on the occasion (Jan 10) of Knuth's birthday. :-)

\$\endgroup\$
4
  • \$\begingroup\$ Awesome! Not only somebody finally posted the Knuth's solution (I intended to do so, but in Pascal) with great analysis and performance that beats some of the best previous postings, but also set a new record for speed with another C++ program! Wonderful. \$\endgroup\$ Jan 10, 2020 at 18:07
  • 1
    \$\begingroup\$ The only two comments I have: 1) your second program currently fails with Segmentation fault: 11 for test cases with arbitrarily large words and gaps; 2) even though it might feel that I sympathize McIlroy's "critique", I am well aware that Knuth's intention was only to show off his literate programming technique, while McIlroy criticized it from engineering perspective. McIlroy himself later admitted that it was not a fair thing to do. \$\endgroup\$ Jan 10, 2020 at 18:13
  • \$\begingroup\$ @AndriyMakukha Oh oops, that was the recursive word_for; fixed it now. Yes McIlroy, as the inventor of Unix pipes, took the opportunity to evangelize the Unix philosophy of composing small tools. It's a good philosophy, compared to Knuth's frustratingly (if you're trying to read his programs) monolithic approach, but in the context it was a bit unfair, also for another reason: today Unix way is widely available, but in 1986 was confined to Bell Labs, Berkeley, etc ("his firm makes the best prefabs in the business") \$\endgroup\$ Jan 10, 2020 at 19:04
  • \$\begingroup\$ Works! Congrats to the new king :-P As for Unix and Knuth, he didn't seem to like the system very much, because there was and is little unity between different tools (e.g. many tools define regexes differently). \$\endgroup\$ Jan 11, 2020 at 15:34
9
\$\begingroup\$

[Rust] Optimized version of test9753's code

I changed a few details (e.g. pre-processing the data and splitting up the parent links from child links) while also making the code a bit more idiomatic.

On my machine this runs the giganovel about 20% faster.

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<Pointer>,
    children: &mut Vec<Node>,
    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<Pointer>,
    children: &mut Vec<Node>,
    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::<Vec<String>>();
    if args.len() != 3 {
        return Err(error(&format!(
            "Usage: {} file-path limit-num",
            env::args().next().unwrap()
        )));
    }
    let mut data: Vec<u8> = std::fs::read(&args[1])?;
    for d in &mut data {
        *d = (*d | 32) - b'a';
    }

    let mut children: Vec<Node> = Vec::with_capacity(data.len() / 600);
    let mut parents: Vec<Pointer> = 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(())
}
\$\endgroup\$
4
  • \$\begingroup\$ Welcome and congrats for the large margin improvement over ShreevatsaR's C++ solution! \$\endgroup\$ Feb 27, 2020 at 13:56
  • 3
    \$\begingroup\$ This is great, thank you! Learning a lot about Rust from this "more idiomatic" translation of my program :) Actually IIRC I had tried keeping the parent links separate but hadn't seen any speed improvements in the C++ version as I recall. Preprocessing the input is an interesting idea and I'm actually surprised to see it help despite (AFAICT) iterating over the whole input twice. Overall, happy to see the trie idea get faster and faster :) \$\endgroup\$ Feb 27, 2020 at 15:16
  • \$\begingroup\$ Since the problem is specified to not consider unicode letters, this might see another small performance improvement if utf-8 validation was skipped (returning drow directly form word_for and printing it with stdout().write_all(word), or using OsString instead of Vec<u8>). \$\endgroup\$
    – jplatte
    Feb 27, 2020 at 17:16
  • \$\begingroup\$ Would you mind providing a working version for large files (files that cannot fit within the available RAM)? Got memory allocation of 44169952666 bytes failed with your script. Also go thread 'main' panicked at 'attempt to subtract with overflow on smaller files (that can fit into the available memory). \$\endgroup\$
    – Lo Bellin
    Sep 25, 2021 at 23:52
8
\$\begingroup\$

Rust

On my computer, this runs giganovel 100000 about 42% faster (10.64 s vs. 18.24 s) than Moogie’s C “prefix tree + bins” C solution. Also it has no predefined limits (unlike the C solution which predefines limits on word length, unique words, repeated words, 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

Usage

cargo build --release
time target/release/frequent ulysses64 10
\$\endgroup\$
5
  • 2
    \$\begingroup\$ Superb! Very good performance across all three settings. I was just literally in the midst of watching a recent talk by Carol Nichols about Rust :) Somewhat unusual syntax, but I am excited to learn the language: seems to be the only language out of the post-C++ system languages that doesn't sacrifice much performance while making developer's life much easier. \$\endgroup\$ Jul 15, 2019 at 13:17
  • \$\begingroup\$ Very quick! i am impressed! I wonder if the better compiler option for C (tree + bin) will give a similar result? \$\endgroup\$
    – Moogie
    Jul 15, 2019 at 13:36
  • \$\begingroup\$ @Moogie I was already testing yours with -O3, and -Ofast doesn’t make a measurable difference. \$\endgroup\$ Jul 15, 2019 at 13:42
  • \$\begingroup\$ @Moogie, I was compiling your code like gcc -O3 -march=native -mtune=native program.c. \$\endgroup\$ Jul 15, 2019 at 16:38
  • \$\begingroup\$ @Andriy Makukha ah. That would explain the large difference in speed between the results you are getting vs my results: you already were applying optimization flags. I don't think there are many big code optimizations left. I cannot test using map as suggested by others as mingw dies not have an implementation... And would only give a 5% increase. I think I will have to yield to Anders's awesome entry. Well done! \$\endgroup\$
    – Moogie
    Jul 15, 2019 at 20:50
7
\$\begingroup\$

Rust translation of ShreevatsaR's "Faster variant"

Uses:

$ cargo --version
cargo 1.41.0 (626f0f40e 2019-12-03)

$ rustc --version
rustc 1.41.0 (5e1a79984 2020-01-27)

src/main.rs:

use std::env;
use std::fs::File;
use std::io::{Error, ErrorKind, Read};
use std::string::String;
use std::vec::Vec;

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

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

const MAX_STRING_LEN: usize = 25;
const ORD_A: Char = 97; // 'a'

fn word_for(nodes: &[Node], p: Pointer) -> String {
    let mut p = p;
    let mut drow = String::with_capacity(MAX_STRING_LEN);
    while p != 0 {
        let c = p % 27;
        drow.push(char::from(ORD_A - 1 + (c as Char)));
        let index = (p - c) as usize;
        if index != 0 {
            if let Some(elem) = nodes.get(index) {
                p = elem.link;
            } else {
                unreachable!();
            }
        } else {
            p = 0;
        }
    }
    drow.chars().rev().collect()
}

fn create_child(nodes: &mut Vec<Node>, p: Pointer, c: Char) -> Pointer {
    let h = nodes.len();
    nodes.resize(nodes.len() + 27, Node { link: 0, count: 0 });
    if let Some(elem) = nodes.get_mut(h) {
        *elem = Node { link: p, count: -1 };
    } else {
        unreachable!();
    }
    if let Some(el) = nodes.get_mut(p as usize) {
        el.link = h as Pointer;
    }
    (h as u32 + c as u32) as Pointer
}

fn find_child(nodes: &mut Vec<Node>, p: Pointer, c: Char) -> Pointer {
    assert!(1 <= c && c <= 26);
    if p == 0 {
        return c as Pointer;
    }
    if let Some(elem) = nodes.get(p as usize) {
        if elem.link == 0 {
            create_child(nodes, p, c)
        } else {
            (elem.link as u32 + c as u32) as Pointer
        }
    } else {
        unreachable!();
    }
}

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

fn main() -> std::io::Result<()> {
    if env::args().count() != 3 {
      return Err(error(&format!("Usage: {} file-path limit-num",
                     env::args().next().unwrap())));
    }
    let fname = env::args().nth(1).ok_or_else(|| error("Invalid ARGV[1]"))?;
    let mut file = File::open(fname)?;
    let file_size = file.metadata()?.len() as usize;
    let mut data: Vec<u8> = Vec::with_capacity(file_size);
    file.read_to_end(&mut data)?;

    let mut nodes: Vec<Node> = Vec::with_capacity(file_size / 600);
    for _ in 1..=27 {
        nodes.push(Node { link: 0, count: 0 });
    }

    {
        let mut p: Pointer = 0;
        for i in 0..file_size {
            if let Some(elem) = data.get(i) {
                let c: Char = (*elem | 32) - ORD_A + 1;
                if 1 <= c && c <= 26 {
                    p = find_child(&mut nodes, p, c);
                } else if let Some(el) = nodes.get_mut(p as usize) {
                    el.count += 1;
                    p = 0;
                } else {
                    unreachable!();
                }
            } else {
                unreachable!();
            }
        }

        if let Some(e) = nodes.get_mut(p as usize) {
            e.count += 1;
        } else {
            unreachable!();
        }

        if let Some(e) = nodes.get_mut(0) {
            e.count = 0;
        } else {
            unreachable!();
        }
    }

    struct Pair {
        count: i32,
        word: String,
    }

    let mut counts_words: Vec<Pair> = Vec::new();
    for i in 1..nodes.len() {
        if let Some(e) = nodes.get(i) {
            let count = e.count;
            if !((count == 0) || (i % 27 == 0)) {
                counts_words.push(Pair {
                    count,
                    word: word_for(&nodes, i as Pointer),
                });
            }
        } else {
            unreachable!();
        }
    }

    let cmp = |x: &Pair, y: &Pair| -> std::cmp::Ordering {
        if x.count != y.count {
            return y.count.cmp(&x.count);
        }
        x.word.cmp(&y.word)
    };

    counts_words.sort_by(cmp);

    let argv_2 = env::args().nth(2).ok_or_else(|| error("Invalid ARGV[2]"))?;
    let limit = usize::from_str_radix(&argv_2, 10)
        .map_err(|_| error("ARGV[2] must be in range: [1, usize_max]"))?;
    let max_words_to_print = std::cmp::min(counts_words.len(), limit);

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

    Ok(())
}

Building:

$ cargo build --release    

Testing:

$ time ./target/release/bentley golf/ulysses64 10
the 968832
of 528960
and 466432
a 421184
to 322624
in 320512
he 270528
his 213120
i 191808
s 182144

real    0m1.408s
user    0m1.240s
sys     0m0.157s

C++ "Faster variant" testing

$ time golf/faster-variant golf/ulysses64 10
the 968832
of 528960
and 466432
a 421184
to 322624
in 320512
he 270528
his 213120
i 191808
s 182144

real    0m1.533s
user    0m1.411s
sys     0m0.109s
\$\endgroup\$
2
  • 1
    \$\begingroup\$ New top! Congrats. I built your program with opt-level = 3. I also tried lto = true, as in @AndersKaseorg 's answer, but it only made the performance worse (it produces 7–13% slower executables, which would make it slower than C++). The margin is quite narrow! \$\endgroup\$ Feb 27, 2020 at 2:24
  • 2
    \$\begingroup\$ Thanks for translating my program into Rust! It's very instructive. \$\endgroup\$ Feb 27, 2020 at 14:38
5
\$\begingroup\$

[C]

The following runs in under 1.6 seconds for Test 1 on my 2.8 Ghz Xeon W3530. Built using MinGW.org GCC-6.3.0-1 on Windows 7:

It takes two arguments as input (path to text file and for k number of most frequent words to list)

It simply creates a tree branching on letters of words, then at the leaf letters it increments a counter. Then checks to see if the current leaf counter is greater than the smallest most frequent word in the list of most frequent words. (list size is the number determined via the command line argument) If so then promote the word represented by the leaf letter to be one of the most frequent. This all repeats until no more letters are read in. After which the list of most frequent words are output via an inefficent iterative search for the most frequent word from the list of most frequent words.

It currently defaults to output the processing time, but for purposes of conistency with other submissions, disable the TIMING definition in the source code.

Also, I have submitted this from a work computer and have not been able to download Test 2 text. It should work with this Test 2 without modification, however the MAX_LETTER_INSTANCES value may need to be increased.

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

For Test 1, and for the top 10 frequent words and with timing enabled it should print:

 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
\$\endgroup\$
5
  • \$\begingroup\$ Impressive! Use of list supposedly makes it O(Nk) in the worst case, so it runs slower than the reference C++ program for giganovel with k = 100,000. But for k << N it is a clear winner. \$\endgroup\$ Jul 12, 2019 at 7:03
  • 1
    \$\begingroup\$ @AndriyMakukha Thanks! I was a little surprised that such a simple implementation yielded great speed. I could make it better for larger values of k by having the list sorted. (the sorting should not be too expensive as the list order would be changing slowly) but that adds complexity, and would likely impact the speed for lower values of k. Will have to experiment \$\endgroup\$
    – Moogie
    Jul 12, 2019 at 7:10
  • \$\begingroup\$ yeah, I was surprised as well. It might be because the reference program uses a lot of function calls and the compiler fails to optimize it properly. \$\endgroup\$ Jul 12, 2019 at 7:14
  • \$\begingroup\$ Another performance benefit probably comes from the semistatic allocation of letters array, while the reference implementation allocates tree nodes dynamically. \$\endgroup\$ Jul 12, 2019 at 10:29
  • \$\begingroup\$ mmap-ing should be faster (~5% on my linux laptop): #include<sys/mman.h>,<sys/stat.h>,<fcntl.h>, replace file reading with int d=open(argv[1],0);struct stat s;fstat(d,&s);dataLength=s.st_size;data=mmap(0,dataLength,1,1,d,0); and comment out free(data); \$\endgroup\$
    – ngn
    Jul 14, 2019 at 17:28
3
\$\begingroup\$

[C] Prefix Tree + Bins

NOTE: The compiler used has a significant effect on program execution speed! I have used gcc (MinGW.org GCC-8.2.0-3) 8.2.0. When using the -Ofast switch, the program runs almost 50% faster than the normally compiled program.

Algorithm Complexity

I have since come to realise that the Bin sorting I am performing is a form of Pigeonhost sort this means that i can derrive the Big O complexity of this solution.

I calculate it to be:

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

The tree construction complexity is equivalent to tree traversal so since at any level the correct node to traverse to is O(1) (as each letter is mapped directly to a node and we are always only traverse one level of the tree for each letter)

Pigeon Hole sorting is O(N + n) where n is the range of key values, however for this problem, we do not need to sort all values, only the k number so the worst case would be O(N + k).

Combining together yields O(1 + N + k).

Space Complexity for tree construction is due to fact that the worst case is 26*M nodes if the data consists of one word with M number of letters and that each node has 26 nodes (i.e. for the letters of the alphabet). Thus O (26*M) = O(M)

For the Pigeon Hole sorting has space complexity of O(N + n)

Combining together yields O(26*M + N + n) = O(M + N + n)

Algorithm

It takes two arguments as input (path to text file and for k number of most frequent words to list)

Based on my other entries, this version has a very small time cost ramp with increasing values of k compared to my other solutions. But is noticeably slower for low values of k however it should be much faster for larger values of k.

It create a tree branching on letters of words, then at the leaf letters it increments a counter. Then adds the word to a bin of words of the same size (after first removing the word from bin it already resided in). This all repeats until no more letters are read in. After which the bins are reverse iterated k times starting from the largest bin and the words of each bin are output.

It currently defaults to output the processing time, but for purposes of conistency with other submissions, disable the TIMING definition in the source code.

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

EDIT: now deferring populating bins until after tree is constructed and optimising construction of output.

EDIT2: now using pointer arithmetic instead of array access for speed optimisation.

\$\endgroup\$
6
  • \$\begingroup\$ Wow! 100,000 most frequent words from a 1 GB file in 11 seconds... This looks like some kind of magic trickery. \$\endgroup\$ Jul 13, 2019 at 13:03
  • \$\begingroup\$ No tricks... Just trading CPU time for in efficient memory usage. I am surprised at your result... On my older pc it takes over 60 seconds. I have noticed that I I am doing unnecessary comparisons and can defer binning until the file has been processed. It should make it even quicker. I will try it soon and update my answer. \$\endgroup\$
    – Moogie
    Jul 13, 2019 at 21:14
  • \$\begingroup\$ @AndriyMakukha I have now deferred populating the Bins until after all the words has been processed and the tree is constructed. This avoids unnecessary comparisons and bin element manipulation. I also changed the way the output is constructed as i found printing was taking a significant amount of time! \$\endgroup\$
    – Moogie
    Jul 14, 2019 at 1:49
  • \$\begingroup\$ On my machine this update doesn't make any noticeable difference. However, it did perform very fast on ulysses64 once, so it is a current leader now. \$\endgroup\$ Jul 14, 2019 at 8:03
  • \$\begingroup\$ Must be a unique issue with my PC then :) I noticed a 5 second speed up when using this new output algorithm \$\endgroup\$
    – Moogie
    Jul 14, 2019 at 12:46
3
\$\begingroup\$

APL (Dyalog Unicode)

The following runs in under 8 seconds on my 2.6 Ghz i7-4720HQ using 64-bit Dyalog APL 17.0 on Windows 10:

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

It first prompts for the file name, then for k. Note that a significant part of the running time (about 1 second) is just reading the file in.

To time it, you should be able to pipe the following into your dyalog executable (for the ten most frequent words):

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

It should print:

 the  968832
 of   528960
 and  466432
 a    421184
 to   322624
 in   320512
 he   270528
 his  213120
 i    191808
 s    182144
\$\endgroup\$
19
  • \$\begingroup\$ Very nice! It beats Python. It worked best after export MAXWS=4096M. I guess, it uses hash tables? Because reducing workspace size to 2 GB makes it slower by whole 2 seconds. \$\endgroup\$ Jul 10, 2019 at 13:37
  • \$\begingroup\$ @AndriyMakukha Yes, uses a hash table as per this, and I'm pretty sure does internally too. \$\endgroup\$
    – Adám
    Jul 10, 2019 at 13:43
  • \$\begingroup\$ Why is it O(N log N)? Looks more like Python (k times restoring heap of all unique words) or AWK (sorting only unique words) solution to me. Unless you sort all the words, like in McIlroy's shell script, it shouldn't be O(N log N). \$\endgroup\$ Jul 10, 2019 at 16:03
  • \$\begingroup\$ @AndriyMakukha It grades all the counts. Here is what our performance guy wrote me: Time complexity is O(N log N), unless you believe some theoretically dubious things about hash tables, in which case it's O(N). \$\endgroup\$
    – Adám
    Jul 10, 2019 at 16:36
  • \$\begingroup\$ Well, when I run your code against 8, 16, and 32 Ulysses, it slows down exactly linearly. Maybe your performance guy needs to reconsider his views on hash tables' time complexity :) Also, this code doesn't work for the bigger test case. It returns WS FULL, even though I increased working space to 6 GB. \$\endgroup\$ Jul 11, 2019 at 9:26
3
\$\begingroup\$

J

9!:37 ] 0 _ _ _

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

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

exit 0

Run as a script with jconsole <script> <input> <k>. For example, the output from the giganovel with 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

There's no limit except for the amount of available system memory.

\$\endgroup\$
3
  • \$\begingroup\$ Very fast for the smaller test case! Nice! However, for arbitrarily large words it truncates words in the output. I am not sure if there is a limit on number of characters in a word or if it is just to make output more concise. \$\endgroup\$ Jul 27, 2019 at 10:01
  • \$\begingroup\$ @AndriyMakukha Yeah, the ... occurs because of output truncation per line. I added one line at the start to disable all truncation. It slows down on giganovel since it uses much more memory as there are more unique words. \$\endgroup\$
    – miles
    Jul 27, 2019 at 12:28
  • \$\begingroup\$ Great! Now it passes the generality test. And it didn't slow down on my machine. In fact, there was a minor speedup. \$\endgroup\$ Jul 27, 2019 at 12:51
3
\$\begingroup\$

Java

I though it would be nice to get Java represented. There i nothing novel in the approach, just porting what others have done.

package trie;

import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.List;

public class ByteTrie {

    static class Node {
        public Node parent;
        public int index;
        public Node[] nodes = null;
        public int count;

        public Node(Node parent, int index) {
            this.parent = parent;
            this.index = index;
            Trie.allNodes.add(this);
        }

        public String getWord() {
            if (this.index >= 0) {
                return this.parent.getWord() + (char) (this.index + 97);
            } else {
                return "";
            }
        }

        public Node traverse(int b) {
            if (this.nodes == null) {
                this.nodes = new Node[26];
                return this.nodes[b] = new Node(this, b);
            }
            if (this.nodes[b] == null) return this.nodes[b] = new Node(this, b);
            return this.nodes[b];
        }
    }

    static class Trie {
        public static List<Node> allNodes = new ArrayList<>();
        private final Node root = new Node(null, -1);
    }

    public static class App {
        private final String filename;
        private final int k;

        public App(String filename, int k) {
            this.filename = filename;
            this.k = k;
        }

        public void run() throws IOException {
            Trie trie = new Trie();

            Path path = Paths.get(filename);

            Node current = trie.root;

            InputStream inputStream = Files.newInputStream(path);
            BufferedInputStream bufferedInputStream = new BufferedInputStream(inputStream);
            int b;
            boolean inWord = false;
            while ((b = bufferedInputStream.read()) != -1) {
                int u = ((b | 32) - 97);
                if (u >= 26 || u < 0) {
                    if (inWord) {
                        ++current.count;
                    }
                    inWord = false;
                } else {
                    if (!inWord) {
                        current = trie.root;
                    }
                    inWord = true;
                    current = current.traverse(u);
                }
            }

            bufferedInputStream.close();
            inputStream.close();
            Trie.allNodes.sort((o1, o2) -> Integer.compare(o2.count, o1.count));
            List<Node> finalList = Trie.allNodes.subList(0, k);
            for (Node node : finalList) {
                System.out.println(node.getWord() + "\t" + node.count);
            }
        }

    }

    public static void main(String[] args) throws IOException {
        if (args.length == 0) {
            System.out.println("Filename required");
            System.exit(1);
        }
        String filename = args[0];
        int k = args.length > 1 ? Integer.parseInt(args[1]) : 10;
        App app = new App(filename, k);
        app.run();
    }

}

The fun part is compiling it to a native image using GraalVM with PGO (which unfortunately requires GraalVM Enterprise Edition) which roughly cuts the runtime in half.

java:

time java -jar build/libs/trie-1.0-all.jar ../giganovel 100000  
8.02s user 0.27s system 101% cpu 8.186 total

java -jar build/libs/trie-1.0-all.jar ../ulysses64 10  
0.82s user 0.03s system 111% cpu 0.763 total

native image:

time ./trie-1.0-all ../giganovel 100000  
4.14s user 0.26s system 96% cpu 4.582 total

time ./trie-1.0-all ../ulysses64 10  
0.35s user 0.02s system 99% cpu 0.366 total

Full solution at https://github.com/dillon-sellars/MultiTrie

\$\endgroup\$
2
  • \$\begingroup\$ Welcome to Code Golf, and nice answer! I had no idea the JVM made things twice as slow (if that's what's at play here). \$\endgroup\$ Mar 2, 2022 at 2:09
  • \$\begingroup\$ Great! Thanks for an awesome answer. Unfortunately, I already gave away my Intel laptop and bought a new one. So, I'll rank your answer once somebody else answers it. \$\endgroup\$ May 9, 2022 at 17:00
2
\$\begingroup\$

Scala Simple Implementation (using mutable.Map)

  val map = scala.collection.mutable.Map.empty[String, Int]

  def wordsFromFile(filePath: String) = {
    val file = scala.io.Source.fromFile(filePath)

    val regex = "[a-z]+".r()

    file
      .getLines()
      .flatMap(line => (regex findAllIn line.toLowerCase))
      .foreach { word =>
        val v = map.getOrElse(word, 0)
        map.put(word, v + 1)
      }

    file.close()
  }

  def freq(filePath: String, k: Int) = {
    wordsFromFile(filePath)

    map.toSeq
      .sortBy(a => -a._2)
      .take(k)
  }

  val start = System.currentTimeMillis()
  freq("ulysses64", 10)
    .foreach { 
      case (word, count) => println(s"$word\t$count")
    }
  val end = System.currentTimeMillis()
  println(s"Time taken: ${end - start} ms")

Result:

the 968832
of  528960
and 466432
a   421184
to  322624
in  320512
he  270528
his 213120
i   191808
s   182144
Time taken: 3973 ms
\$\endgroup\$
1
  • \$\begingroup\$ Thanks for posting! Even though your solution runs in less than four seconds with ulysses64, the CPU time it uses is over 9 seconds. That's what counts. But hey: it's still much faster than Python ;) \$\endgroup\$ Feb 27, 2020 at 17:55
2
\$\begingroup\$

RUST Hashmap with FNV hasher

Managed to get around ~95% of the top performer's performance without a custom data structure by just using a good hashmap.

EDIT: This doesn't scale well to giganovel - which it is performing much worse on (2-3 times slower).

❯ time "./target/release/current ulysses64.txt 10"
Benchmark #1: ./target/release/current ulysses64.txt 10
  Time (mean ± σ):     718.8 ms ±  26.8 ms    [User: 643.0 ms, System: 66.2 ms]
  Range (min … max):   676.5 ms … 763.6 ms    10 runs


❯ time "./target/release/mine ulysses64.txt 10"
Benchmark #1: ./target/release/mine
  Time (mean ± σ):     760.8 ms ±  26.7 ms    [User: 660.5 ms, System: 90.0 ms]
  Range (min … max):   730.0 ms … 800.2 ms    10 runs

in cargo.toml:

[dependencies]
fnv = "1.0"

Code:

use std::env::args;
use std::fs::File;
use std::io::Read;
use std::str::from_utf8_unchecked;

use fnv::FnvHashMap;

type Result<T> = std::result::Result<T, Box<dyn std::error::Error>>;

struct WordServer<'a> {
    data: &'a [u8],
    index: usize,
}

impl<'a> Iterator for WordServer<'a> {
    type Item = &'a [u8];

    fn next(&mut self) -> Option<Self::Item> {
        let start = self.index;

        let end = loop {
            let b = match self.data.get(self.index) {
                Some(b) => *b,
                None => return None,
            };

            match b {
                0..=25 => self.index += 1,
                _ => break self.index,
            }
        };

        loop {
            let b = match self.data.get(self.index) {
                Some(b) => *b,
                None => return None,
            };

            match b {
                0..=25 => break,
                _ => self.index += 1,
            }
        }

        Some(&self.data[start..end])
    }
}

fn go(file: &str, topn: usize) -> Result<()> {
    let mut file = File::open(file)?;
    let file_len = file.metadata()?.len();

    let mut data = Vec::with_capacity(file_len as usize);

    file.read_to_end(&mut data)?;

    // Convert all data into lowercase and nulls
    let data = data
        .iter()
        .map(|b| (b | 0b100000).wrapping_sub(b'a'))
        .collect::<Vec<_>>();

    let word_server = WordServer {
        data: data.as_slice(),
        index: 0,
    };

    let cap = file_len >> 35;

    // let mut collection: HashMap<&[u8], u32> = HashMap::with_capacity(cap as usize);
    // let mut collection: HashMap<&[u8], u32> = HashMap::with_hasher();
    let mut collection = FnvHashMap::with_capacity_and_hasher(cap as usize, Default::default());

    // Add words to our collection

    for word in word_server {
        match collection.get_mut(word) {
            Some(num) => *num += 1,
            None => {
                collection.insert(word, 1);
            }
        }
    }

    // Now get top n words

    let mut all = collection.iter().collect::<Vec<(&&[u8], &u32)>>();

    all.sort_unstable_by(|a, b| b.1.partial_cmp(a.1).unwrap());

    for (b, c) in all.iter().take(topn) {
        let changed = b.iter().map(|b| b + b'a').collect::<Vec<u8>>();

        let string = unsafe { from_utf8_unchecked(&changed) };
        println!("Count: {}: {}", c, string);
    }

    Ok(())
}

fn main() {
    let mut args = args();
    let file = args.nth(1).unwrap();
    let topn = args.next().unwrap().parse::<usize>().unwrap();
    go(&file, topn).unwrap()
}
```
\$\endgroup\$
6
  • \$\begingroup\$ Doesn't compile. 1) ``` 2) "use of undeclared type or module fnv". Please, make sure it compiles as is without debugging and/or provide instructions on how to compile it. \$\endgroup\$ Feb 27, 2020 at 10:05
  • \$\begingroup\$ Also, please, note that there are three tests, while your program seems to be hardcoded to work with the first test only… I think, your program must pass at least three tests without recompilation (one for ulysses64 and two for giganovel) in order to qualify for final ranking. \$\endgroup\$ Feb 27, 2020 at 10:17
  • \$\begingroup\$ Ok done - it now takes arguments as the others do. There is a dependency to compile since fnv is an external crate. \$\endgroup\$
    – Plasma_000
    Feb 27, 2020 at 18:44
  • \$\begingroup\$ Could you include the full Cargo.toml file and build command (as in Anders Kaseorg's answer)? On my computer let alone "~95% of the top performer's performance" this seems to take more than twice as long as test9753's answer (which was the top performer at the time you posted this answer), namely about 10.9 seconds instead of about 4.8 seconds. I assume you are testing it on giganovel rather than ulysses64 right? \$\endgroup\$ Feb 27, 2020 at 21:24
  • \$\begingroup\$ Yeah you're totally right, I wasn't testing giganovel and it is performing much worse on that. I'm guessing the reason is a combination of more different words (they dont need to be in the english dictionary), and the hashmap needing to scale larger. \$\endgroup\$
    – Plasma_000
    Feb 28, 2020 at 0:01
2
\$\begingroup\$

OCaml

Pre-requisites:

  1. Install Opam
  2. $ opam install core dune
$ opam --version
2.0.6

$ ocamlc --version
4.10.0

$ dune --version
2.3.1

$ opam show -f version core
v0.13.0

File: main.ml

open Core;;
let () =
  let argv = Sys.get_argv () in
  match argv with
  | [| _prog_name; file_name; limit |] ->
    let limit = Int.of_string limit in
    assert (limit > 0);
    In_channel.with_file file_name ~f:(fun in_ch -> (
      let word_counts = String.Table.create () in
      let update_word_counts current_chars =
        if not (List.is_empty current_chars) then (
          let current_word = String.of_char_list @@ List.rev current_chars in
          String.Table.update word_counts current_word
            ~f:(fun v -> 1 + (Option.value v ~default:0))) in
      let buf_size = 1048576 in
      let buf = Bytes.create buf_size in
      let finished = ref false in
      let current_chars = ref [] in
      while not !finished do
        let len = In_channel.input in_ch ~buf ~pos:0 ~len:buf_size in
        if len > 0 then (
          for i = 0 to (len - 1) do
            let ch = Caml.Bytes.get buf i in
            current_chars := (
              if Char.is_alpha ch then ((Char.lowercase ch) :: !current_chars)
              else (update_word_counts !current_chars; []))
          done
        ) else finished := true
      done;
      update_word_counts !current_chars;
      let count = Int.min limit (String.Table.length word_counts) in
      let max_word, max_count, max_wcs = ref "", ref 0, ref [] in
      for _i = 1 to count do
        String.Table.iteri word_counts ~f:(fun ~key ~data ->
          if data > !max_count then (max_word := key; max_count := data));
        String.Table.remove word_counts !max_word;
        max_wcs := (!max_word, !max_count) :: (!max_wcs);
        max_word := ""; max_count := 0
      done;
      max_wcs := List.sort (!max_wcs) ~compare:(fun (w1, c1) (w2, c2) ->
        if phys_equal c1 c2 then String.compare w1 w2 else Int.compare c2 c1);
      List.iter (!max_wcs) ~f:(fun (word, count) ->
        Printf.printf "%s %d\n" word count)))
  | _ -> Printf.eprintf "Error: Usage: %s file-name limit\n" argv.(0)

File: dune

(executable
 (name main)
 (libraries core))

Build:

$ dune build main.exe

Run:

$ time ./_build/default/main.exe ulysses64 10
the 968832
of 528960
and 466432
a 421184
to 322624
in 320512
he 270528
his 213120
i 191808
s 182144

real  0m6.143s
user  0m6.047s
sys   0m0.068s
\$\endgroup\$
3
  • \$\begingroup\$ Operation opam install core=v0.12.3 dune failed with a long error message, that contained: core → ppx_jane < v0.13 → ppxlib < 0.9.0 → ocaml < 4.10. I guess, it didn't like that my OCaml version is 4.10. I did opam install core dune, now it doesn't compile: Error (alert deprecated): Core.Sys.argv [since 2019-08] Use [Sys.get_argv] instead – could you, please, rewrite it to use the latest compiler, as mentioned in the question? \$\endgroup\$ Mar 3, 2020 at 22:39
  • \$\begingroup\$ Updated as requested. \$\endgroup\$
    – test9753
    Mar 5, 2020 at 11:23
  • \$\begingroup\$ Thanks. Added it to the ranking table. 15th best program so far. \$\endgroup\$ Mar 5, 2020 at 13:26
2
\$\begingroup\$

Since only latin words are searched for, don't forget to export LC_ALL=C:

$ time ./wordcount.sh /tmp/ulysses64.txt 10
...
./wordcount.sh /tmp/ulysses64.txt 10  31.48s user 0.63s system 103% cpu 31.016 total
$ time ./wordcount.mawk /tmp/ulysses64.txt 10
...
./wordcount.mawk /tmp/ulysses64.txt 10  3.68s user 0.14s system 104% cpu 3.653 total
$ export LC_ALL=C
$ time ./wordcount.sh /tmp/ulysses64.txt 10
...
./wordcount.sh /tmp/ulysses64.txt 10  8.64s user 0.42s system 113% cpu 7.979 total
$ time ./wordcount.mawk /tmp/ulysses64.txt 10
...
./wordcount.mawk /tmp/ulysses64.txt 10  3.58s user 0.12s system 104% cpu 3.541 total

wordcount.sh:

#!/bin/sh
tr -cs A-Za-z '\n' <"$1" | tr A-Z a-z | sort | uniq -c | sort -rn | head -n"$2"

wordcount.mawk:

#!/bin/sh
tr A-Z a-z <"$1" | mawk -vRS='[^a-z]+' '
    {++count[$0]}
    END {for (w in count) print count[w], w}' | \
        sort -k1,1 -rn | head -n"$2"

By the way, here's a simpler and faster wordcount.py:

#!/usr/bin/env python3.9
import collections, re, sys

filename = sys.argv[1]
k = int(sys.argv[2])
reg = re.compile('[a-z]+')

counts = collections.Counter()
counts.update(reg.findall(open(filename).read().lower()))
for i, w in counts.most_common(k):
    print(i, w)

Result:

$ time ./wordcount_SE.py /tmp/ulysses64.txt 10
...
./wordcount_SE.py /tmp/ulysses64.txt 10  16.28s user 0.22s system 99% cpu 16.508 total
$ time ./wordcount.py /tmp/ulysses64.txt 10
...
./wordcount.py /tmp/ulysses64.txt 10  10.65s user 0.96s system 99% cpu 11.607 total

My favourite scripting language is quite slow, sadly:

$ time ./wordcount.tcl /tmp/ulysses64.txt 10
...
./wordcount.tcl /tmp/ulysses64.txt 10  24.13s user 0.87s system 99% cpu 25.000 total

wordcount.tcl:

#!/usr/bin/env tclsh

proc wordcount {path head} {
    set data [string tolower [read [open $path]]]
    foreach word [regexp -all -inline {[a-z]+} $data] {
        dict incr wordcount $word
    }
    set sorted [lsort -stride 2 -index 1 -int -decr $wordcount]
    lrange $sorted 0 [expr {$head * 2 - 1}]
}

foreach {count word} [wordcount {*}$argv] {
    puts "$word\t$count"
}

Everything done on Gentoo -O3 -march=native with an AMD 2700X, mawk-20200106, python 3.9, tcl-8.6.8 and coreutils 8.32.

PS: some interesting additions would be Pypy and LuaJIT

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for awesome answer! You are right about LC_ALL=C. It really improves the performance of standard Unix tools for the given problem. Your TCL solution is also interesting. However, I don't plan to include new solutions into the standings, until someone beats Tethys Svensson. \$\endgroup\$ Jun 17, 2021 at 7:53
1
\$\begingroup\$

Python 3

This implementation with a simple dictionary is slightly faster than the one using Counter one on my system.

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)
\$\endgroup\$
4
  • 1
    \$\begingroup\$ I could only test with giganovel on my system, and it takes quite a long time (~90sec). gutenbergproject is blocked in Germany for legal reasons... \$\endgroup\$
    – movatica
    Jul 12, 2019 at 21:30
  • \$\begingroup\$ Interesting. It's either heapq doesn't add any performance to the Counter.most_common method, or enumerate(sorted(...)) also uses heapq internally. \$\endgroup\$ Jul 13, 2019 at 7:55
  • \$\begingroup\$ I tested with Python 2 and the performance was similar, so, I guess, sorting just works about as fast, as Counter.most_common. \$\endgroup\$ Jul 13, 2019 at 14:34
  • \$\begingroup\$ Yeah, maybe it was just jitter on my system... At least it is not slower :) But the regex search is a lot faster than iterating over characters. It seems to be implemented quite performant. \$\endgroup\$
    – movatica
    Jul 14, 2019 at 8:25
1
\$\begingroup\$

[C] Prefix Tree + Sorted Linked List

It takes two arguments as input (path to text file and for k number of most frequent words to list)

Based on my other entry, this version is much faster for larger values of k but at a minor cost of performance at lower values of k.

It create a tree branching on letters of words, then at the leaf letters it increments a counter. Then checks to see if the current leaf counter is greater than the smallest most frequent word in the list of most frequent words. (list size is the number determined via the command line argument) If so then promote the word represented by the leaf letter to be one of the most frequent. If already a most frequent word, then swap with the next most frequent if the word count is now higher, thus keeping the list sorted. This all repeats until no more letters are read in. After which the list of most frequent words are output.

It currently defaults to output the processing time, but for purposes of conistency with other submissions, disable the TIMING definition in the source code.

// 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;
}
\$\endgroup\$
3
  • \$\begingroup\$ It returns not very sorted output for k=100,000: 12 eroilk 111 iennoa 10 yttelen 110 engyt. \$\endgroup\$ Jul 12, 2019 at 14:05
  • \$\begingroup\$ I think I have an idea as to the reason. My thought is that I will need to iterate swap words in the list when checking whether the current word's next highest word. When I have time I will check \$\endgroup\$
    – Moogie
    Jul 12, 2019 at 22:02
  • \$\begingroup\$ hmm well it seems that the simple fix of changing an if to while does work, however it also significantly slows down the algorithm for larger values of k. I may have to think of a more clever solution. \$\endgroup\$
    – Moogie
    Jul 13, 2019 at 9:52
1
\$\begingroup\$

C#

This one should work with the lastest .net SDKs.

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

Here's a sample output.

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

At first, I tried to use a dictionary with string keys, but that was way too slow. I think it's because .net strings are internally represented with a 2-byte encoding, which is kind of wasteful for this application. So then I just switched to pure bytes, and an ugly goto-style state machine. Case conversion is a bitwise operator. Character range checking is done in a single comparison after subtraction. I didn't spend any effort optimizing the final sort since I found it's using less than 0.1% of the runtime.

Fix: The algorithm was essentially correct, but it was over-reporting total words, by counting all prefixes of words. Since total word count isn't a requirement of the problem, I removed that output. In order to output all k words, I also adjusted the output. I eventually settled on using string.Join() and then writing the whole list at once. Surprisingly this is about a second faster on my machine that writing each word separately for 100k.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Very impressive! I like your bitwise tolower and single comparison tricks. However, I don't understand why your program reports more distinct words than expected. Also, according to the original problem description, the program needs to output all k words in decreasing order of frequency, so I didn't count your program towards the last test, which needs to output 100,000 most frequent words. \$\endgroup\$ Jul 13, 2019 at 7:51
  • \$\begingroup\$ @AndriyMakukha: I can see that I'm also counting word prefixes that never occurred in the final count. I avoided writing all the output because console output is pretty slow in windows. Can I write the output to a file? \$\endgroup\$
    – recursive
    Jul 13, 2019 at 13:09
  • \$\begingroup\$ Just print it standard output, please. For k=10, it should be fast on any machine. You can also redirect output into a file from a command line. Like this. \$\endgroup\$ Jul 13, 2019 at 13:14
  • \$\begingroup\$ @AndriyMakukha: I believe I've addressed all the problems. I found a way to produce all the required output without much runtime cost. \$\endgroup\$
    – recursive
    Jul 13, 2019 at 13:41
  • \$\begingroup\$ This output is blazing fast! Very nice. I modified your program to also print frequency counts, as other solutions do. \$\endgroup\$ Jul 13, 2019 at 14:25
1
\$\begingroup\$

Ruby 2.7.0-preview1 with tally

The latest version of Ruby has a new method called tally. From the release notes:

Enumerable#tally is added. It counts the occurrence of each element.

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

This almost solves the entire task for us. We just need to read the file first and find the max later.

Here's the whole thing:

k = ARGV.shift.to_i

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

edit: Added k as an command line argument

It can be run with ruby k filename.rb input.txt using the 2.7.0-preview1 version of Ruby. This can be downloaded from various links on release notes page, or installed with rbenv using rbenv install 2.7.0-dev.

Example run on my own beat-up, old computer:

$ 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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I installed Ruby from sources. It runs roughly as fast as on your machine (15 seconds vs 17). \$\endgroup\$ Jul 17, 2019 at 7:09
1
\$\begingroup\$

AWK + sort

Just for the sake of completeness, here are two solutions that work best for different versions of AWK.

This one works best with Michael Brennan's AWK (both mawk-2 and mawk 1.3.4). It outperforms GNU awk by a factor of x7.5.

mawk -v RS="[^A-Za-z]+" '
{
    freq[tolower($0)]++;
}
END {
    for (word in freq)
        print(freq[word] " " word)
}
' filename | sort -rn | head -10

This version works best for the "one true awk" (nawk) and GNU awk (gawk).

awk -v FS="[^a-zA-Z]+" '
{
    for (i=1; i<=NF; i++)
        freq[tolower($i)]++;
}
END {
    for (word in freq)
        print(freq[word] " " word)
}
' filename | sort -rn | head -10

P.S. Bounty to anyone, who can find even faster AWK solution.

\$\endgroup\$
2
  • \$\begingroup\$ I feel there should be a perl solution that is as fast as any awk solution. \$\endgroup\$
    – user9207
    Feb 24, 2020 at 21:43
  • \$\begingroup\$ @Anush, feel free to post one. I can test it. But I have a feeling that Perl will be slower than Python. \$\endgroup\$ Feb 25, 2020 at 3:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.