C ++ (라 크 누스)

Knuth의 프로그램이 어떻게 작동하는지 궁금해서 그의 원래의 Pascal 프로그램을 C ++로 번역했습니다.

Knuth의 주요 목표는 속도가 아니라 웹 프로그래밍 시스템의 WEB 시스템을 설명하는 것이었지만,이 프로그램은 놀랍도록 경쟁력이 있으며 지금까지의 답변보다 빠른 솔루션을 제공합니다. 다음은 그의 프로그램을 번역 한 것입니다 (웹 프로그램의 해당 “섹션”번호는 ” {§24}” 와 같은 주석에 언급되어 있습니다 ).

#include <iostream>
#include <cassert>

// Adjust these parameters based on input size.
const int TRIE_SIZE = 800 * 1000; // Size of the hash table used for the trie.
const int ALPHA = 494441;  // An integer that's approximately (0.61803 * TRIE_SIZE), and relatively prime to T = TRIE_SIZE - 52.
const int kTolerance = TRIE_SIZE / 100;  // How many places to try, to find a new place for a "family" (=bunch of children).

typedef int32_t Pointer;  // [0..TRIE_SIZE), an index into the array of Nodes
typedef int8_t Char;  // We only care about 1..26 (plus two values), but there's no "int5_t".
typedef int32_t Count;  // The number of times a word has been encountered.
// These are 4 separate arrays in Knuth's implementation.
struct Node {
  Pointer link;  // From a parent node to its children's "header", or from a header back to parent.
  Pointer sibling;  // Previous sibling, cyclically. (From smallest child to header, and header to largest child.)
  Count count;  // The number of times this word has been encountered.
  Char ch;  // EMPTY, or 1..26, or HEADER. (For nodes with ch=EMPTY, the link/sibling/count fields mean nothing.)
} node[TRIE_SIZE + 1];
// Special values for `ch`: EMPTY (free, can insert child there) and HEADER (start of family).
const Char EMPTY = 0, HEADER = 27;

const Pointer T = TRIE_SIZE - 52;
Pointer x;  // The `n`th time we need a node, we'll start trying at x_n = (alpha * n) mod T. This holds current `x_n`.
// A header can only be in T (=TRIE_SIZE-52) positions namely [27..TRIE_SIZE-26].
// This transforms a "h" from range [0..T) to the above range namely [27..T+27).
Pointer rerange(Pointer n) {
  n = (n % T) + 27;
  // assert(27 <= n && n <= TRIE_SIZE - 26);
  return n;
}

// Convert trie node to string, by walking up the trie.
std::string word_for(Pointer p) {
  std::string word;
  while (p != 0) {
    Char c = node[p].ch;  // assert(1 <= c && c <= 26);
    word = static_cast<char>('a' - 1 + c) + word;
    // assert(node[p - c].ch == HEADER);
    p = (p - c) ? node[p - c].link : 0;
  }
  return word;
}

// Increment `x`, and declare `h` (the first position to try) and `last_h` (the last position to try). {§24}
#define PREPARE_X_H_LAST_H x = (x + ALPHA) % T; Pointer h = rerange(x); Pointer last_h = rerange(x + kTolerance);
// Increment `h`, being careful to account for `last_h` and wraparound. {§25}
#define INCR_H { if (h == last_h) { std::cerr << "Hit tolerance limit unfortunately" << std::endl; exit(1); } h = (h == TRIE_SIZE - 26) ? 27 : h + 1; }

// `p` has no children. Create `p`s family of children, with only child `c`. {§27}
Pointer create_child(Pointer p, int8_t c) {
  // Find `h` such that there's room for both header and child c.
  PREPARE_X_H_LAST_H;
  while (!(node[h].ch == EMPTY and node[h + c].ch == EMPTY)) INCR_H;
  // Now create the family, with header at h and child at h + c.
  node[h]     = {.link = p, .sibling = h + c, .count = 0, .ch = HEADER};
  node[h + c] = {.link = 0, .sibling = h,     .count = 0, .ch = c};
  node[p].link = h;
  return h + c;
}

