Niente male anche le trie; con un'implementazione abbastanza povera (senza check che l'elemento sia un terminale e con payload su ogni nodo) ma con interi piccoli come indici e "frozen trie" con un vector come backend (dopo aver costruito il tutto con la deque per evitare riallocazioni del vettore durante il lookup) per guadagnare un 30% in prestazioni, il risultato è competitivo con la hashtable.
Trie:
codice:
template<typename T>
struct trie_node {
uint16_t next[26] = {0};
T payload = T();
template<typename TCont>
trie_node *lookup(const char *sz, bool add, TCont &alloc) {
if(*sz==0) return this;
uint16_t &n = next[*sz-'a'];
if(n==0) {
if(add) {
n = alloc.size();
alloc.push_back(trie_node());
} else {
return nullptr;
}
}
return alloc[n].lookup(sz+1, add, alloc);
}
};
template<typename T>
struct trie {
std::deque<trie_node<T>> nodes;
trie_node<T> *lookup(const char *sz, bool add) {
return nodes[0].lookup(sz, add, nodes);
}
trie() {
nodes.resize(1);
}
};
template<typename T>
struct frozen_trie {
std::vector<trie_node<T>> nodes;
trie_node<T> *lookup(const char *sz) {
return nodes[0].lookup(sz, false, nodes);
}
frozen_trie(trie<T> &orig) : nodes(orig.nodes.begin(), orig.nodes.end()) {}
};
Codice in coda al main:
codice:
{
std::cout<<"Trie\n";
trie<unsigned> count_t;
for(auto &sz: combs) {
count_t.lookup(sz.c_str(), true);
}
frozen_trie<unsigned> count_t_frozen(count_t);
for(int i=0; i<tot_count*comb_n; ++i) {
const std::string &key = combs[rand()%comb_n];
count_t_frozen.lookup(key.c_str())->payload++;
}
std::cout<<"Fine trie\n";
}
Risultati:
codice:
[mitalia@mitalia ~/scratch/lookup]$ stdbuf -o0 ./lookup.x | ts -i '%.s'
0.000019 Lineare
33.315037 Fine lineare!
0.000230 Dicotomica
6.158021 Fine dicotomica
0.000079 Hashtable
1.610438 Fine hashtable
0.000084 Map
3.777893 Fine map
0.000089 Trie
2.120793 Fine trie