WordCount:McIlroy的解决方案效率如何？

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？它看起来对我很好.关于sort | 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/

Answer 2

Doug McIlroy 的解决方案的时间复杂度为 O(T log T)，其中 T 是单词总数。这是由于第一个sort.

为了比较，以下是同一问题的四种更快的解决方案：

这是一个 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 中更复杂算法的糟糕实现很容易比他的管道运行得慢得多（我已经目睹了这一点）。