// Move `p`'s family of children to a place where child `c` will also fit. {§29}
void move_family_for(const Pointer p, Char c) {
  // Part 1: Find such a place: need room for `c` and also all existing children. {§31}
  PREPARE_X_H_LAST_H;
  while (true) {
    INCR_H;
    if (node[h + c].ch != EMPTY) continue;
    Pointer r = node[p].link;
    int delta = h - r;  // We'd like to move each child by `delta`
    while (node[r + delta].ch == EMPTY and node[r].sibling != node[p].link) {
      r = node[r].sibling;
    }
    if (node[r + delta].ch == EMPTY) break;  // There's now space for everyone.
  }

  // Part 2: Now actually move the whole family to start at the new `h`.
  Pointer r = node[p].link;
  int delta = h - r;
  do {
    Pointer sibling = node[r].sibling;
    // Move node from current position (r) to new position (r + delta), and free up old position (r).
    node[r + delta] = {.ch = node[r].ch, .count = node[r].count, .link = node[r].link, .sibling = node[r].sibling + delta};
    if (node[r].link != 0) node[node[r].link].link = r + delta;
    node[r].ch = EMPTY;
    r = sibling;
  } while (node[r].ch != EMPTY);
}

// Advance `p` to its `c`th child. If necessary, add the child, or even move `p`'s family. {§21}
Pointer find_child(Pointer p, Char c) {
  // assert(1 <= c && c <= 26);
  if (p == 0) return c;  // Special case for first char.
  if (node[p].link == 0) return create_child(p, c);  // If `p` currently has *no* children.
  Pointer q = node[p].link + c;
  if (node[q].ch == c) return q;  // Easiest case: `p` already has a `c`th child.
  // Make sure we have room to insert a `c`th child for `p`, by moving its family if necessary.
  if (node[q].ch != EMPTY) {
    move_family_for(p, c);
    q = node[p].link + c;
  }
  // Insert child `c` into `p`'s family of children (at `q`), with correct siblings. {§28}
  Pointer h = node[p].link;
  while (node[h].sibling > q) h = node[h].sibling;
  node[q] = {.ch = c, .count = 0, .link = 0, .sibling = node[h].sibling};
  node[h].sibling = q;
  return q;
}

// Largest descendant. {§18}
Pointer last_suffix(Pointer p) {
  while (node[p].link != 0) p = node[node[p].link].sibling;
  return p;
}

// The largest count beyond which we'll put all words in the same (last) bucket.
// We do an insertion sort (potentially slow) in last bucket, so increase this if the program takes a long time to walk trie.
const int MAX_BUCKET = 10000;
Pointer sorted[MAX_BUCKET + 1];  // The head of each list.

// Records the count `n` of `p`, by inserting `p` in the list that starts at `sorted[n]`.
// Overwrites the value of node[p].sibling (uses the field to mean its successor in the `sorted` list).
void record_count(Pointer p) {
  // assert(node[p].ch != HEADER);
  // assert(node[p].ch != EMPTY);
  Count f = node[p].count;
  if (f == 0) return;
  if (f < MAX_BUCKET) {
    // Insert at head of list.
    node[p].sibling = sorted[f];
    sorted[f] = p;
  } else {
    Pointer r = sorted[MAX_BUCKET];
    if (node[p].count >= node[r].count) {
      // Insert at head of list
      node[p].sibling = r;
      sorted[MAX_BUCKET] = p;
    } else {
      // Find right place by count. This step can be SLOW if there are too many words with count >= MAX_BUCKET
      while (node[p].count < node[node[r].sibling].count) r = node[r].sibling;
      node[p].sibling = node[r].sibling;
      node[r].sibling = p;
    }
  }
}

// Walk the trie, going over all words in reverse-alphabetical order. {§37}
// Calls "record_count" for each word found.
void walk_trie() {
  // assert(node[0].ch == HEADER);
  Pointer p = node[0].sibling;
  while (p != 0) {
    Pointer q = node[p].sibling;  // Saving this, as `record_count(p)` will overwrite it.
    record_count(p);
    // Move down to last descendant of `q` if any, else up to parent of `q`.
    p = (node[q].ch == HEADER) ? node[q].link : last_suffix(q);
  }
}

