C ++ (a la Knuth)
Byłem ciekawy, jak sobie poradzi program Knutha, więc przetłumaczyłem jego (pierwotnie Pascal) program na C ++.
Mimo że głównym celem Knutha nie była szybkość, ale zilustrowanie jego internetowego systemu czytania i pisania, program jest zaskakująco konkurencyjny i prowadzi do szybszego rozwiązania niż jakakolwiek z dotychczasowych odpowiedzi. Oto moje tłumaczenie jego programu (odpowiednie numery „sekcji” programu WEB są wymienione w komentarzach takich jak „ {§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;
}
Różnice w stosunku do programu Knutha:
- I w połączeniu 4 tablice Knutha
link, sibling, countich w tablicy Astruct Node (łatwiej zrozumieć w ten sposób).
- Zmieniłem tekstową transkluzję programowania (w stylu WEB) na bardziej konwencjonalne wywołania funkcji (i kilka makr).
- Nie musimy używać standardowych dziwnych konwencji / ograniczeń Pascala, więc używamy
freadidata[i] | 32 - 'a' jak w innych odpowiedziach tutaj, zamiast obejścia Pascala.
- W przypadku przekroczenia limitów (braku miejsca) podczas działania programu, oryginalny program Knutha radzi sobie z tym z wdziękiem, usuwając późniejsze słowa i drukując wiadomość na końcu. (Nie jest słuszne stwierdzenie, że McIlroy „skrytykował rozwiązanie Knutha, ponieważ nie był nawet w stanie przetworzyć pełnego tekstu Biblii”; wskazał jedynie, że czasami w tekście mogą pojawić się bardzo częste słowa, takie jak słowo „Jezus „w Biblii, więc warunek błędu nie jest nieszkodliwy.) Przyjąłem głośniejsze (i tak łatwiejsze) podejście po prostu kończąc program.
- Program deklaruje stałą wartość TRIE_SIZE do kontrolowania użycia pamięci, co spowodowało wzrost. (Stała 32767 została wybrana dla oryginalnych wymagań - „użytkownik powinien być w stanie znaleźć 100 najczęstszych słów w dwudziestostronicowym dokumencie technicznym (około 50 KB)” i ponieważ Pascal dobrze radzi sobie z liczbą całkowitą na odległość optymalizuje typy i pakuje je. Musieliśmy go zwiększyć 25x do 800 000, ponieważ dane wejściowe do testu są teraz 20 milionów razy większe).
- W celu ostatecznego wydrukowania łańcuchów możemy po prostu przejść się po trie i zrobić głupi (być może nawet kwadratowy) łańcuch.
Poza tym jest to właściwie program Knutha (wykorzystujący jego strukturę danych mieszania / upakowanej struktury danych i sortowanie kubełkowe) i wykonuje prawie takie same operacje (jak zrobiłby to program Knutha Pascala), jednocześnie zapętlając wszystkie znaki na wejściu; zwróć uwagę, że nie używa on żadnych zewnętrznych algorytmów ani bibliotek struktury danych, a także, że słowa o równej częstotliwości będą drukowane w kolejności alfabetycznej.
wyczucie czasu
Kompilowany z
clang++ -std=c++17 -O2 ptrie-walktrie.cc
Po uruchomieniu na największej teście tutaj ( giganovelz żądaniem 100 000 słów) i porównaniu z najszybszym opublikowanym tutaj programem, znajduję ją nieco, ale konsekwentnie szybciej:
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...]
(Górna linia to rozwiązanie Rust Andersa Kaseorga; dolna część to powyższy program. Są to czasy od 100 przebiegów, ze średnią, min, maks., Medianą i kwartylami.)
Analiza
Dlaczego to jest szybsze? Nie chodzi o to, że C ++ jest szybszy niż Rust, ani że program Knutha jest najszybszy z możliwych - w rzeczywistości program Knutha jest wolniejszy przy wstawianiu (jak wspomina) z powodu trie-upakowania (w celu oszczędzania pamięci). Podejrzewam, że przyczyna jest związana z czymś, na co narzekał Knuth w 2008 roku :
Płomień o 64-bitowych wskaźnikach
Absolutnie idiotyczne jest posiadanie 64-bitowych wskaźników, kiedy kompiluję program, który wykorzystuje mniej niż 4 gigabajty pamięci RAM. Kiedy takie wartości wskaźnika pojawiają się wewnątrz struktury, nie tylko marnują połowę pamięci, ale skutecznie wyrzucają połowę pamięci podręcznej.
Powyższy program używa 32-bitowych wskaźników tablicowych (nie wskaźników 64-bitowych), więc struktura „Węzła” zajmuje mniej pamięci, więc na stosie jest więcej Węzłów i mniej braków pamięci podręcznej. (W rzeczywistości, nie było pewne prace na ten temat jako x32 ABI , ale wydaje się, że nie jest w stanie dobrym , chociaż pomysł jest oczywiście przydatne, np patrz niedawne oświadczenie o kompresji wskaźnika w V8 . No cóż.) Więc na giganovel, ten program zużywa 12,8 MB dla (spakowanego) trie, w porównaniu do 32,18 MB z programu Rust dla jego trie (on giganovel). Możemy zwiększyć skalę o 1000x (powiedzmy „giganovel” do „teranovel”) i nadal nie przekraczać 32-bitowych indeksów, więc wydaje się to rozsądnym wyborem.
Szybszy wariant
Możemy zoptymalizować szybkość i zrezygnować z pakowania, dzięki czemu możemy faktycznie używać (niezapakowanego) trie jak w rozwiązaniu Rust, z indeksami zamiast wskaźników. Daje to coś, co jest szybsze i nie ma ustalonych limitów liczby różnych słów, znaków itp .:
#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;
}
Ten program, mimo że robi coś znacznie głupszego do sortowania niż rozwiązania tutaj, używa ( giganoveltylko) 12,2 MB dla swojej wersji i jest szybszy. Czasy działania tego programu (ostatnia linia) w porównaniu z wcześniejszymi wymienionymi czasami:
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...]
Chciałbym zobaczyć, co by to (lub program hash-trie) przełożyło na Rust . :-)
Dalsze szczegóły
O użytej tutaj strukturze danych: wyjaśnienie „prób pakowania” podano zwięźle w ćwiczeniu 4 w sekcji 6.3 (Wyszukiwanie cyfrowe, tj. Próby) w tomie 3 TAOCP, a także w pracy studenta Knutha, Franka Lianga, na temat dzielenia wyrazów w TeX : Słowo Hy-phen-a-tion autorstwa Com-put-er .
Kontekst kolumn Bentleya, programu Knutha i recenzji McIlroy'a (tylko niewielka część dotyczyła filozofii uniksowej) jest jaśniejszy w świetle poprzednich i późniejszych kolumn oraz poprzednich doświadczeń Knutha, w tym kompilatorów, TAOCP i TeX.
Jest cała książka Ćwiczenia w stylu programowania , pokazująca różne podejścia do tego konkretnego programu itp.
Mam niedokończony post na blogu opisujący powyższe punkty; może edytować tę odpowiedź po jej zakończeniu. Tymczasem i tak zamieszczam tutaj tę odpowiedź, przy okazji (10 stycznia) urodzin Knutha. :-)