3 ms·
When did they hold the competition? I believe the textbook solution to this is using a heap.
by KRAKRISMOTT 3y ago
When did they hold the competition? I believe the textbook solution to this is using a heap.
- abecedarius 3y agoIt 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
- deleted 3y ago[deleted]
- donkeybeer 3y agoIt seems the date was 1986. What I find surprising is McIlroy's solution feels completely modern still, one could still solve the problem more or less in the same manner today when writing a command pipeline on a unix derived os. Even the names and syntax of the commands hasn't changed.