レコード付き動的ダブル配列

今週に入ってから本格的に実装してみた。削除は不要なので実装せず、漸進的なキーの追加とレコードの更新のみ。未使用リストの探索順序と衝突時の置換方法で検索効率、構築速度がかなり変わることを実感。あと、コードの長さ (C++ で200-250行ぐらいのヘッダファイル) の割に例外処理が面倒。とくに、未使用リストの更新周り、置換順序などの例外処理が煩雑。構築速度はキー集合が数千万オーダ (サイズで1G超) になっても 一般的な静的ダブル配列のライブラリと変わらないようになったが、検索速度を改善するには置換順序を工夫しないとダメそうだ。

あとはできあがりのダブル配列のコンパクト化ぐらいは実装しても良さそうだけど、検索インタフェースやデータ構造を分けたりする必要があって微妙かも。

[追記] 構築速度を速くしようとすると、検索速度が下がったりとなかなか難しい・・・