요약: 간단한 면접 문제(고유 단어의 빈도 세기)를 설명하고, 여러 언어로 해결한 뒤 언어별 성능을 비교한다. 각 언어마다 관용적이고 단순한 풀이와 프로파일링을 통한 최적화 풀이를 함께 담았다.

지난 몇 년간 코딩 면접을 많이 진행했는데, 자주 내는 질문 중 하나는 다음과 같다:

표준 입력에서 고유 단어들의 빈도를 세어, 가장 빈도가 높은 순으로 단어와 빈도를 함께 출력하는 프로그램을 작성하세요. 예를 들어 다음과 같은 입력이 주어지면:

The foo the foo the
defenestration the

프로그램은 다음과 같이 출력해야 합니다:

the 4
foo 2
defenestration 1

이 질문이 좋은 면접 문제라고 생각하는 이유는 FizzBuzz보다는 조금 더 풀기 어렵지만, “화이트보드에서 이진 트리를 뒤집어 보세요” 같은 문제는 아니기 때문이다. 실제로 프로그래머가 스크립트를 짜야 할 법한 종류의 일이고, 파일 입출력, 해시 테이블(맵), 그리고 해당 언어의 정렬 함수를 어떻게 다루는지 알 수 있다. 정렬 부분에 약간의 까다로움이 있는데, 대부분의 해시 테이블은 순서가 없고, 순서가 있더라도 키나 삽입 순서 기준이지 값 기준이 아니기 때문이다.

후보자가 기본적인 풀이를 완성하면 여러 방향으로 더 파고들 수 있다: 대소문자는 어떻게 할 건지? 구두점은? 빈도가 같은 두 단어는 어떤 순서로 정렬할 건지? 성능 병목은 어디일 가능성이 큰지? 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 파이프라인의 발명자인 Doug McIlroy가 tr, sort, uniq를 이용한 한 줄짜리 Unix 셸 버전으로 응수했다.

이미지 출처 comic.browserling.com/97.

어쨌든 나는 한동안 이 문제로 이것저것 실험을 해왔고, 여러 언어로 프로그램이 어떻게 생겼는지, 그리고 단순하고 관용적인 풀이와 최적화한 버전 각각에서 얼마나 빠르게 동작하는지 보고 싶었다. 글에는 코드 일부를 크게 인용했지만, 각 버전의 전체 소스는 내 benhoyt/countwords 저장소에 있다. 아니면 바로 성능 결과로 넘어가도 된다.

문제 정의와 제약 조건

각 프로그램은 표준 입력에서 읽어 고유한 공백 구분 단어들의 빈도를 가장 빈도가 높은 순부터 가장 낮은 순으로 출력해야 한다. 풀이를 단순하고 일관되게 유지하기 위해 내가 스스로 정한 제약 조건은 다음과 같다:

• 대소문자: 단어를 소문자로 정규화해야 하므로, “The the THE”는 출력에서 “the 3”으로 나타나야 한다.
• 단어: 공백으로 구분된 것이라면 무엇이든 단어로 본다 – 구두점은 무시한다. 이렇게 하면 프로그램의 실용성은 떨어지지만, 토큰화 논쟁으로 번지는 것을 피하고 싶었다.
• ASCII: 공백 처리와 소문자 변환은 ASCII만 지원해도 괜찮다. 최적화된 변형 중 대부분은 그렇게 한다.
• 순서: 두 단어의 빈도가 같을 경우 출력 순서는 상관없다. 출력이 올바른지 확인하기 위해 정규화 스크립트를 사용한다.
• 스레딩: 단일 머신에서 단일 스레드로 동작해야 한다 (면접에서는 종종 동시성을 함께 논의하지만).
• 메모리: 파일 전체를 메모리에 읽어들이지 않는다. 한 줄씩 버퍼링하거나, 최대 버퍼 크기를 64KB로 하여 청크 단위로 읽는 것은 괜찮다. 다만 단어 수 카운트 맵 전체를 메모리에 유지하는 것은 괜찮다고 본다 (입력은 무작위로 생성된 고유 단어로 가득한 데이터가 아니라 실제 언어의 텍스트라고 가정한다).
• 텍스트: 입력 파일은 텍스트이며, 각 줄 길이는 버퍼 크기보다 짧은 “합리적인” 길이라고 가정한다.
• 안전성: 최적화된 변형이라도 가급적 안전하지 않은 언어 기능은 사용하지 않고, 어셈블리로 내려가지 않는다.
• 해싱: 직접 해시 테이블을 구현하지 않는다 (최적화된 C 버전은 예외).
• 표준 라이브러리: 해당 언어의 표준 라이브러리 함수만 사용한다.

테스트 입력 파일은 King James 성경 텍스트를 열 번 이어 붙인 것이다. 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자씩 처리하게 되었다. 같은 바이트 수를 읽고 처리하지만, 이제 대부분을 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++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 함수와 동기화하는 것을 비활성화할 수 있다. 이 한 줄로 실행 속도가 거의 두 배 빨라진다:

ios::sync_with_stdio(false);

C

C는 절대 죽지 않는 아름다운 야수다: 빠르고, 안전하지 않으며, 단순하다. 안타깝게도 C 표준 라이브러리에는 해시 테이블 자료구조가 없다. 하지만 libc에는 hcreate와 hsearch 해시 테이블 함수가 있으므로, 이 libc 함수(엄밀히는 stdlib은 아니지만)는 예외적으로 사용하기로 하자.

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가 가장 잘하는 일이다. 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

성능 결과 및 교훈

아래는 내 노트북(SSD를 탑재한 64비트 Linux, 버전은 다음과 같다)에서 이 프로그램들을 실행한 성능 수치다. 각 테스트를 다섯 번 실행하고 최소 시간을 결과로 삼았다 (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에서의 토론 참고).