もう少しで Darts-clone 0.32f を公開できそう
Darts-clone の新しいバージョンを来週にでも公開できそうです.これまでのバージョンとは方向性が異なり,特殊なデータに対して特化したものになります.一週間ほど前には既に動く状態になっていたものの,辞書を作成するときのメモリ消費が大きすぎるという問題を解決すべく,改良を施していました.
- 特徴
- TAIL を使いません.
- 辞書のサイズは Darts の 1/2 以下になります.
- 検索時間は Darts と同等です.
- レコードの指定がないときは,今までどおりの方法でダブル配列を作成します.
- レコードの指定があるときは,同じレコードがあることを期待して,共通部分木を併合します.
- 通常のトライを経由せずに共通部分木を併合します.
- さっそく Left-leaning Red-Black Trees を使っています.
- 同じレコードが多いほど辞書が小さくなります.
- キーの有無だけが必要なときは,レコードをすべて 0 にして使うのが吉です.
# なんだか忙しくて,あまり大きなことができない今日この頃です.