18
\$\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
C++ (trie) by ShreevatsaR            0.671          4.227          4.276
C (trie + bins) by Moogie            0.704          9.568          9.459
C (trie + list) by Moogie            0.767          6.051          82.306
C++ (hash trie) by ShreevatsaR       0.788          5.283          5.390
C (trie + sorted list) by Moogie     0.804          7.076          x
Rust (trie) by Anders Kaseorg        0.842          6.932          7.503
J by miles                           1.273          22.365         22.637
mawk-2 + sort                        2.763          28.488         29.329
mawk 1.3.4 + sort                    2.982          34.149         34.617
C# (trie) by recursive               3.722          25.378         24.771
C++ (trie + heap)                    4.145          42.631         72.138
APL (Dyalog Unicode) by Adám         7.680          x              x
Python (dict) by movatica            9.387          99.118         100.859
Python (Counter)                     10.547         102.822        103.930
Ruby (tally) by daniero              15.139         171.095        171.551
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  C++ (trie) by ShreevatsaR           300     Yes
 2  C++ (hash trie) by ShreevatsaR      368      x
 3  Rust (trie) by Anders Kaseorg       465     Yes
 4  C (trie + bins) by Moogie           552      x
 5  J by miles                         1248     Yes
 6  C# (trie) by recursive             1734      x
 7  mawk-2 + sort                      1772     Yes
 8  mawk 1.3.4 + sort                  2062     Yes
 9  C (trie + list) by Moogie          2182      x
10  C++ (trie + heap)                  3313      x
11  Python (dict) by movatica          6103     Yes
12  Python (Counter)                   6435     Yes
13  Ruby (tally) by daniero           10316     Yes
14  gawk + sort                       13317     Yes
15  McIlroy (tr + sort + uniq)        40970     Yes

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

Best program so far: here (second solution)

\$\endgroup\$
  • \$\begingroup\$ The score is just the time on Ulysses? It seems implied but it is not explicitly said \$\endgroup\$ – Post Rock Garf Hunter Jul 10 '19 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\$ – Andriy Makukha Jul 10 '19 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\$ – Post Rock Garf Hunter Jul 10 '19 at 13:49
  • 1
    \$\begingroup\$ @tsh That is my understanding: e.g. would be two words e and g \$\endgroup\$ – Moogie Jul 12 '19 at 4:20
  • 1
    \$\begingroup\$ @AndriyMakukha Ah, thanks. Those were just bugs; I fixed them. \$\endgroup\$ – Anders Kaseorg Jul 16 '19 at 6:52

11 Answers 11

6
\$\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\$
  • \$\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\$ – Andriy Makukha Jan 10 at 18:07
  • \$\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\$ – Andriy Makukha Jan 10 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\$ – ShreevatsaR Jan 10 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\$ – Andriy Makukha Jan 11 at 15:34
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\$
  • \$\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\$ – Andriy Makukha Jul 12 '19 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 '19 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\$ – Andriy Makukha Jul 12 '19 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\$ – Andriy Makukha Jul 12 '19 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 '19 at 17:28
4
\$\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 <andersk@mit.edu>"]
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\$
  • 1
    \$\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\$ – Andriy Makukha Jul 15 '19 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 '19 at 13:36
  • \$\begingroup\$ @Moogie I was already testing yours with -O3, and -Ofast doesn’t make a measurable difference. \$\endgroup\$ – Anders Kaseorg Jul 15 '19 at 13:42
  • \$\begingroup\$ @Moogie, I was compiling your code like gcc -O3 -march=native -mtune=native program.c. \$\endgroup\$ – Andriy Makukha Jul 15 '19 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 '19 at 20:50
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\$
  • \$\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\$ – Andriy Makukha Jul 10 '19 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 '19 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\$ – Andriy Makukha Jul 10 '19 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 '19 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\$ – Andriy Makukha Jul 11 '19 at 9:26
2
\$\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\$
  • \$\begingroup\$ Wow! 100,000 most frequent words from a 1 GB file in 11 seconds... This looks like some kind of magic trickery. \$\endgroup\$ – Andriy Makukha Jul 13 '19 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 '19 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 '19 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\$ – Andriy Makukha Jul 14 '19 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 '19 at 12:46
2
\$\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\$
  • \$\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\$ – Andriy Makukha Jul 27 '19 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 '19 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\$ – Andriy Makukha Jul 27 '19 at 12:51
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\$
  • 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 '19 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\$ – Andriy Makukha Jul 13 '19 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\$ – Andriy Makukha Jul 13 '19 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 '19 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\$
  • \$\begingroup\$ It returns not very sorted output for k=100,000: 12 eroilk 111 iennoa 10 yttelen 110 engyt. \$\endgroup\$ – Andriy Makukha Jul 12 '19 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 '19 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 '19 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\$
  • 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\$ – Andriy Makukha Jul 13 '19 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 '19 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\$ – Andriy Makukha Jul 13 '19 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 '19 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\$ – Andriy Makukha Jul 13 '19 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
    \$\begingroup\$ I installed Ruby from sources. It runs roughly as fast as on your machine (15 seconds vs 17). \$\endgroup\$ – Andriy Makukha Jul 17 '19 at 7:09
0
\$\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. Like to anyone, who can find even faster AWK solutions.

\$\endgroup\$
  • \$\begingroup\$ I feel there should be a perl solution that is as fast as any awk solution. \$\endgroup\$ – Anush 2 hours ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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