int main(int, char** argv) {
  // Program startup
  std::ios::sync_with_stdio(false);

  // Set initial values {§19}
  for (Char i = 1; i <= 26; ++i) node[i] = {.ch = i, .count = 0, .link = 0, .sibling = i - 1};
  node[0] = {.ch = HEADER, .count = 0, .link = 0, .sibling = 26};

  // read in file contents
  FILE *fptr = fopen(argv[1], "rb");
  fseek(fptr, 0L, SEEK_END);
  long dataLength = ftell(fptr);
  rewind(fptr);
  char* data = (char*)malloc(dataLength);
  fread(data, 1, dataLength, fptr);
  if (fptr) fclose(fptr);

  // Loop over file contents: the bulk of the time is spent here.
  Pointer p = 0;
  for (int i = 0; i < dataLength; ++i) {
    Char c = (data[i] | 32) - 'a' + 1;  // 1 to 26, for 'a' to 'z' or 'A' to 'Z'
    if (1 <= c && c <= 26) {
      p = find_child(p, c);
    } else {
      ++node[p].count;
      p = 0;
    }
  }
  node[0].count = 0;

  walk_trie();

  const int max_words_to_print = atoi(argv[2]);
  int num_printed = 0;
  for (Count f = MAX_BUCKET; f >= 0 && num_printed <= max_words_to_print; --f) {
    for (Pointer p = sorted[f]; p != 0 && num_printed < max_words_to_print; p = node[p].sibling) {
      std::cout << word_for(p) << " " << node[p].count << std::endl;
      ++num_printed;
    }
  }

  return 0;
}

크 누스 프로그램과의 차이점 :

• 내가 크 누스의 4 개 배열을 결합 link, sibling, count및 ch(A)의 배열로struct Node (쉽게이 방법을 이해 찾기).
• 나는 문단의 프로그래밍 언어 (WEB- 스타일) 텍스트 번역을보다 일반적인 함수 호출 (및 두 개의 매크로)로 변경했다.
• 우리가 사용하므로, 표준 파스칼의 이상한 I / O 규칙 / 제한을 사용할 필요가 없습니다 fread및data[i] | 32 - 'a' 대신 파스칼 해결 방법으로, 여기에 다른 답변에서와 같이.
• 프로그램이 실행되는 동안 한계가 초과되면 (공간 부족) Knuth의 원래 프로그램은 이후 단어를 삭제하고 마지막에 메시지를 인쇄하여 우아하게 처리합니다. McIlroy가 “성경의 전체 텍스트를 처리 할 수 ​​없다고 Knuth의 해결책을 비판했다”고 말하는 것은 옳지 않은 일입니다. “성경에서 오류 상태는 무해하지 않습니다.) 나는 단순히 프로그램을 종료하는 더 시끄러운 접근 방식을 취했습니다.
• 이 프로그램은 상수 TRIE_SIZE를 선언하여 메모리 사용량을 제어합니다. (32767의 상수는 원래 요구 사항에 따라 선택되었습니다. “사용자는 20 페이지 기술 논문 (대략 50K 바이트 파일)에서 가장 자주 100 개의 단어를 찾을 수 있어야합니다.”) 테스트 입력이 현재 2 천만 배 더 커짐에 따라 25 배에서 800,000 개로 늘려야했습니다.)
• 줄의 마지막 인쇄를 위해, 우리는 단지 trie를 걷고 멍청한 (2 차적인) 문자열 추가를 할 수 있습니다.

그 외에도, 이것은 해시 트라이 / 팩 트리 데이터 구조 및 버킷 정렬을 사용하는 Knuth의 프로그램과 거의 동일하며 입력의 모든 문자를 반복하면서 Knuth의 파스칼 프로그램과 거의 동일한 작업을 수행합니다. 외부 알고리즘이나 데이터 구조 라이브러리를 사용하지 않으며 동일한 빈도의 단어가 알파벳 순서로 인쇄됩니다.

타이밍

로 컴파일

clang++ -std=c++17 -O2 ptrie-walktrie.cc

여기에서 가장 큰 테스트 사례 ( giganovel10 만 단어 요청)에서 실행하고 지금까지 게시 된 가장 빠른 프로그램과 비교할 때 약간 있지만 지속적으로 빠릅니다.

target/release/frequent:   4.809 ±   0.263 [ 4.45.. 5.62]        [... 4.63 ...  4.75 ...  4.88...]
ptrie-walktrie:            4.547 ±   0.164 [ 4.35.. 4.99]        [... 4.42 ...   4.5 ...  4.68...]

