3 ms·
It wasn't a competition. As I remember it, Jon Bentley asked Knuth to write an introductory example of literate programming, and McIlroy to review it in somethi
by abecedarius 3y ago
It wasn't a competition. As I remember it, Jon Bentley asked Knuth to write an introductory example of literate programming, and McIlroy to review it in something like the way a literary critic would critique an essay. Both responses were thoughtful. I learned more from the Knuth, but then I was already familiar with the Unix philosophy.
To use the heap you still need to look up the words efficiently.
- bombcar 3y agoIt’s reprinted in Knuth collections so even he notes the point - there’s a time and place for everything. And one requires WEB and the other requires the entire Unix tool chain. (And the only reason the Unix critique is ever mentioned is because of the literate programming version. Which would programmatical archeologists love to find in 2525 - if man is still alive?)
- KRAKRISMOTT 3y ago> To use the heap you still need to look up the words efficiently. Why? Just split the text and put everything into the heap, the heap algorithm will maintain the sorted order by rebalancing during insertion
- abecedarius 3y agoThe textbook solution I assume you meant, to find the most common k elements of a list, uses an updatable priority queue (heap). This orders the (key, count) pairs by the count. But that's a separate question from how you look up the key (i.e. given a word, find the pair whose count you want to increment), which is what Knuth's hash tries were for here.
- KRAKRISMOTT 3y agoThanks for the clarification