tr1::unordered_mapのkeyを自作クラスとかで使う

C++さっぱりわかりませんね（ﾄﾞﾔ
とりあえず、コンパイラさんに激怒されずに使うまでのメモ。
g++ ver4.5.1
boost ver1.44.0

int,long long,std::string etcなどは問題なく使用できるが、pairをkeyに指定したら怒られた。
たぶん、〜だろうなーという妄想はできるが確信はないのでその辺は一切書かないことにする。とにかくソースを見れば分かるのだからそれでいいw

#include <iostream>
#include <map>
#include <tr1/unordered_map>
#include <boost/functional/hash.hpp> // hash_combine
#include <cstdio>
using namespace std;
using namespace tr1;
using namespace boost;

struct peq{
  bool operator()(const pair<int,int>& a, const pair<int,int>& b)const{
    return a.first==b.first && a.second==b.second;
  }
};
struct phash{
  size_t operator()(const pair<int,int>& a)const{
    size_t seed = 0;
    hash_combine(seed, a.first);
    hash_combine(seed, a.second);
    return seed;
  }
};

int main(){
  unordered_map<pair<int,int>, int, phash, peq> umpp;
  umpp[make_pair(234,234)] = 234;
  return 0;
}

phashでpairの要素2つを計算してるが、例えば、setとかの場合は要素全部計算しないといけないの？size()じゃだめ？
と思ったので、以下のコードでハッシュ値が何度も衝突してしまう場合はどうなるのか確かめてみた。

//test code
#include <iostream>
#include <map>
#include <tr1/unordered_map>
#include <boost/functional/hash.hpp>
#include <cstdio>
#include <sys/time.h>
#include <sys/resource.h>
using namespace std;
using namespace tr1;
using namespace boost;

double getrusage_sec(){
  struct rusage t;
  struct timeval tv;
  getrusage(RUSAGE_SELF, &t);
  tv = t.ru_utime;
  return tv.tv_sec + (double)tv.tv_usec*1e-6;
}

struct peq{
  bool operator()(const int& a, const int& b)const{
    return a==b;
  }
};
struct phash_ver1{
  size_t operator()(const int& a)const{
    return 1;
  }
};
struct phash_ver2{
  size_t operator()(const int& a)const{
    size_t seed = 0;
    hash_combine(seed, a);
    return seed;
  }
};

int main(){
  double t1,t2;
  unordered_map<int, int, phash_ver1, peq> test1;
  unordered_map<int, int, phash_ver2, peq> test2;

  //正しくないhash処理
  t1 = getrusage_sec();
  for(int i=0; i<50000; i++){
    test1[i] = i;
  }
  t2 = getrusage_sec();
  printf("test1 :: time = %10.20fsec\n",t2-t1);
  //1
  
  //正しいhash処理
  t1 = getrusage_sec();
  for(int i=0; i<50000; i++){
    test2[i] = i;
  }
  t2 = getrusage_sec();
  printf("test2 :: time = %10.20fsec\n",t2-t1);
  //2
  return 0;
}

実行結果

test1 :: time = 21.75969200000000114414sec
test2 :: time = 0.01899699999999882039sec

うわぁー…洒落になってない。
ハッシュ値が何度も衝突したときはチェイン法とかになってるのか？（馬鹿）あれ、メモリ使用量爆発しない？とか思ったので、
test1,test2を片方ずつ走らせて、ループに入る前と抜けた後の2度の状態で /proc/pid/maps のheap領域を比較してみましたが
メモリ使用量はどちらも同じでした。
ハッシュ値が衝突してもハッシュ値の再計算を行ってるはず、と思うのですが、時間がかかりすぎな気もします。
もしかして、衝突時のハッシュ値の再計算は元の値に依存しており、次に振られる値が一緒なのか？…
だとすると、格納されてる要素の数がn個だとすると、n+1個目の要素が衝突せずに割り振られるのがn回目再計算？
それだと時間の増加率にも納得できるかも。
ちゃんとベンチマークを取ればわかりそうだが、ベンチマークどうやって取るんだろう。

気になった点が1つ、keyが例えば vector だとして、格納されてる要素すべてに hash_combine を施すと時間がかかります。
ある一定回数以上は効果が得られないような気がするので、上限が何回なのかということ。

まとめ
自作クラスに一切触れてない、基本一緒だから別にいいよね

ichirin2501's diary

いっちりーん。

tr1::unordered_mapのkeyを自作クラスとかで使う