Ok, ho fatto qualche prova io in C++ con un programma di test di questo tipo:
codice:
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <iostream>
#include <unordered_map>
#include <map>
const int comb_n = 233;
const int tot_count = 172400;
int main() {
std::string sz = "abcdefghijklm";
std::vector<std::string> combs;
for(int i=0; i<comb_n; ++i) {
std::random_shuffle(sz.begin(), sz.end());
combs.push_back(sz);
}
{
std::cout<<"Lineare\n";
std::vector<std::pair<std::string, unsigned>> count_v;
for(auto &sz: combs) {
count_v.push_back(std::make_pair(sz, 0U));
}
for(int i=0; i<tot_count*comb_n; ++i) {
const std::string &key = combs[rand()%comb_n];
for(auto &it: count_v) {
if(it.first == key) {
it.second++;
break;
}
}
}
std::cout<<"Fine lineare!\n";
std::cout<<"Dicotomica\n";
std::sort(count_v.begin(), count_v.end());
for(int i=0; i<tot_count*comb_n; ++i) {
const std::string &key = combs[rand()%comb_n];
auto it = std::lower_bound(count_v.begin(), count_v.end(), key,
[](const std::pair<std::string, int> &a, const std::string &b) {
return a.first < b;
});
it->second++;
}
std::cout<<"Fine dicotomica\n";
}
{
std::cout<<"Hashtable\n";
std::unordered_map<std::string, unsigned> count_h;
for(int i=0; i<tot_count*comb_n; ++i) {
const std::string &key = combs[rand()%comb_n];
count_h[key]++;
}
std::cout<<"Fine hashtable\n";
}
{
std::cout<<"Map\n";
std::map<std::string, unsigned> count_h;
for(int i=0; i<tot_count*comb_n; ++i) {
const std::string &key = combs[rand()%comb_n];
count_h[key]++;
}
std::cout<<"Fine map\n";
}
return 0;
}
I risultati:
codice:
[mitalia@mitalia ~/scratch/lookup]$ stdbuf -o0 ./lookup.x | ts -i '%.s'
0.000017 Lineare
34.237293 Fine lineare!
0.000084 Dicotomica
6.239760 Fine dicotomica
0.000086 Hashtable
1.640778 Fine hashtable
0.000086 Map
3.793371 Fine map
(i valori che contano sono quelli delle righe "Fine xxx", e si riferiscono a 233*172400 lookup fatti in ordine casuale)
Vince la hashtable di default fornita con libstdc++, che sembra usare murmurhash2 come funzione di hashing.