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

xor addressing を実装して、base のあるブロックに兄弟ノードを配置するようにした。根ノードの扱いが面倒だったので (根ノードの base を最初のブロック中にすると、根ノード自身と衝突したときの処理が面倒) 最初のブロックは根ノードからの遷移のみを保持するようにして、残りのノードは次のブロック以降に配置するようにした。結果として、検索は1割ほど速くなったが、構築は辞書順はほぼ前と同じで(非辞書順だと) 遅くなった。続いてブロック管理を実装予定。プログラム260行。
2500万のバイナリのキーを、非辞書順で追加したダブル配列の構築がやっと終わった。1.249e+08 [ms] なので、12500秒、約3.5時間。サイズは2割増、検索速度は3倍。辞書順だと構築は約20秒で終わり未使用要素もほぼ0なのでひどい差だ。しかしサイズ2割増で済んでいるのはちょっと驚いた。

ついでにブロック管理を実装した。が、キーを非辞書順に登録した際の(xor addressing と offset base との間の) 速度差は無くなった。実装がうまくない可能性あり。もうちょっと考えてみよう。311行。