长话短说：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有什么问题？我觉得它很好看。关于sort | uniq -c，这是一种非常缓慢的确定频率的方法吗？
几个注意事项：
tr应为线性时间（？）sort我不确定，但我认为这并不是那么糟糕uniq也应该是线性时间- 生成进程应该是线性时间（以进程数量为单位）
Unix脚本有一些线性运算和2个排序。它将是计算顺序O(n log(n))。
对于只取顶部N的Knuth算法：http://en.wikipedia.org/wiki/Selection_algorithm在算法的时间和空间复杂性方面，你可以有一些选择，但理论上，对于一些具有大量（不同）单词的典型示例，它们可以更快。
所以克努思可以更快。当然是因为英语词典的篇幅有限。它可以将log(n)转换为某个大常数，尽管可能会消耗大量内存。
但也许这个问题更适合https://cstheory.stackexchange.com/
为了进行比较，以下是同一问题的四种更快的解决方案：
这是一个C++实现，其上限时间复杂度为O（（T+N）log N），但实际上几乎是线性的，接近O（T+N log N）。
下面是一个快速Python实现。在内部，它使用哈希字典和堆，时间复杂度为O（T+N log Q），其中Q是唯一单词的数量：
import collections, re, sys
filename = sys.argv[1]
k = int(sys.argv[2]) if len(sys.argv)>2 else 10
reg = re.compile('[a-z]+')
counts = collections.Counter()
for line in open(filename):
counts.update(reg.findall(line.lower()))
for i, w in counts.most_common(k):
print(i, w)
以及另一个使用AWK的Unix shell解决方案。它具有时间复杂性O（T+Q log Q）:
awk -v FS="[^a-zA-Z]+" '
{
for (i=1; i<=NF; i++)
freq[tolower($i)]++;
}
END {
for (word in freq)
print(freq[word] " " word)
}
' | sort -rn | head -10
这是Anders Kaseorg在Rust中的一个极其快速的解决方案。
CPU时间比较（秒）：
bible32 bible256 Asymptotical
Rust (prefix tree) 0.632 5.284 O(?)
C++ (prefix tree + heap) 4.838 38.587 O((T + N) log N)
Python (Counter) 14.366 115.855 O(T + N log Q)
AWK + sort 21.548 176.411 O(T + Q log Q)
McIlroy (tr + sort + uniq) 60.531 690.906 O(T log T)
注：
- T>=Q，通常为Q>>N（N是一个小常数）
- bible32是圣经连接32次（135 MB），bible256–256次（1.1 GB）
- AWK的时间可能会因您使用的AWK版本而异（gawk、nawk或mawk）
正如你所看到的，McIlroy的解决方案运行速度大约是已知最快程序的100倍！然而，他的解决方案仍然非常优雅，易于调试，毕竟，它的性能也没有那么糟糕，除非你开始将其用于千兆字节的文件。C/C++或Haskell中更复杂算法的糟糕实现很容易比他的管道运行得慢得多（我亲眼目睹过）。