大規模なキー集合を登録してみた
キーを 1000 万件くらい登録しようとすると std::bad_alloc でお亡くなりになったため,メモリの無駄遣いを減らすように修正しました(push_back で追加する前に reserve を呼び出すなど).
後,std::sort() を std::stable_sort() に変更しました.これは,コンパイラによって構築される辞書が変わると気持ち悪いからです(互換性には影響なし).
次に更新するときに反映します.
以下,Google N-gram コーパスの unigram を用いた実験結果です.
キー集合 | キー数 | ソース | Darts | Darts-clone |
---|---|---|---|---|
英語 | 13,588,391 | 125,937,836 | 406,358,432 | 223,290,696 |
日本語 | 2,565,427 | 50,784,220 | 162,689,912 | 36,857,172 |
※ 英語に対する Darts-clone の構築は Darts より低速でしたが,日本語に対しては Darts-clone の方が高速でした.日本語の場合に辞書サイズの差が大きくなっているのは,長いカタカナが大量に含まれていたことが原因と考えられます.