17

长话短说：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也应该是线性时间
  • 产卵进程应该是线性时间（进程数）
4

2 回答 2

8

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

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

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

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

于 2014-09-21T10:08:39.670 回答
6

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

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

这是一个具有上限时间复杂度 O((T + N) log N) 的 C++ 实现，但实际上 - 几乎是线性的，接近 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 中更复杂算法的错误实现很容易比他的管道运行得慢得多（我已经见证了这一点）。

于 2019-07-09T17:59:24.503 回答