知られざるTHashedStringListの事実。
ハッシュテーブルといえば
Delphiにジェネリクスが導入される以前、ハッシュテーブル(らしきもの)を使おうと思うと、標準VCLではIniFilesユニットに含まれるTHashedStringListしかなかった*1。一方、導入後はGenerics.CollectionsユニットのTDictionaryができたので、やっとまともなハッシュテーブルが使えるようになった。
どっちが速いの?
使い勝手は明らかにTDictionaryが上だけど、伝統的なTHashedStringListにもきっといいところはあるはず!
で、調べてみた
条件としてはランダムなキー(16文字)を10万件追加し、その10万件と同じキーの取得時間(1)と、存在しないキー10万件の取得時間(2)を測定。
THashedStringList.Add | 30ms |
THashedStringList.IndexOf(1) | 1776ms |
THashedStringList.IndexOf(2) | 4247ms |
TDictionary |
137ms |
TDictionary |
59ms |
TDictionary |
60ms |
TDictionaryはえー
と思ったけど、どちらかというとTHashedStringListが遅いだけな気がする…。
ということでTStringList(Sorted)と比較
TStringListは10万件Addし終わった後にSorted:=TrueするまでをAddの処理として計測。THashedStringListは上記のものと同じ。
TStringList.Add | 795ms |
TStringList.IndexOf(1) | 572ms |
TStringList.IndexOf(2) | 631ms |
THashedStringList.Add | 30ms |
THashedStringList.IndexOf(1) | 1776ms |
THashedStringList.IndexOf(2) | 4247ms |
THashedStringListより、ずっとはやーい
1万件程度ではTStringListより速い(それでも2倍程度だけど)ので、恐らく件数が多いとハッシュ値が衝突しまくって、処理時間のほとんどを線形探索に使われているのではないかと予想。実際にソースを見るとTHashedStringList内で使ってるハッシュテーブルクラス(TStringHash)のデフォルトサイズが256で、特にサイズを拡張することもなく使ってるので、10万件も追加したら毎回衝突するのも仕方ないといったところ*2。
ちなみに100万件で計測すると、TDictionaryは参照が1秒以内に終わるのに対して、THashedStringListは5分弱(存在しないキーの参照では10分弱!)かかるという悲惨な結果に。
ということで結論
今まで糞みたいなTHashedStringListを使っていたところは(Delphi2009以降を使っているなら)TDictionaryに置き換えようぜ!もしまだジェネリクスの無いバージョンを使っているとしても、件数が一定以上なら普通の(ソート済み)TStringList使った方が速いんだぜ!