2009年5月25日月曜日

std::set や std::map の速度

 要素検索だけなら、set や map は速いだろうという頭があったわけですよ。で、int 型の2つのキーを

unsigned long long key = (((unsigned long long) id1) << 32) | ((unsigned long long)id2));

という風にして、検索させてたんですが、キー数 N に対して、インデックス数 N * N の場合 set や map 使うよりも、std::vector<std::vector<value> > を宣言して、

array[id1][id2];

した方が、超絶に速いわけなんですね。一回、連想コンテナも、どれぐらいの速度差があるのか、比較して体感速度を会得しておいた方が良いかもしんないです。予想していたよりも差があって、正直面食らってしまいました。

0 件のコメント: