Есть ли какие-либо эффективные по скорости и кэшу реализации trie в C/С++? Я знаю, что такое trie, но я не хочу изобретать колесо, реализуя его сам.
Выполнение Trie
Ответ 1
если вы ищете реализацию ANSI C, вы можете "украсть" ее из FreeBSD. Файл, который вы ищете, называется radix.c. Он используется для управления данными маршрутизации в ядре.
Ответ 2
Я понимаю, что речь шла о готовых реализациях, но для справки...
Прежде чем прыгать на Джуди, вы должны были прочитать " Сравнение производительности" Judy to Hash Tables". Тогда googling название, вероятно, даст вам целую жизнь обсуждения и реституции, чтобы читать.
Явное понимание кэширования, о котором я знаю, это HAT-trie.
HAT-trie, когда она реализована правильно, очень крутая. Однако для поиска префикса вам нужен шаг сортировки на хэш-ведрах, что несколько противоречит идее структуры префикса.
Несколько проще trie - burst-trie, который по существу дает вам интерполяцию между стандартным деревом какого-то типа (например, BST) и три. Мне это нравится концептуально, и это намного проще реализовать.
Ответ 3
Мне повезло с libTrie. Возможно, он не оптимизирован специально для кеша, но производительность всегда была приличной для моих приложений.
Ответ 4
GCC поставляется с несколькими структурами данных в рамках своих "Структур данных на основе политик". Это включает несколько реализаций trie.
http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/trie_based_containers.html
Ответ 5
Литература,
- A Реализация двойного массива (включает реализацию
C
) - TRASH - динамическая структура данных LC-trie и хешей - (ссылка на PDF в формате PDF, описывающая динамическое использование LC-trie в ядре Linux для реализации поиска адресов в таблице IP-маршрутизации
Ответ 6
массивы Judy: очень быстрые и эффективные по памяти массивы с редкими динамическими массивами для бит, целых чисел и строк. Массивы Judy быстрее и эффективнее памяти, чем любое дерево двоичного поиска (включая avl и red-black-trees).
Ответ 7
Вы также можете попробовать TommyDS в http://tommyds.sourceforge.net/
См. страницу контрольных показателей на сайте для сравнения скорости с недрами и юбилеем.
Ответ 8
Cedar, HAT-Trie, и JudyArray довольно удивительно, вы можете найти эталон здесь.
Ответ 9
Оптимизация кэша - это то, что вам, вероятно, придется делать, потому что вам нужно будет сопоставить данные в одной кешлинке, которая обычно составляет примерно 64 байта (что, вероятно, будет работать, если вы начнете комбинировать данные, например как указатели). Но это сложно: -)
Ответ 10
"Burst Trie" , кажется, немного эффективнее пространства. Я не уверен, сколько кеш-эффективности вы можете получить из любого индекса, так как кэширование CPU настолько крошечное. Однако этот вид trie достаточно компактен, чтобы хранить большие массивы данных в ОЗУ (где обычный Trie не будет).
Я написал реализацию Scala пакета trie, который также включает в себя некоторые методы экономии пространства, которые я нашел в реализации GWT-типа.
Ответ 11
У меня были очень хорошие результаты (очень хороший баланс между производительностью и размером) с marisa-trie по сравнению с несколькими реализациями TRIE, упомянутыми в моем наборе данных.
Ответ 12
Совместное использование моей "быстрой" реализации для Trie, проверено только в основном сценарии:
#define ENG_LET 26
class Trie {
class TrieNode {
public:
TrieNode* sons[ENG_LET];
int strsInBranch;
bool isEndOfStr;
void print() {
cout << "----------------" << endl;
cout << "sons..";
for(int i=0; i<ENG_LET; ++i) {
if(sons[i] != NULL)
cout << " " << (char)('a'+i);
}
cout << endl;
cout << "strsInBranch = " << strsInBranch << endl;
cout << "isEndOfStr = " << isEndOfStr << endl;
for(int i=0; i<ENG_LET; ++i) {
if(sons[i] != NULL)
sons[i]->print();
}
}
TrieNode(bool _isEndOfStr = false):isEndOfStr(_isEndOfStr), strsInBranch(0) {
for(int i=0; i<ENG_LET; ++i) {
sons[i] = NULL;
}
}
~TrieNode() {
for(int i=0; i<ENG_LET; ++i) {
delete sons[i];
sons[i] = NULL;
}
}
};
TrieNode* head;
public:
Trie() { head = new TrieNode();}
~Trie() { delete head; }
void print() {
cout << "Preorder Print : " << endl;
head->print();
}
bool isExists(const string s) {
TrieNode* curr = head;
for(int i=0; i<s.size(); ++i) {
int letIdx = s[i]-'a';
if(curr->sons[letIdx] == NULL) {
return false;
}
curr = curr->sons[letIdx];
}
return curr->isEndOfStr;
}
void addString(const string& s) {
if(isExists(s))
return;
TrieNode* curr = head;
for(int i=0; i<s.size(); ++i) {
int letIdx = s[i]-'a';
if(curr->sons[letIdx] == NULL) {
curr->sons[letIdx] = new TrieNode();
}
++curr->strsInBranch;
curr = curr->sons[letIdx];
}
++curr->strsInBranch;
curr->isEndOfStr = true;
}
void removeString(const string& s) {
if(!isExists(s))
return;
TrieNode* curr = head;
for(int i=0; i<s.size(); ++i) {
int letIdx = s[i]-'a';
if(curr->sons[letIdx] == NULL) {
assert(false);
return; //string not exists, will not reach here
}
if(curr->strsInBranch==1) { //just 1 str that we want remove, remove the whole branch
delete curr;
return;
}
//more than 1 son
--curr->strsInBranch;
curr = curr->sons[letIdx];
}
curr->isEndOfStr = false;
}
void clear() {
for(int i=0; i<ENG_LET; ++i) {
delete head->sons[i];
head->sons[i] = NULL;
}
}
};