レコード付き動的ダブル配列
拡張遷移先節点集合を実装してみた。アイデアはシンプルなので適当に解釈して実装。が、いつもプログラムを変更するときのように格納途中でダブル配列が壊れる。check が壊れるのが大半で、あとは未使用要素リストが壊れることが多い。後者は配列の添字が負になって segmentation fault するので、gdb でチェックして assert を入れれば割とすぐに解決できるが、大変なのは前者。print 文デバッグするしかない。
- 格納時とチェック時に、base, label, check を出力する print 文を追加
- 全キーを格納してできたダブル配列に対し、各キーを検索し、検索が成功するかどうかチェックし、成功すれば終了、失敗すれば 3 に
- キーの総数を N として、二分探索でダブル配列を壊すキーが何番目か (=n とする) 調べる
- バグの原因を同定
- n != N なら 2 に戻る
の繰り返し。これが終わっても、ランダム順や、別のキー集合を入力するとこけるときがあるので萎える・・・
結局、2-5 のループを4回ほど繰り返してデバッグ終了。作業時のメモリが 8n->10n bytes (n はトライのノード数) になった代わりに，約1.5倍ほど速くなった。とりあえず commit して code の cleanup をした。cleanup 後の行数は(c++で)290行ぐらい。
[考察] 単純に未使用リストを線形に探索する場合、衝突時に一度に移動するノードの数が増えてくると、更新時間が極端に増えてしまう。移動するノード数や、失敗上限などの条件を満たすものを末尾に置くとある程度は解決できるが、未使用要素が増えたり検索が遅くなったりしてなかなか悩ましい。
