TinySegmenter.jl の高速化手法を追っかけてみた

今日の元ネタはこちらです.

chezou.hatenablog.com

他言語との比較が行われているわけですが,Julia 版はアルゴリズムの作りが他とだいぶ変わってしまっているので, そのまま比較するのはどうかなと思うわけですが,でも,Julia が書けるわけでもないので,ざっくりどんな高速化が行われたのか golangで追っかけてみました(結局 golang ネタです).

TinySegmenter はもともと javascript でコンパクトに書かれた分かち書き用のプログラムです.

TinySegmenter: Javascriptだけで実装されたコンパクトな分かち書きソフトウェア

なるべくオリジナルに忠実に golang で実装して,そこから Julia 版の高速化手法を盛り込んでいってパフォーマンスを見ていきます.

で,こちらにご用意したのが golang 版です.

shogo82148.github.io

すごいものを作る方がいらっしゃいますね! perl, ruby, python, c++, c# 各種言語の TinySegmenter を生成してくれます. TeXvim にも対応してます.もちろん golang も.

というわけで,最初のバージョンはこれで生成したものを使わせて頂きます.

Julia 版が行ってる高速化は大まかに2つです

  • セグメントを生成するときに,文字列の連結を行わず,なるべく文字列の添え字の処理だけでおこなう
  • 文字のカテゴリを調べるときに,オリジナルは正規表現を利用して調べているところを,正規表現を使わないで調べる

というわけで,こんな感じでリファクタリングしていきました.

  1. TinySegmenterMaker で生成
  2. 配列の初期値を十分大きく取るように調整
  3. セグメント生成時に文字列の連結などを行わないようにアルゴリズムを修正
  4. 正規表現の利用の排除

パフォーマンスの遷移を調べる

github.com

gobenchui というツールを使うと,コミット履歴ごとにベンチマークを計算してグラフを作ってくれます. 使い方は至ってシンプルで,普段のテストのかわりに

$ gobenchui .

とするだけです.結果はこうなりました.3倍くらい速くなってるでしょうか.正規表現の除去も効いてるみたいですが,やっぱり文字列の連結操作が減ったのが一番効いてるみたいですね.

f:id:ikawaha:20151023155151p:plain

ちなみにメモリパフォーマンスはこんな感じで推移しました.

f:id:ikawaha:20151023155459p:plain

まとめ

Julia 版が高速化前と後でどのくらい違うのか気になるところですが,それはさておき,TinySegmenterMaker がすごすぎます. TinySegmenterMaker に Julia 用のテンプレートを PR したかったのですが,ぼくの Julia 力では無理そうなので,どなたか是非チャレンジしてみて欲しいです.

今回作ったサンプルはこちら.

github.com

追記

model.go という,モデルを切り出したファイルをアルゴリズムの変更の時に作ったんだが,こいつをコミットし忘れてた. 慌ててコミットしたけど,gobenchui による再現がうまくいかないかも.ごめんなさい.