google::dense_hash_mapのset_deleted_keyメソッド
google::dense_hash_mapを使うときは、データのinsertを行う前にset_empty_keyメソッドで空のとき用のキーを指定しておく必要がある。同様にキーの削除を行う前には、set_deleted_keyメソッドで削除されたとき用のキーを指定しておかなければならない。
で、このset_deleted_keyをあらかじめ指定しておくようにしてたんだけど、そうしたら何か遅くなった?と思って、ちょっと動作速度を調べてみた。
#include <cstdlib> #include <ctime> #include <iostream> #include <google/dense_hash_map> int main() { clock_t start, end; const int max = 20000000; srand(time(NULL)); // not set_deleted_key google::dense_hash_map<int, int> h1; h1.set_empty_key(-1); start = clock(); for (int i = 0; i < max; i++) { // write h1[i] = i; } for (int i = 0; i < max; i++) { // read int r = rand() % max; int val = h1[r]; } end = clock(); std::cout << "not_set_deleted_key: " << (double)(end - start) / CLOCKS_PER_SEC << std::endl; // set_deleted_key google::dense_hash_map<int, int> h2; h2.set_empty_key(-1); h2.set_deleted_key(-2); start = clock(); for (int i = 0; i < max; i++) { // write h2[i] = i; } for (int i = 0; i < max; i++) { // read int r = rand() % max; int val = h2[r]; } end = clock(); std::cout << "set_deleted_key: " << (double)(end - start) / CLOCKS_PER_SEC << std::endl; return 0; }
set_deleted_keyをあらかじめ指定した場合と、指定しなかった場合それぞれで、データのinsertとgetを繰り返し実行したときの処理時間を調べてみた。
% g++ dense_hash_bench.cc % ./a.out not_set_deleted_key: 17.2 set_deleted_key: 17.65
びみょーな差だけど、set_deleted_keyを指定しておくと遅くなった。
ドキュメントを見てみると、set_empty_keyは初めから指定しておかないとダメだけど、set_deleted_keyはeraseが呼ばれるまでは実行しておく必要はないらしい。
http://goog-sparsehash.sourceforge.net/doc/dense_hash_map.html#6
なのでdense_hash_mapを使うときは、eraseが呼ばれる直前まではset_deleted_keyは使用しない方がよさそう。それとclear_deleted_keyを呼べばdeleted_keyもクリアされて、遅くなっていたのもの元に戻ってたので、set_deleted_keyを使用した後はclear_deleted_keyも忘れずに。
そもそもempty_keyやdeleted_keyを指定しておかないといけないかが分かっていないんだけど…。やはりアルゴリズムの中身をちゃんと勉強してないとダメだな。