algorithm - 字数 : how inefficient is McIlroy's solution?

Question

长话短说:1986 年，一位面试官要求 Donald Knuth 编写一个程序，输入文本和数字 N，并列出按频率排序的 N 个最常用的词。 Knuth 编写了一个 10 页的 Pascal 程序，Douglas McIlroy 用以下 6 行 shell 脚本回复了该程序:

tr -cs A-Za-z '\n' |
tr A-Z a-z |
sort |
uniq -c |
sort -rn |
sed ${1}q

阅读全文 http://www.leancrew.com/all-this/2011/12/more-shell-less-egg/ .

当然，他们的目标截然不同:Knuth 展示了他的文学编程概念并从头开始构建所有内容，而 McIlroy 使用一些常见的 UNIX 实用程序来实现最短的源代码。

我的问题是:那有多糟糕？
(纯粹从运行时速度的角度来看，因为我很确定我们都同意 6 行代码比 10 页代码更容易理解/维护，无论是否有文化编程。)

我可以理解 sort -rn | sed ${1}q 可能不是提取常用词的最有效方法，但是 tr -sc A-za-z '\n' | 有什么问题？ tr A-Z a-z?对我来说看起来不错。关于排序 | uniq -c，这是一种非常慢的确定频率的方法吗？

一些注意事项:

• tr 应该是线性时间(？)
• sort 我不确定，但我假设它不是那个坏的
• uniq 也应该是线性时间
• 产卵过程应该是线性时间(在过程数中)

Answer 1

Unix 脚本有几个线性操作和 2 个排序。这将是计算顺序 O(n log(n))。

对于只取前 N 个的 Knuth 算法:http://en.wikipedia.org/wiki/Selection_algorithm您可以在算法的时间和空间复杂度方面有一些选择，但理论上对于一些具有大量(不同)单词的典型示例，它们可以更快。

所以 Knuth 可以更快。当然是因为英语词典的大小有限。它可以将 log(n) 转换为一些大常量，尽管可能会消耗大量内存。

但也许这个问题更适合 https://cstheory.stackexchange.com/