Re: Is there a faster way to fetch data from stl map?
Ian Collins wrote:
tni wrote:
[Is there any reason for not quoting context?]
Is there any reason you are not using a hash map? Unless you need the
the keys in sort order, there is no reason to prefer the std::map. I
would be surprised, if a decent hash map wasn't 10x faster than std::map
for your amount of data.
With an integer key? From where did you draw that conclusion?
With GCC 4.1:
Hash map time: 485 0
Std map time: 5656 0
(I'm assuming the keys are pretty much sequential.)
----------------------------------------------------------------
#include <google/dense_hash_map>
#include <map>
#include <vector>
#include <time.h>
#include <iostream>
struct hash {
size_t operator()(int a) const {
a = (a ^ 61) ^ (a >> 16);
a = a + (a << 3);
a = a ^ (a >> 4);
a = a * 0x27d4eb2d;
a = a ^ (a >> 15);
return a;
}
};
int main(int argc, char* argv[]) {
int elems = 1000000;
int loop_count = 100;
std::vector<int> data_vec;
std::vector<int> keys;
data_vec.resize(200);
google::dense_hash_map<int, std::vector<int>, hash > hash_map;
hash_map.set_empty_key(-1);
std::map<int, std::vector<int> > std_map;
for(int i = 0; i < elems; i++) {
int key = i;
keys.push_back(key);
hash_map[key] = data_vec;
std_map[key] = data_vec;
}
int a = 0;
clock_t start_time = clock();
for(int j = 0; j < loop_count; j++) {
for(int i = 0; i < elems; i++) {
int key = keys[j];
std::vector<int>& data = (*hash_map.find(key)).second;
a += data[0];
}
}
clock_t stop_time = clock();
std::cout << "Hash map time: " << (stop_time - start_time) << " "
<< a << "\n";
start_time = clock();
for(int j = 0; j < loop_count; j++) {
for(int i = 0; i < elems; i++) {
int key = keys[j];
std::vector<int>& data = (*std_map.find(key)).second;
a += data[0];
}
}
stop_time = clock();
std::cout << "Std map time: " << (stop_time - start_time) << " " <<
a << "\n";
}