同条件で、hashとDoubleArrayでパフォーマンスを比較してみた。hashはglibの物を使用した。構築時間に関しては、hashが0.30秒、DoubleArrayが0.91秒程度。DoubleArrayの方が遅い。（Cannadicの全ての単語を登録した結果。） 検索時間に関しては、hashが0.24…

というわけで、今度こそページ分割に取り掛かりたいが、その前に論文を読まねば…。

もう一度sysprofでprofileをしてみると、x_check（条件を満たす空き要素探索）が処理時間の7割を占めている。ここでも馬鹿正直に空き要素を最初から線形探索しているコードがあったので、空き要素リストを使うように書き換えてみた。 この変更で、約9万語の…

よくよくみると、DoubleArrayというのは非常に密なデータ構造だ。実際に計測してみると、普通に辞書として単語を登録していくと、99.95%ぐらいの要素にはデータが詰まっている。ということは、ひとつ前を探索する際にも空き要素を先頭から手繰っていく方が速…

辞書の構築を高速化するだけなら、「次の空き要素」配列と「前の空き要素」配列を作れば、簡単に高速化は可能である。そして、できた辞書をmmap可能な形でコンパクトにファイルに書き出すことも可能である。省メモリでon the flyに構造を構築したいとか考え…

今書いているのはDoubleArrayのコードなのだが、validation用のコードなんかも入っているとは言え、既に800行に達している。しかも、DoubleArrayがどういう構造なのか頭に入ってない人にはちょっと読めなさそうな、ややこしいコードだ。正直言って、半年後の…

どうにも遅くて仕方ないので、sysprofでprofileをとってみた。profileの結果を信じるなら、配列のひとつ前の空き要素を線形探索する部分が遅いようだ。 というわけで、探索している関数をちょっといじって、どれぐらいの要素を線形探索しているのかを調べて…