摘要：本文介绍一道简单的面试题（统计不同单词的出现频率），用多种语言实现并对比它们的性能。每种语言都提供了符合习惯的简单解法，以及通过性能分析得到的更优解法。

过去几年里我主持过许多编程面试，其中一道我喜欢问的题目是：

请编写一个程序，从标准输入统计不同单词的出现频率，然后按频率从高到低打印单词及其出现次数。例如，给定如下输入：

The foo the foo the
defenestration the

程序应输出如下内容：

the 4
foo 2
defenestration 1

我认为这是一道不错的面试题，因为它比FizzBuzz稍难一些，却又不会陷入“在这块白板上翻转二叉树”那种困境。这是程序员在实际工作中可能需要写脚本解决的典型问题，能够考察他们是否理解文件 I/O、哈希表（映射）以及如何使用所用语言的排序功能。排序部分有一点小技巧，因为大多数哈希表是无序的，即使有序，也是按键或插入顺序排序，而非按值排序。

当候选人给出基础解法后，你可以从各种角度深入追问：大小写怎么处理？标点呢？频率相同的两个单词如何排序？性能瓶颈可能在哪里？大 O 表现如何？内存占用是多少？处理 1GB 文件大概需要多久？如果是 1TB 还能行吗？等等。也可以往“软件工程”方向展开，讨论错误处理、可测试性、如何将其打造成健壮的命令行工具等。

基础解法是逐行读取文件，将每行转为小写、按单词切分，并在哈希表中统计频率。完成后，将哈希表转换为单词-计数对的列表，按计数从大到小排序并打印。

在 Python 中，使用普通 dict 的一种直观解法如下所示（已省略导入语句）：

counts = {}
for line in sys.stdin:
    words = line.lower().split()
    for word in words:
        counts[word] = counts.get(word, 0) + 1

pairs = sorted(counts.items(), key=lambda kv: kv[1], reverse=True)
for word, count in pairs:
    print(word, count)

如果候选人是 Python 资深用户，可能会用到collections.defaultdict甚至collections.Counter——后者的代码见下文。遇到这种情况，我会问他们其底层原理是什么，或者如何用普通字典来实现。

顺便一提，这道题在几十年前曾引发两位计算机科学家之间的“巫师对决”。1986 年，Jon Bentley 请 Donald Knuth 用这道题来展示“文学编程”，Knuth 为此写出了长达十页、精妙绝伦的经典之作。随后，Unix 管道的发明者 Doug McIlroy 用 tr、sort 和 uniq 给出了一个单行的 Unix shell 版本作为回应。

图片来源 comic.browserling.com/97。

不管怎么说，我已经研究这个问题有一段时间了，很想看看用不同语言实现会是什么样子、运行速度如何，包括符合习惯的简单版本和更优化的版本。文中会包含大量代码片段，但每个版本的完整源码都在我的 benhoyt/countwords 仓库中。你也可以直接跳到性能测试结果一睹为快。

问题描述与约束条件

每个程序都必须从标准输入读取，并按频率从高到低打印以空格分隔的不同单词的出现次数。为了让各解法保持简单一致，我设定了以下（自我施加的）约束：

• 大小写：程序必须将单词统一转为小写，因此 “The the THE” 在输出中应显示为 “the 3”。
• 单词：以空白字符分隔的任何内容——忽略标点。这样做会让程序的实用性降低，但我不想让它变成一场分词之战。
• ASCII：空白处理和转小写操作只需支持 ASCII 即可，大多数优化版本都是这么做的。
• 排序：若两个单词频率相同，其在输出中的先后顺序不限。我会使用一个标准化脚本来校验输出是否正确。
• 线程：应在单机单线程下运行（尽管我在面试中也经常讨论并发）。
• 内存：不要将整个文件读入内存。逐行缓冲或以最大 64KB 的块为单位缓冲是可以的。不过，整个单词计数映射可以保留在内存中（我们假设输入是自然语言文本，而非充斥着随机唯一单词的数据）。
• 文本：假设输入文件为文本，且每行长度“合理”，短于缓冲区大小。
• 安全性：即使是优化版本，也尽量不使用不安全的语言特性，不要下沉到汇编层面。
• 哈希：不要自己实现哈希表（优化版 C 语言除外）。
• 标准库：仅使用各语言标准库提供的函数。

我们的测试输入文件是钦定版圣经文本重复拼接十次的结果。该文本来自 Gutenberg.org，我将智能引号替换为 ASCII 引号，并用 cat 将其复制十倍，得到 43MB 的基准输入文件。

那么，开始写代码吧！下面的解法按我实现的先后顺序排列。

Python

