This is a classic problem that got some resonance in 1986, when Donald Knuth implemented a fast solution with hash tries in an 8-pages-long program to illustrate his literate programming technique, while Doug McIlroy, the godfather of Unix pipes, responded with a one-liner, that was not as quick, but got the job done:
tr -cs A-Za-z '\n' | tr A-Z a-z | sort | uniq -c | sort -rn | sed 10q
Of course, McIlroy's solution has time complexity O(N log N), where N is a total number of words. There are much faster solutions. For example:
Here is a C++ implementation with the upper bound time complexity O((N + k) log k), typically – nearly linear.
Below is a fast Python implementation using hash dictionaries and heap with time complexity O(N + k log Q), where Q is a number of unique words:
import collections, re, sys
filename = sys.argv
k = int(sys.argv) if len(sys.argv)>2 else 10
text = open(filename).read()
counts = collections.Counter(re.findall('[a-z]+', text.lower()))
for i, w in counts.most_common(k):
CPU time comparison (in seconds):
C++ (prefix tree + heap) 5.659 44.730
Python (Counter) 10.314 100.487
Sheharyar (AWK + sort) 30.864 251.301
McIlroy (tr + sort + uniq) 60.531 690.906
- bible32 is Bible concatenated with itself 32 times (135 MB), bible256 – 256 times respectively (1.1 GB).
- Python scripts's non-linear slow down is caused purely by the fact that it processes files completely in memory, so the overheads are getting bigger for huge files.
- If there was a Unix tool that could construct a heap and pick n elements from top of the heap, the AWK solution could achieve near-linear time complexity, while currently it is O(N + Q log Q).