title: WordCount: how inefficient is McIlroy's solution?
body: <p>Long story short: in 1986 an interviewer asked Donald Knuth to write a program that takes a text and a number N in input, and lists the N most used words sorted by their frequencies. Knuth produced a 10-pages Pascal program, to which Douglas McIlroy replied with the following 6-lines shell script:</p>
  
  <pre><code>tr -cs A-Za-z '\n' |
  tr A-Z a-z |
  sort |
  uniq -c |
  sort -rn |
  sed ${1}q
  </code></pre>
  
  <p>Read the full story at <a href="http://www.leancrew.com/all-this/2011/12/more-shell-less-egg/">http://www.leancrew.com/all-this/2011/12/more-shell-less-egg/</a> .</p>
  
  <p>Of course they had very different goals: Knuth was showing his concepts of literate programming and built everything from scratch, while McIlroy used a few common UNIX utilities to achieve the shortest source code.</p>
  
  <p>My question is: how bad is that?<br>
  (Purely from a runtime-speed point of view, since I'm pretty sure we all agree that 6 lines of code is easier to understand/maintain than 10 pages, literate programming or not.)</p>
  
  <p>I can understand that <code>sort -rn | sed ${1}q</code> may not be the most efficient way to extract the common words, but what's wrong with <code>tr -sc A-za-z '\n' | tr A-Z a-z</code>? It looks pretty good to me. 
  About <code>sort | uniq -c</code>, is that a terribly slow way to determine the frequencies?</p>
  
  <p>A few considerations:</p>
  
  <ul>
  <li><code>tr</code> should be linear time (?)</li>
  <li><code>sort</code> I'm not sure of, but I'm assuming it's not <em>that</em> bad</li>
  <li><code>uniq</code> should be linear time too</li>
  <li>spawning processes should be linear time (in the number of processes)</li>
  </ul>