刺身の上にたんぽぽ乗せる日記

プログラミングしたり、自販機の下に落ちてる小銭を集めたりしてます

高速なsplit/parse

昨日datファイルのパースが遅くてびっくりしてた。
900レスくらいのデータを行ごとに配列に入れた上で、

  • デリミタの<>でsplit
  • 本文の<br>を\nに置換
  • 本文のタグをstrip
  • 本文のhtmlエスケープ文字(&など)のアンエスケープ

という処理をやってたわけだけど、ざっくり900レスで2000+msecかかってた。遅過ぎる。
splitはString.split、残りはRegexpでやってたわけだけど、両方とも死ぬ程遅過ぎてうんこ。

String.split

http://sdc.sun.co.jp/java/docs/j2se/1.4/ja/docs/ja/api/java/lang/String.html#split%28java.lang.String%29

この文字列を、指定された正規表現に一致する位置で分割します。

そりゃあ遅いわ、という感じである。

http://developer.android.com/reference/android/text/TextUtils.html#split%28java.lang.String,%20java.lang.String%29

こっち使ってみたけど、結局対してスピードは変わらなかった。

しょうがないので、試しに自作のsplitを書いてみた。
今回の用途に関しては、いくつにsplitされるか予測がつくので、bufferを外から渡すことでオブジェクト生成のオーバーヘッドを減らせる。

static public int split(String orig, String delim, String[] out);

こんな感じで、中ではorig.indexOf(delim, offset)でループして、substringを作ってoutに順番にセットという感じ。これで大分高速になったのはあまりにも意外だった。

これで500msecくらい高速化できた。

String.replace

一応replaceではなくPatternでやってたけど、やっぱり遅い。
&などのエスケープ文字の種類の分だけreplaceAllしていたりするので、やっぱり速度が出ない。

オブジェクトの生成コストと、n回の走査が無駄かなぁ、と思って、ワンパスで全部置換できるように、タグとエスケープ文字全てがマッチするRegexpを書いて、ループしてみた。

Matcherには正にこういう時に便利なappendReplacementとappendTailという関数があって、
http://sdc.sun.co.jp/java/docs/j2se/1.4/ja/docs/ja/api/java/util/regex/Matcher.html#appendReplacement%28java.lang.StringBuffer,%20java.lang.String%29
http://sdc.sun.co.jp/java/docs/j2se/1.4/ja/docs/ja/api/java/util/regex/Matcher.html#appendTail%28java.lang.StringBuffer%29
比較的簡単に書けた。
大体パフォーマンスは200-300msecくらいよくなったんだけど、体感速度はそれほど変わらない。

大分処理の効率はよくなっているはずなので、試しにオブジェクトの生成数を抑えるためにString.toCharArray()でchar単位で文字列を見ていって、出力をcharのバッファにセットしていて、最後に出力のcharからStringを作るという方法。出力の文字数は必ずオリジナルの文字数より少ない事がわかるので、出力のバッファは最初に作ればいいだけ。楽。オブジェクトの生成数は本当に少ない。
さらに改善するならば、出力のために使うchar[]のバッファは使い回せるので、toCharArray()と戻り値のString以外はオブジェクトの生成はいらないはず。

この実装を試してみたところ、この書き換えで大体1000msecくらい速くなった。この処理だけで比較したら、10倍くらい速くなってた。

これで2000+msecかかってた処理は500msec弱くらいになり、大分ストレスが軽減されるようになった。

あと他に改善できるとわかっているのはList。
BufferedReaderでdatを読み込む時にreadlineで配列にわけてるけど、Listに突っ込んでからtoArrayで配列にしてる。これの代わりに自作したStringBufferのArray版みたいなやつでbenchmarkとってみたら、macだと割と高速に動作するっぽいことがわかった。
多分こっちのほうがオブジェクト生成数は圧倒的に少ないはずだから、実機で動かしたらなおさら高速化するはずだけど、それほどネックになってない箇所だから、まだList使いっぱなしにしてる。