(맨 위 줄은 Anders Kaseorg의 Rust 솔루션입니다. 맨 아래 줄은 위의 프로그램입니다. 이들은 평균, 최소, 최대, 중앙값 및 사 분위수를 포함한 100 회 실행의 타이밍입니다.)

분석

왜 이것이 더 빠릅니까? C ++이 Rust보다 빠르거나 Knuth의 프로그램이 가장 빠르다는 것은 아닙니다. 실제로 Knuth의 프로그램은 (메모리를 보존하기 위해) trie-packing으로 인해 삽입이 느립니다. 그 이유는 Knuth 가 2008 년에 불평 한 것과 관련이 있다고 생각합니다 .

64 비트 포인터에 대한 불꽃

4 기가 바이트 미만의 RAM을 사용하는 프로그램을 컴파일 할 때 64 비트 포인터를 갖는 것은 절대적으로 바보입니다. 이러한 포인터 값이 구조체 내부에 나타나면 메모리 절반을 낭비 할뿐만 아니라 캐시의 절반을 효과적으로 버립니다.

위의 프로그램은 32 비트 배열 인덱스 (64 비트 포인터가 아님)를 사용하므로 “Node”구조체는 메모리를 덜 차지하므로 스택에 더 많은 노드가 있고 캐시 누락이 줄어 듭니다. (사실, x32 ABI 로서 이것 에 대한 연구 가 있었지만 , 좋은 상태 가 아닌 것 같습니다. 아이디어는 예를 참조 분명 유용에도 불구하고 최근 발표 의 V8에서 포인터 압축을 . 아 글쎄.) 등giganovel ,이 프로그램은 (포장 된) 트라이에 12.8MB를 사용하고 Rust 프로그램의 트라이에 32.18MB를 사용합니다 (giganovel ). “giganovel”에서 “teranovel”로 1000 배까지 확장 할 수 있지만 여전히 32 비트 인덱스를 초과 할 수 없으므로 이는 합리적인 선택입니다.

더 빠른 변형

속도를 최적화하고 패킹을 포기할 수 있으므로 Rust 솔루션에서와 같이 (포장되지 않은) 트라이를 실제로 포인터 대신 인덱스와 함께 사용할 수 있습니다. 이것은 더 빠른 것을 제공합니다 하고 별개의 단어, 문자 등의 수에 미리 고정 된 제한이 없습니다 :

#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>

typedef int32_t Pointer;  // [0..node.size()), an index into the array of Nodes
typedef int32_t Count;
typedef int8_t Char;  // We'll usually just have 1 to 26.
struct Node {
  Pointer link;  // From a parent node to its children's "header", or from a header back to parent.
  Count count;  // The number of times this word has been encountered. Undefined for header nodes.
};
std::vector<Node> node; // Our "arena" for Node allocation.

std::string word_for(Pointer p) {
  std::vector<char> drow;  // The word backwards
  while (p != 0) {
    Char c = p % 27;
    drow.push_back('a' - 1 + c);
    p = (p - c) ? node[p - c].link : 0;
  }
  return std::string(drow.rbegin(), drow.rend());
}

// `p` has no children. Create `p`s family of children, with only child `c`.
Pointer create_child(Pointer p, Char c) {
  Pointer h = node.size();
  node.resize(node.size() + 27);
  node[h] = {.link = p, .count = -1};
  node[p].link = h;
  return h + c;
}

// Advance `p` to its `c`th child. If necessary, add the child.
Pointer find_child(Pointer p, Char c) {
  assert(1 <= c && c <= 26);
  if (p == 0) return c;  // Special case for first char.
  if (node[p].link == 0) return create_child(p, c);  // Case 1: `p` currently has *no* children.
  return node[p].link + c;  // Case 2 (easiest case): Already have the child c.
}

