摘要：本文將介紹一道簡單的面試題目（統計不重複單字的出現次數），以多種語言實作解答，並比較它們的效能。針對每種語言，我都提供了一個簡潔且符合慣用寫法的解法，以及一個透過效能分析進一步最佳化的版本。

過去幾年我進行過許多程式面試，其中一道我很喜歡出的題目是：

請撰寫一個程式，從標準輸入讀取資料，統計其中每個不重複單字的出現次數，然後依照出現次數由高至低依序列印出單字與其出現次數。例如，給定以下輸入：

The foo the foo the
defenestration the

程式應印出如下結果：

the 4
foo 2
defenestration 1

我認為這是一道不錯的面試題，因為它比 FizzBuzz 稍微難一些，卻不會有「請在白板上反轉二元樹」那種問題。它是那種程式設計師在現實生活中可能真的會寫個小工具來處理的題目，也能看出應試者是否理解檔案 I/O、雜湊表（map），以及如何運用該語言的排序功能。排序的部分有一點小陷阱，因為大多數雜湊表本身是無序的，即使有序，也是依鍵或插入順序排序，而非依數值排序。

當應試者完成基本解法後，你可以往各種方向深入探討：大小寫要怎麼處理？標點符號呢？如果兩個單字出現次數相同，要怎麼排序？效能瓶頸最可能在哪裡？以 Big-O 來看表現如何？記憶體用量呢？處理一個 1GB 的檔案大概需要多久？如果是 1TB 呢，還能應付嗎？等等。或者，也可以往「軟體工程」的方向聊，談談錯誤處理、可測試性、如何將它打造成一個穩健的命令列工具等等。

一個基本的解法是逐行讀取檔案，將每一行轉為小寫、切成單字，然後用雜湊表統計每個單字的出現次數。完成後，再將雜湊表轉換為單字—次數的配對清單，依次數由大到小排序後印出。

在 Python 中，若使用一般的 dict，一個直覺的解法看起來會像這樣（省略 import）：

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 以「文學程式設計（literate programming）」來展示這題的解法，Knuth 於是寫出了一篇精緻的、長達十頁、充滿 Knuth 個人風格的經典之作。接著，Unix 管線（pipeline）的發明者 Doug McIlroy 則用 tr、sort 與 uniq 回敬了一個一行搞定的 Unix shell 版本。

圖片來源 comic.browserling.com/97。

總之，我玩這道題目已經有一段時間了，一直想看看用各種語言寫出來的程式會長什麼樣子，以及執行速度有多快——包括符合慣用寫法的簡單版本，以及更進一步最佳化的版本。文章中會包含大量的程式碼片段，但每個版本的完整原始碼都放在我的 benhoyt/countwords 儲存庫中。或者，你也可以直接跳到效能測試結果。

題目說明與限制條件

每個程式都必須從標準輸入讀取資料，並依照出現次數由高到低印出以空白分隔的不重複單字及其出現次數。為了讓解法保持簡單且一致，我自行訂定了以下限制條件：

• 大小寫：程式必須將單字正規化為小寫，因此「The the THE」在輸出中應顯示為「the 3」。
• 單字：以空白字元分隔的任何內容皆視為單字——忽略標點符號。這會讓程式的實用性降低，但我不想讓這變成一場分詞（tokenization）大戰。
• ASCII：僅需支援 ASCII 的空白字元處理與轉小寫操作即可。大多數最佳化版本也都是這麼做的。
• 排序：如果兩個單字的出現次數相同，它們在輸出中的先後順序不限。我會使用正規化腳本來確保輸出結果正確。
• 執行緒：程式應在單機上以單執行緒執行（雖然我在面試中也常會討論併發處理）。
• 記憶體：不要將整個檔案讀進記憶體。逐行緩衝或以區塊為單位讀取是可接受的，緩衝區大小上限為 64KB。話雖如此，將整個單字計數表保留在記憶體中是沒問題的（我們假設輸入是自然語言的文字，而非充滿隨機不重複單字的資料）。
• 文字：假設輸入檔案為文字檔，且每一行的長度都在「合理」範圍內，不會超過緩衝區大小。
• 安全性：即使是最佳化版本，也盡量不要使用不安全的語言特性，也不要直接寫組合語言。
• 雜湊：不要自己實作雜湊表（最佳化的 C 版本除外）。
• 標準函式庫：僅能使用該語言標準函式庫提供的功能。

我們的測試輸入檔是將《欽定版聖經》（King James Bible）的全文串接十次而成。我是從 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 bytecode 相對來說有多慢——主迴圈是純 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 來計數，再用單字—次數配對的 slice 來做排序，其實也很簡單：

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++ 已經進步很多：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）。還有一個神奇的咒語，只要在程式開頭加上，就能關閉與 C stdio 函式在每次 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 進入「bytes」模式，改用 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-fast 而非 gforth 來執行，就能神奇地提升速度。

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 實際上並未解決單字計數問題，僅作為對照基準。）

我們能從這一切學到什麼？以下有幾點想法：

• 我認為最能說明問題的是那些簡潔、符合慣用寫法的版本。這才是程式設計師在現實生活中最可能寫出的程式碼。
• 除非你正在寫一個新的 GNU wordfreq 工具之類的東西，否則你幾乎肯定不該寫那種最佳化的 C 版本。它實在太容易出錯了。如果你想要一個用安全語言寫成、又夠快的版本，我會推薦 Go 或 Rust。
• 如果你只是需要一個快速的解決方案（這通常就是實際情況），Python 和 AWK 在這類文字處理上表現得非常出色。
• C++ 樣板產生的錯誤訊息和在效能分析器中的函式名稱實在慘不忍睹，幾乎無法閱讀。
• 我仍然認為這道面試題作為程式設計考題相當不錯，不過顯然我不會期望應試者在白板上寫出那些最佳化版本。
• 我們通常認為 I/O 很昂貴，但在這個例子中，I/O 並不是瓶頸。以測試的情況來說，檔案很可能已經被快取了，但即使沒有，如今硬碟的讀取速度也非常快。分詞與雜湊表操作才是真正的瓶頸所在。

這絕對是一次有趣的練習！我學到了不少關於最佳化熱點、使用 Valgrind 效能分析器的知識，而且睽違多年後再次寫了 Forth 程式。

歡迎告訴我你的想法或回饋，或是提出改進建議（可參考 Hacker News、programming Reddit 與 Lobsters 上的討論）。