今度はメモリ消費量の比較をしてみよう。HashはGlibのハッシュライブラリを用いた。Glibのハッシュライブラリにはメモリ消費量を知る機能がないので、適当にライブラリ内部に手を入れて計算するようにしてみた。 今回もテストデータとしてはCannadicにある全…

DoubleArrayを辞書構造として使う場合、実際に登録されるデータは多くの場合に分岐が少ない。分岐が少ないデータというのは空き領域が見つけやすいので、これがDoubleArrayの高使用率に貢献しているのは明らかである。TAILを用いるという事は、この分岐の少…

論文を読んでいると、P(x|y)=むにゃむにゃ、という形で数式が書いてあるのに、「これはgenerative model」みたいな事が書いてあるところがあった。 これまで生成モデルはP(x,y)で、識別モデルはP(y|x)である、つまり生成モデルは同時確率、識別モデルは条件…

同条件で、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の結果を信じるなら、配列のひとつ前の空き要素を線形探索する部分が遅いようだ。 というわけで、探索している関数をちょっといじって、どれぐらいの要素を線形探索しているのかを調べて…

valgring --tool=memcheckとして動かすと、書き込んではいけない場所に書き込んじゃってることをvalgrindが報告してくれた。valgrindばんざい。

今開発しているプログラムは、途中でreallocがエラーを出して停止してしまうのだが、valgrindを通すと問題なく動く。うーん、なんか変なバグを作りこんでしまったらしい…。

高速化のために今日一日格闘したのに、いじる前よりも1.3倍も遅くなってしもうた…。orz しょうがないので論文を読んでやり直し。泣ける。

ここしばらく作っていたDoubleArrayのコードがやっと動いた。境界条件のチェックをしたら、次は配列サイズ削減のためのページ分割の実装だな。これをしているDoubleArrayのライブラリは今のところみたことがない。（そもそもDoubleArrayのフリーな実装は3つ…

境界条件のチェックではまりまくった。結局、境界条件のチェックに半日かかった計算になる。

A new compression method of double array for compact dictionariesという論文を読んだ。要するに、BASEやCHECKの要素には通常32bit intを使うけど、double arrayの元になるTRIE木を分割して大きな数字がでてこないようにすれば、16bit intで十分なんじゃ…

Fast and compact updating algorithms of a double-array structureという論文を読んだ。要するに、double arrayの空き部分を探すのに、オリジナルのやり方（適当な空き部分が見付かるまでdouble arrayの全領域をスキャン）で探すと使用率が高い場合に効率…

CLWFKはあきらめて、KAGEを使ってみた。ストロークの連結処理を行っていないみたいで、大きく表示するとちょっと使用に耐えない感じ。（ソースを読んだ限りでは、kagecomb.cあたりで連結処理をしてそうなんだけど…。）

とりあえずさざなみフォントを改良してみようとして、CLWFKを使ってみた。しかしスタックオーバーフローが起こってフォントが生成できない。（tracecontでオーバーフローが起こる。）デバッグしようにもコードが読めない。この程度の分量のプログラムが読め…

潮待フォントに影響されて、もっかいフォントをいじってみようかなという気分になった。どうでもいいけど、全然研究の事書いてないね、この日記。

やはり、フォントをどうにかしなければならない、と感じた。IPAフォントはフリーとは言えないしなぁ。さて、それでは、どのようにして作業をするべきか。生成後のトゥルータイプフォントをfontforgeでいじるのはたやすいが、それではあまりに効率が悪すぎる…

MEMM（最大エントロピーマルコフモデル）はCRFに比べるとあまり性能が出ない ベータ分布がよく使われる理由 パラメータをいじることでいろんなデータにフィットする（分布の形が柔軟に変えられる） 平均や分散が計算できる 以上2点により、扱いやすい フィッ…