要約：シンプルな面接問題（単語ごとの出現回数を数える）を紹介し、さまざまな言語で解いて性能を比較します。各言語について、シンプルで慣用的な解法と、プロファイリングによるより最適化されたアプローチの両方を紹介しています。

ここ数年、コーディング面接を数多く実施してきましたが、その中で私がよく出す質問の一つがこれです：

標準入力から単語ごとの出現回数を数え、最も頻度の高いものから順に、単語とその回数を出力するプログラムを書いてください。たとえば、次のような入力が与えられた場合：

The foo the foo the
defenestration the

プログラムは次のように出力すべきです：

the 4
foo 2
defenestration 1

この問題はFizzBuzzよりは少し難しいものの、「ホワイトボードで二分木を反転せよ」といった類の問題が抱える欠点がないため、良い面接問題だと思っています。現実でもプログラマーがスクリプトを書くことになりそうな内容ですし、ファイルI/O、ハッシュテーブル（マップ）、そして言語のソート機能の使い方を理解しているかどうかが分かります。ソートの部分に少しトリッキーな点があるのは、ほとんどのハッシュテーブルが順序を持たず、持っていたとしてもキー順や挿入順であって、値順ではないからです。

候補者が基本的な解法を書けた後は、さまざまな方向に話を広げられます。大文字・小文字はどうするか？句読点は？同じ頻度の単語はどう並べるか？性能のボトルネックはどこになりそうか？計算量は？メモリ使用量は？1GBのファイルを処理するのにどのくらいかかりそうか？1TBでも同じ解法は通用するか？といった具合です。あるいは「ソフトウェアエンジニアリング」的な方向に進めて、エラーハンドリングやテスト容易性、堅牢なコマンドラインユーティリティ化などについて議論することもできます。

基本的な解法は、ファイルを1行ずつ読み込み、小文字に変換し、各行を単語に分割して、ハッシュテーブルで出現回数を数えるというものです。処理が終わったら、ハッシュテーブルを単語と回数のペアのリストに変換し、回数でソートして（大きい順）、出力します。

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にこの問題で「文芸的プログラミング」を披露するよう依頼し、Knuthは見事な10ページにわたるKnuthらしい傑作を作り上げました。すると、Unixパイプの発明者であるDoug McIlroyが、tr、sort、uniqを使ったワンライナーのUnixシェル版で応酬したのです。

画像クレジット comic.browserling.com/97。

いずれにしても、私はしばらくこの問題で遊んでいて、さまざまな言語でプログラムがどうなるか、そしてシンプルで慣用的な解法とより最適化されたバージョンのそれぞれで、どれくらい速く動くのかを見てみたいと思いました。記事中では大きなコード断片を載せていますが、各バージョンの完全なソースコードは私のbenhoyt/countwordsリポジトリにあります。もちろん、手っ取り早く性能結果だけ見ても構いません。

問題の定義と制約

各プログラムは標準入力から読み込み、空白で区切られた単語ごとの出現回数を、最も頻度の高いものから低いものへと順に出力しなければなりません。解法をシンプルかつ一貫したものに保つため、以下の（自己課した）制約を設けています：

• 大文字・小文字：単語は小文字に正規化しなければなりません。たとえば「The the THE」は出力では「the 3」となるべきです。
• 単語：空白で区切られたものはすべて単語とみなします――句読点は無視します。これでプログラムの実用性は下がりますが、トークン化の争いにしたくはありません。
• ASCII：空白の処理や小文字化はASCIIのみをサポートすればよいことにします。最適化版のほとんどはそうしています。
• 順序：2つの単語の頻度が同じ場合、出力上の順序は問いません。正しい出力を保証するために正規化スクリプトを使っています。
• スレッド：単一マシン上のシングルスレッドで動作すること（ただし面接では並行性について議論することもよくあります）。
• メモリ：ファイル全体をメモリに読み込まないこと。1行ずつバッファリングするか、最大64KBのチャンクで読み込むのは許容します。ただし、単語カウントのマップ全体をメモリに保持するのは構いません（入力はランダムなユニーク単語の羅列ではなく、自然言語のテキストであると想定しています）。
• テキスト：入力ファイルはテキストであり、行の長さはバッファサイズより短い「妥当な」長さであると想定します。
• 安全性：最適化版であっても、可能な限り言語のunsafeな機能は使わず、アセンブリにまで落とさないようにします。
• ハッシュ：自作のハッシュテーブルは使わないこと（最適化されたCバージョンを除く）。
• 標準ライブラリ：言語の標準ライブラリの機能のみを使うこと。

テスト用の入力ファイルには、欽定訳聖書（King James Bible）のテキストを10回連結したものを使います。Gutenberg.orgから入手し、スマートクォートをASCIIのクォート文字に置き換え、catで10倍にして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は入力の行数で、1行ずつ読み込んでいるため、関数呼び出しや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)

1回あたり平均42文字（平均行長）で処理していたメインループが、今回は65,536文字単位での処理になります。読み込んで処理するバイト数は同じですが、そのほとんどをPythonループではなくCで処理するようになりました。

Go

シンプルで慣用的なGo版なら、おそらく分割関数としてScanWordsを使ったbufio.Scannerを使うでしょう。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++は大きく進歩しました。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のstdio関数との同期を無効にできるおまじないがあります。この一行で実行速度がほぼ2倍になります：

ios::sync_with_stdio(false);

C

Cは決して滅びない美しい野獣です。速く、安全ではなく、シンプルです。残念ながらCの標準ライブラリにはハッシュテーブルのデータ構造がありません。ただしlibcにはhcreateとhsearchというハッシュテーブル関数があるので、今回は小さな例外として、stdlibではないものの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が重いことが分かります。そこで、ここからは少しクレイジーに最適化していきます。次の3点に絞ります。ファイルをチャンクで読むこと、バイト列を一度だけ処理すること、そして高速な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を「バイト」モードにしてUTF-8の代わりにASCIIを使うようにします。もう一つの「最適化」は、gawkより高速なAWKインタプリタであるmawkで実行することです。

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シェル

基本的な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

性能結果と学び

以下は、これらのプログラムを私のノートPC（SSD搭載の64ビットLinuxで、これらのバージョンを使用）で実行した性能数値です。各テストを5回実行し、最短時間を結果として採用しています（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での議論も参照してください）。