符合 Python 习惯的版本可能会使用 collections.Counter。Python 的 collections 库非常好用——感谢 Raymond Hettinger！这已经是最简洁的写法了：

simple.py

counts = collections.Counter()
for line in sys.stdin:
    words = line.lower().split()
    counts.update(words)

for word, count in counts.most_common():
    print(word, count)

这个版本支持 Unicode，也很可能是我在“实际开发”中会写的代码。它其实相当高效，因为所有底层操作都是用 C 实现的：读取文件、转小写并按空白切分、更新计数器，以及 Counter.most_common 所做的排序。

但我们来试着优化一下！Python 自带名为 cProfile 的性能分析模块。用起来很简单——只需用 python3 -m cProfile 来运行程序即可。我已注释掉最后的 print 调用，以免分析输出与程序输出混在一起——反正这部分开销可以忽略不计。

$ python3 -m cProfile -s tottime simple.py <kjvbible_x10.txt
         6997799 function calls (6997787 primitive calls) in 3.872 seconds
   Ordered by: internal time
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   998170    1.361    0.000    1.361    0.000 {built-in method _collections._count_elements}

从中可以看出几点：

• 998,170 是输入文件的行数，由于我们逐行读取，主循环中的函数调用和 Python 循环执行了这么多次。
• 在 simple.py 本身上花费的大量时间表明执行 Python 字节码相对较慢——主循环是纯 Python 代码，同样执行了 998,170 次。
• str.split 相对较慢，可能是因为它需要分配和复制大量字符串。
• Counter.update 会调用 isinstance，累积起来开销也不小。

我们主要需要做的是减少主 Python 循环的执行次数，从而减少对这些函数的调用次数。因此我们改为按 64KB 的块来读取：

optimized.py

counts = collections.Counter()
remaining = ''
while True:
    chunk = remaining + sys.stdin.read(64*1024)
    if not chunk:
        break
    last_lf = chunk.rfind('\n')
    if last_lf == -1:
        remaining = ''
    else:
        remaining = chunk[last_lf+1:]
        chunk = chunk[:last_lf]
    counts.update(chunk.lower().split())

for word, count in counts.most_common():
    print(word, count)

这样，主循环不再是一次处理 42 个字符（平均行长度），而是一次处理 65,536 个字符。我们读取和处理的字节总数不变，但大部分工作现在是在 C 层面完成，而非在 Python 循环中。

Go

符合 Go 习惯的简单版本可能会使用 bufio.Scanner，并以 ScanWords 作为切分函数。Go 没有类似 Python collection.Counter 的东西，但用 map[string]int 来计数，再用单词-计数对的切片来排序就很简单：

simple.go

func main() {
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Split(bufio.ScanWords)
    counts := make(map[string]int)
    for scanner.Scan() {
        word := strings.ToLower(scanner.Text())
        counts[word]++
    }
    // ... sort and print ...
}

Go 的简单版本比 Python 的简单版本快得多，但仅比 Python 的优化版本快一点。

为了提升扫描效率，我们将在扫描单词的同时将其转为 ASCII 小写。为了减少内存分配，我们将使用 map[string]*int 而非 map[string]int，这样每个不同单词只需分配一次，而不是每次计数递增都分配。

optimized.go

func main() {
    var word []byte
    buf := make([]byte, 64*1024)
    counts := make(map[string]*int)
    for {
        n, err := os.Stdin.Read(buf)
        if err != nil && err != io.EOF {
            fmt.Fprintln(os.Stderr, err)
            os.Exit(1)
        }
        if n == 0 {
            break
        }
        for i := 0; i < n; i++ {
            c := buf[i]
            if c <= ' ' {
                if len(word) > 0 {
                    increment(counts, word)
                    word = word[:0]
                }
                continue
            }
            if c >= 'A' && c <= 'Z' {
                c = c + ('a' - 'A')
            }
            word = append(word, c)
        }
    }
    // ...
}

C++

自上次认真使用 C++ 以来，它已经有了长足的发展：C++11 带来了许多好东西，随后 C++14、17 和 20 又增加了更多。这是我写的简单版本：

simple.cpp

int main() {
    std::string word;
    std::unordered_map<std::string, int> counts;
    while (std::cin >> word) {
        std::transform(word.begin(), word.end(), word.begin(),
            [](unsigned char c){ return std::tolower(c); });
        ++counts[word];
    }
    // ... sort and print ...
}

优化时，首先要做的是开启优化选项进行编译（g++ -O2）。在程序开头念一句“咒语”可以禁用每次 I/O 操作后与 C 标准 I/O 函数的同步，这一行就能让速度提升近一倍：

ios::sync_with_stdio(false);

C