int main(int, char** argv) {
  auto start_c = std::clock();

  // Program startup
  std::ios::sync_with_stdio(false);

  // read in file contents
  FILE *fptr = fopen(argv[1], "rb");
  fseek(fptr, 0, SEEK_END);
  long dataLength = ftell(fptr);
  rewind(fptr);
  char* data = (char*)malloc(dataLength);
  fread(data, 1, dataLength, fptr);
  fclose(fptr);

  node.reserve(dataLength / 600);  // Heuristic based on test data. OK to be wrong.
  node.push_back({0, 0});
  for (Char i = 1; i <= 26; ++i) node.push_back({0, 0});

  // Loop over file contents: the bulk of the time is spent here.
  Pointer p = 0;
  for (long i = 0; i < dataLength; ++i) {
    Char c = (data[i] | 32) - 'a' + 1;  // 1 to 26, for 'a' to 'z' or 'A' to 'Z'
    if (1 <= c && c <= 26) {
      p = find_child(p, c);
    } else {
      ++node[p].count;
      p = 0;
    }
  }
  ++node[p].count;
  node[0].count = 0;

  // Brute-force: Accumulate all words and their counts, then sort by frequency and print.
  std::vector<std::pair<int, std::string>> counts_words;
  for (Pointer i = 1; i < static_cast<Pointer>(node.size()); ++i) {
    int count = node[i].count;
    if (count == 0 || i % 27 == 0) continue;
    counts_words.push_back({count, word_for(i)});
  }
  auto cmp = [](auto x, auto y) {
    if (x.first != y.first) return x.first > y.first;
    return x.second < y.second;
  };
  std::sort(counts_words.begin(), counts_words.end(), cmp);
  const int max_words_to_print = std::min<int>(counts_words.size(), atoi(argv[2]));
  for (int i = 0; i < max_words_to_print; ++i) {
    auto [count, word] = counts_words[i];
    std::cout << word << " " << count << std::endl;
  }

  return 0;
}

이 프로그램은 여기에있는 솔루션보다 정렬을 위해 많은 어려움을 겪고 있지만 ( giganovel 어려움을 겪고 12.2MB 만 하고 더 빠릅니다. 앞서 언급 한 타이밍과 비교 한이 프로그램의 타이밍 (마지막 라인) :

target/release/frequent:   4.809 ±   0.263 [ 4.45.. 5.62]        [... 4.63 ...  4.75 ...  4.88...]
ptrie-walktrie:            4.547 ±   0.164 [ 4.35.. 4.99]        [... 4.42 ...   4.5 ...  4.68...]
itrie-nolimit:             3.907 ±   0.127 [ 3.69.. 4.23]        [... 3.81 ...   3.9 ...   4.0...]

Rust로 번역 하면이 (또는 해시 트리 프로그램)가 무엇을 원하는지보고 싶어합니다. . 🙂

자세한 내용

1. 여기에 사용 된 데이터 구조 : “패킹”시도에 대한 설명은 TAOCP 3 권 6.3 절 (디지털 검색, 즉 시도)의 연습 4와 TeX의 하이픈에 대한 Knuth의 학생 Frank Liang의 논문에서 간결하게 설명됩니다. : 컴퓨터로 단어 하이 펜션 .

2. 벤틀리 칼럼, 크 누스 프로그램, 맥 일로이의 리뷰 (유닉스 철학에 대한 부분 만)는 이전과 이후의 칼럼 과 컴파일러, TAOCP, TeX를 포함한 Knuth의 이전 경험 에 비추어 더 명확 합니다.

3. 전체 도서있다 프로그래밍 스타일에 연습이 특정 프로그램에 대한 다양한 접근 방식을 보여주는 .

위의 사항에 대해 자세히 설명하지 않은 블로그 게시물이 있습니다. 완료되면이 답변을 편집 할 수 있습니다. 한편, Knuth의 생일 행사 (1 월 10 일)에이 답변을 여기에 게시하십시오. 🙂

답변

def words_from_file(filename):
    import re

    pattern = re.compile('[a-z]+')

    for line in open(filename):
        yield from pattern.findall(line.lower())


def freq(textfile, k):
    frequencies = {}

    for word in words_from_file(textfile):
        frequencies[word] = frequencies.get(word, 0) + 1

    most_frequent = sorted(frequencies.items(), key=lambda item: item[1], reverse=True)

    for i, (word, frequency) in enumerate(most_frequent):
        if i == k:
            break

        yield word, frequency


from time import time

start = time()
print('\n'.join('{}:\t{}'.format(f, w) for w,f in freq('giganovel', 10)))
end = time()
print(end - start)