 string_symbolに対する疑念 （01月02日）- ・昨年の日記の更新頻度を見返してみると、８月は俺の方がさとみよりも上だった件。
これは、第二回一人俺祭りを開催するべきか……！（他の月がボロ負けだったことから目を逸らしつつ）
・拍手レス
>あけおめ！
あけおめこ、とよろ（句点の打ち方が不適切）
さて☆本題、俺は現在AbyssLibのパフォーマンス改善に取り組んでいる。
その作業において、string_symbolに対する疑念を覚えたため以下に備忘録的に書いてみる。
１．string_symbolとは？
以前の日記でも少しだけ触れたが、これのことである。
簡単に言うと、「string型での検索をint型での検索並みに高速化するための仕組み」である。
ただ以前の日記でも書いているが俺はパフォーマンス改善に取り組んでから少ししてその効用を疑っている。
その理由は矢張り以前に書いているのだが、「検索箇所がmap内かset内か変わっただけではないか」と思うからである。
２．map< string, int >とmap< string_symbol, int >の違いについて
さて、ここに単純なモデルケースを用意してみる。
stringとstring_symbolの違いが一番分かりやすい、map< string, int >とmap< string_symbol, int >で違いを比較してみよう。
（１）map< string, int >の場合
findメソッドを使用時に、findメソッド内でstring型での検索が行われる。
（２）map< string_symbol, int >の場合
findメソッドを使用時に、string_symbol型へのキャスト時にstring型での検索が行われる。
……あれれ？ あんまり効率良くないんじゃね？
むしろ、setへのinsertが発生する分効率悪いんじゃね？
……というわけで、実際にやってみた（トリビアの泉風）
３．実際にやってみた
以下のテストコードで、mapへのinsertならびにfindを100万回繰り返してみた。
DWORD LastTime;
char Message[64];
map< string, int > TestMap1;
LastTime = timeGetTime();
for(unsigned int i=0;i<1000000;i++){
char Temp[8];
sprintf(Temp, "%d", i);
TestMap1[Temp] = i;
}
sprintf(Message, "挿入速度（string）：%d", timeGetTime()-LastTime);
MessageBox(NULL, Message, NULL, MB_OK);
LastTime = timeGetTime();
for(unsigned int i=0;i<1000000;i++){
char Temp[8];
sprintf(Temp, "%d", i);
int Temp2 = TestMap1.find(string(Temp))->second;
}
sprintf(Message, "検索速度（string）：%d", timeGetTime()-LastTime);
MessageBox(NULL, Message, NULL, MB_OK);
map< string_symbol, int > TestMap2;
LastTime = timeGetTime();
for(unsigned int i=0;i<1000000;i++){
char Temp[8];
sprintf(Temp, "%d", i);
TestMap2[string_symbol(Temp)] = i;
}
sprintf(Message, "挿入速度（string_symbol）：%d", timeGetTime()-LastTime);
MessageBox(NULL, Message, NULL, MB_OK);
LastTime = timeGetTime();
for(unsigned int i=0;i<1000000;i++){
char Temp[8];
sprintf(Temp, "%d", i);
int Temp2 = TestMap2.find(string_symbol(Temp))->second;
}
sprintf(Message, "検索速度（string_symbol）：%d", timeGetTime()-LastTime);
MessageBox(NULL, Message, NULL, MB_OK);
そして、結果は以下のものとなった。
insert時
insertにおいて、string_symbolはstringの約1.5倍処理に時間が掛かってしまっている。
find時
findにおいても、string_symbolはstringの約1.5倍処理に時間が掛かってしまっている。
だがちょっと待って欲しい、（この手法での）一回だけならミスかもしれない（某新聞風）
string_symbolの根幹である「ハッシュでの検索は早い」というのは事実なので、
ループ毎にハッシュを検索しない方法ではひょっとすると早いのかもしれない。
（まあ、現実的な運用で役立つのかは別として……）
というわけで、次は以下のテストコードでmapへのinsertならびにfindを100万回繰り返してみた。
先程のものとの違いは、ループ突入前にハッシュを取得しているということである。
DWORD LastTime;
char Message[64];
char BaseKey[8] = "10241";
map< string, int > TestMap1;
LastTime = timeGetTime();
for(unsigned int i=0;i<1000000;i++){
char Temp[8];
sprintf(Temp, "%d", i);
TestMap1[Temp] = i;
}
sprintf(Message, "挿入速度（string）：%d", timeGetTime()-LastTime);
MessageBox(NULL, Message, NULL, MB_OK);
string Key1 = string(BaseKey);
LastTime = timeGetTime();
for(unsigned int i=0;i<1000000;i++){
int Temp2 = TestMap1.find(Key1)->second;
}
sprintf(Message, "検索速度（string）：%d", timeGetTime()-LastTime);
MessageBox(NULL, Message, NULL, MB_OK);
map< string_symbol, int > TestMap2;
LastTime = timeGetTime();
for(unsigned int i=0;i<1000000;i++){
char Temp[8];
sprintf(Temp, "%d", i);
TestMap2[string_symbol(Temp)] = i;
}
sprintf(Message, "挿入速度（string_symbol）：%d", timeGetTime()-LastTime);
MessageBox(NULL, Message, NULL, MB_OK);
string_symbol Key2 = string_symbol(BaseKey);
LastTime = timeGetTime();
for(unsigned int i=0;i<1000000;i++){
int Temp2 = TestMap2.find(Key2)->second;
}
sprintf(Message, "検索速度（string_symbol）：%d", timeGetTime()-LastTime);
MessageBox(NULL, Message, NULL, MB_OK);
そして、結果は以下のものとなった。
insert時
insertにおいて、string_symbolはstringの約2倍処理に時間が掛かってしまっている。
まあこれは当然のことだろう、mapとsetにinsertしているわけだからこればかりはどうしようもない。
find時
findにおいて、string_symbolはstringよりも若干早い（ただし誤差か一部例外あり）
まあこれは当然のことだろう、これで遅かったらマジで存在価値がない。
４．結論
string_symbolはstringよりも早い、ただし状況が限定される（事前にハッシュを生成して使い回す場合など）
だが、その場合はmap< string_symbol, X >ではなくmap< ハッシュ型（unsigned longとか）, X >でいい気がしないでもない。
シビアに実行速度を追い求めはせずソースコードの可読性を高めるならmap< string, X >が楽でいいし、そうでないならmap< ハッシュ型（unsigned longとか）, X >でいいような……。
結論として、（俺的には）わざわざ実装する必要のない誰得クラスだと感じられた。
だがまあ、この結論にも疑問が残らなくもない（というか、επιστημηてんてーがこんなミスをする筈がない）
なので、「こういう場合が一番良いんだよ！」とか「ここが間違ってるんだよ！」とかの指摘・ツッコミは大歓迎である。つ〜か、誰かお願いしますｍ（_ _）ｍ
|