C 是一头永远不会消亡的美丽野兽：快速、不安全、简单。遗憾的是，C 标准库中没有哈希表数据结构。不过 libc 提供了 hcreate 和 hsearch 哈希表函数，因此我们破例使用这些属于 libc 但不属于标准库的函数。

simple.c

#define MAX_UNIQUES 60000
typedef struct { char *word; int count; } count;
int cmp_count(const void *p1, const void *p2) { /* ... */ }
int main() {
    count *words = calloc(MAX_UNIQUES, sizeof(count));
    hcreate(MAX_UNIQUES);
    char word[101];
    while (scanf("%100s", word) != EOF) {
        for (char *p = word; *p; p++) *p = tolower(*p);
        // hsearch FIND / ENTER ...
    }
    // qsort and print
}

不出所料，分析显示 scanf 是主要的性能瓶颈，其次是 hsearch。因此接下来我们要在优化上做得更极致一些。我想重点关注三件事：分块读取文件、只处理一遍字节，以及使用快速的 FNV-1 哈希函数实现自己的哈希表。

optimized.c

#define BUF_SIZE 65536
#define HASH_LEN 65536
#define FNV_OFFSET 14695981039346656037UL
#define FNV_PRIME 1099511628211UL
typedef struct { char *word; int word_len; int count; } count;
void increment(char *word, int word_len, uint64_t hash) { /* linear probing */ }
int main() {
    table = calloc(HASH_LEN, sizeof(count));
    char buf[BUF_SIZE];
    // fread in chunks, find last space, tokenize, lowercase and hash as we go
    // increment, then qsort and print
}

AWK

AWK 其实非常适合这项任务：逐行读取并解析为空格分隔的单词正是它的拿手好戏。AWK 做不到（不借助 Gawk 特有功能的话）的一件事是排序，因此我使用 AWK 的管道操作符将输出通过 sort 进行排序。

simple.awk

{
    for (i = 1; i <= NF; i++)
        counts[tolower($i)]++
}
END {
    for (k in counts)
        print k, counts[k] | "sort -nr -k2"
}

在优化版本中，我做的一个小调整是将 tolower 改为每行调用一次，而不是每个单词调用一次。

optimized.awk

{
    $0 = tolower($0)
    for (i = 1; i <= NF; i++)
        counts[$i]++
}

我们可以使用 gawk -b 来运行它，这会让 Gawk 进入“字节”模式，从而使用 ASCII 而非 UTF-8。另一个“优化”是改用 mawk 运行，它是比 gawk 更快的 AWK 解释器。

Forth

Forth 是我学的第一门编程语言，因此我决定尝试用 Gforth 写一个 Forth 版本。

simple.fs

200 constant max-line
create line max-line allot
wordlist constant counts
variable num-uniques  0 num-uniques !
: to-lower ( C -- c ) dup [char] A [ char Z 1+ ] literal within if 32 + then ;
: count-word ( addr u -- ) 2dup counts search-wordlist if >body 1 swap +! 2drop else 2dup lower-in-place ['] create execute-parsing 1 , 1 num-uniques +! then ;
: process-input ( -- ) begin parse-name dup while count-word repeat 2drop ;

在优化方面，事实证明只需将 gforth 换成 gforth-fast，就能神奇地提升速度。

optimized.fs

15 :noname to hashbits hashdouble ; execute
65536 constant buf-size
create buf buf-size allot
wordlist constant counts
: count-word ( c-addr u -- ) 2dup counts find-name-in dup if >body 1 swap +! 2drop else drop nextname create 1 , 1 num-uniques +! then ;
: process-string ( -- ) begin parse-name dup while count-word repeat 2drop ;

Rust

我是 Andrew Gallant 开发的优秀代码搜索工具 ripgrep 的重度用户，我知道他非常推崇 Rust（也热衷于优化），因此在发表本文前，我请他帮忙写一个 Rust 版本。

rust/simple/main.rs

fn main() {
    if let Err(err) = try_main() {
        eprintln!("{}", err);
        std::process::exit(1);
    }
}
fn try_main() -> Result<(), Box<dyn Error>> {
    let stdin = io::stdin();
    let stdin = io::BufReader::new(stdin.lock());
    let mut counts: HashMap<String, u64> = HashMap::new();
    for result in stdin.lines() {
        let line = result?;
        for word in line.split_whitespace() {
            let canon = word.to_lowercase();
            *counts.entry(canon).or_insert(0) += 1;
        }
    }
    let mut ordered: Vec<(String, u64)> = counts.into_iter().collect();
    ordered.sort_by(|&(_, cnt1), &(_, cnt2)| cnt1.cmp(&cnt2).reverse());
    for (word, count) in ordered {
        writeln!(io::stdout(), "{} {}", word, count)?;
    }
    Ok(())
}

rust/optimized/main.rs

fn try_main() -> Result<(), Box<dyn Error>> {
    let stdin = io::stdin();
    let mut stdin = stdin.lock();
    let mut counts: HashMap<Vec<u8>, u64> = HashMap::default();
    let mut buf = vec![0; 64 * (1 << 10)];
    let mut offset = 0;
    let mut start = None;
    loop {
        let nread = stdin.read(&mut buf[offset..])?;
        if nread == 0 { break; }
        // lowercase, split on space/newline, increment
    }
    let mut ordered: Vec<(Vec<u8>, u64)> = counts.into_iter().collect();
    ordered.sort_by(|&(_, cnt1), &(_, cnt2)| cnt1.cmp(&cnt2).reverse());
    for (word, count) in ordered {
        writeln!(io::stdout(), "{} {}", std::str::from_utf8(&word)?, count)?;
    }
    Ok(())
}

Unix shell

我们来试试仅用基础 Unix 命令行工具的版本——这本质上就是 Doug McIlroy 的解法：

tr 'A-Z' 'a-z' | tr -s ' ' '\n' | sort | uniq -c | sort -nr

它相当慢，部分原因在于它必须一次性对整个文件进行排序，而不是使用哈希表来计数。不过，令我惊讶的是，如果将第一个 sort 的区域设置为 C（仅 ASCII），速度会提升 5 倍之多。

tr 'A-Z' 'a-z' | tr -s ' ' '\n' | LC_ALL=C sort -S 2G | uniq -c | \
    sort -nr

其他语言

许多读者为 benhoyt/countwords 仓库贡献了其他流行语言的实现——感谢大家！（请注意，我已不再接受新的贡献。）

• Bash：Jesse Hathaway - 未纳入基准测试，耗时超过 2 分钟
• C#：John Taylor、Yuriy Ostapenko 和 Osman Turan
• C++ 优化版：Jussi Pakkanen、Adev、Nathan Myers
• Common Lisp：Brad Svercl
• Crystal：Andrea Manzini
• D：Ross Lonstein
• F#：Yuriy Ostapenko
• Go：Miguel Angel
• Haskell：Adrien Glauser
• Java：Iulian Pleșoianu
• JavaScript：Dani Biró 和 Flo Hinze
• Julia：Alessandro Melis
• Kotlin：Kazik Pogoda
• Lua：Flemming Madsen
• Nim：csterritt 和 euantorano
• OCaml：doesntgolf
• Perl：Charles Randall
• PHP：Max Semenik
• Ruby：Bill Mill
• Rust：Andrew Gallant
• Swift：Daniel Müllenborn
• Tcl：William Ross
• Zig：ifreund、matu3ba 和 ansingh

性能结果与心得

以下是在我的笔记本电脑（64 位 Linux，配备 SSD，使用这些版本）上运行这些程序的性能数据。每个测试运行五次，取最短时间作为结果（见 benchmark.py）。每次运行基本等同于执行如下命令：

time $PROGRAM <kjvbible_x10.txt >/dev/null

时间以秒为单位，数值越小越好，列表按简单版本的执行时间从快到慢排序。（请注意，grep 和 wc 实际上并未解决词频统计问题，仅作对比参考。）

我们能从中学到什么？以下几点想法：

• 我认为最能说明问题的是符合习惯的简单版本，这才是程序员在实际工作中最可能写出的代码。
• 你几乎肯定不应该写那个优化版的 C 版本，除非你正在编写新的 GNU wordfreq 工具之类的。它太容易出错了。如果你想在安全的语言中获得高性能版本，我推荐 Go 或 Rust。
• 如果你只是需要一个快速的解决方案（这很可能是常态），Python 和 AWK 在这类文本处理上非常出色。
• C++ 模板在性能分析器中产生的错误信息和函数名极其难看，几乎无法阅读。
• 我仍然认为这道面试题作为编程题很不错，不过显然我不会期望候选人在白板上写出其中任何一个优化解法。
• 我们通常认为 I/O 开销很大，但在这里 I/O 并非瓶颈。在基准测试中，文件很可能已被缓存，但即便没有，如今硬盘的读取速度也已经非常快。分词和哈希表操作才是真正的瓶颈，而且差距巨大。

这绝对是一次有趣的实践！我对优化热点、使用 Valgrind 性能分析器学到了不少，还时隔多年第一次写了 Forth 代码。

欢迎告诉我你的想法或反馈，或提出改进建议（可查看 Hacker News、programming Reddit 和 Lobsters 上的讨论）。