2014年11月29日土曜日

[OCaml]XML Parser PXPを使ってみた(Bufferモジュールを利用)

前記事の、E_char_dataイベントで文字列を ^ で連結するやり方は効率が悪すぎた。

ブログ更新をtweetしていたら、@camloebaさんに Bufferがあることを教えていただいた。
いつもありがとうございます!

ということで、Bufferを使うように修正してみた。

修正後のプログラム

修正したのはparse関数だけ。
let parse element_func_list =
  let tags = Stack.create () in
  let element_func () =
    let item = List.find element_func_list ~f:(fun (element_list, _) ->
        Stack.to_list tags = element_list
      ) in
    match item with
      Some (_, func) -> Some func
    | None -> None in
  let in_content = ref false in
  let content = Buffer.create 1024 in
  let apply_func = ref (fun _ -> ()) in
  Pxp_ev_parser.process_entity config entry entmng (fun ev ->
      (* let event_string = Pxp_event.string_of_event ev in *)
      match ev with
        Pxp_types.E_start_tag (name, _, _, _) -> begin
          Stack.push tags name;
          (* print_endline @@ List.to_string (Stack.to_list tags) ~f:ident; *)
          match element_func () with
            Some func' -> begin
              apply_func := func';
              in_content := true
            end
          | _ -> ()
        end
      | Pxp_types.E_end_tag (name, _) -> begin
          ignore @@ Stack.pop_exn tags;
          if !in_content then
            begin
              !apply_func @@ Buffer.contents content;
              Buffer.clear content;
              in_content := false;
            end;
        end
      | Pxp_types.E_char_data str -> begin
          if !in_content then
            Buffer.add_string content str
        end
      | _ -> ())
このような修正は、動的な型の言語の場合、必要な修正箇所を見逃しやすいが、 OCamlのような静的な型の言語の場合は、コンパイルエラーで検出できるので非常にやりやすい。
Emacs+Tuaregでコード書いており、保存と同時にエラーがある行の色が変わるので、修正箇所は一目瞭然。

実行結果

satoshi@xubuntu:~/workspace/ocaml-try/pxp$ time ./parse_wiki > /dev/null

real    0m0.093s
user    0m0.081s
sys     0m0.011s
修正前は、
satoshi@xubuntu:~/workspace/ocaml-try/pxp$ time ./parse_wiki > /dev/null

real    0m3.361s
user    0m3.168s
sys     0m0.180s
およそ35倍速くなった!
これなら全く問題なし。
計測していないが、メモリの使用量も、かなり減ったはず。

なお、^による文字列連結に関しては、 Real World OCaml Chapter 3. Lists and Patternsの Performance of String.concat and ^ にも書かれていた。
^ を使うたびに文字列を生成するので、少しずつ文字列を連結して、大きな文字列を作る場合は、非常にパフォーマンスが悪い。

[OCaml]XML Parser PXPを使ってみた

OCamlのXML ParserであるPXPを使ってみた。

処理したXMLは日本語版Wikipediaの文書データ。
この文書データはここからダウンロードできる。

この文書データは、複数のpage要素からなり、 title要素にタイトル、 text要素に内容が書かれている。
今回は、このタイトルと内容を抜き出して、出力する処理を書いてみた。

PXPのインストール

PXPはopamでインストールできる。
$ opam install pxp

PXPについて

treeモードとeventモードがある。
treeモードでは、DOM treeを構築できるようだ。

やりたいことは 大きなサイズの日本語版Wikipediaのデータをパースすること。
DOMを構築する必要はないので、eventモードを使う。

XML data as stream of events を参考にコードを書いてみる。

eventモードにはPush parsingとPull pasingの二種類のパース方法がある。
今回はPush parsingを利用した。

前準備

ここからWikipediaのデータをダウンロードする。
テストが簡単になるように、10ページ分だけ切り出したデータを作っておく。
$ grep -m 10 -n -F "</page>" jawiki-20141122-pages-articles.xml | cut -d: -f1 | tail -n 1 | xargs -I @ head -n @ jawiki-20141122-pages-articles.xml > jawiki_10.xml
$ echo "</mediawiki>" >> jawiki_10.xml


サンプルプログラム


内容を取り出したい要素と、その内容を取り出したときに呼ばれる関数を、 処理関数parseに渡す方式で実装した。

let element_func_list = [
  (["title"; "page"; "mediawiki"], (fun content -> ..snip..));
  (["text"; "revision"; "page"; "mediawiki"], (fun content -> ..snip..))]

let () = parse element_func_list

parse_wiki.ml


open Core.Std

let config = let open Pxp_types in
  {default_config with encoding = `Enc_utf8}
               
let source = Pxp_types.from_file "/home/satoshi/Documents/jawiki/jawiki_10.xml"

let entmng = Pxp_ev_parser.create_entity_manager config source

let entry = `Entry_document []

let element_func_list = [
  (["title"; "page"; "mediawiki"],
   (fun content ->
      print_endline @@ sprintf "Title: %s" content));
  (["text"; "revision"; "page"; "mediawiki"],
   (fun content ->
      let max_length = 40 in
      let content' = 
        if String.length content > max_length then
          (String.slice content 0 max_length) ^ "..."
        else
          content in
      print_endline @@ sprintf "Text: %s" content'))]

let parse element_func_list =
  let tags = Stack.create () in
  let element_func () =
    let item = List.find element_func_list ~f:(fun (element_list, _) ->
        Stack.to_list tags = element_list
      ) in
    match item with
      Some (_, func) -> Some func
    | None -> None in
  let in_content = ref false in
  let content = ref "" in
  let apply_func = ref (fun _ -> ()) in
  Pxp_ev_parser.process_entity config entry entmng (fun ev ->
      (* let event_string = Pxp_event.string_of_event ev in *)
      match ev with
        Pxp_types.E_start_tag (name, _, _, _) -> begin
          Stack.push tags name;
          (* print_endline @@ List.to_string (Stack.to_list tags) ~f:ident; *)
          match element_func () with
            Some func' -> begin
              apply_func := func';
              in_content := true
            end
          | _ -> ()
        end
      | Pxp_types.E_end_tag (name, _) -> begin
          ignore @@ Stack.pop_exn tags;
          if !in_content then
            begin
              !apply_func !content;
              content := "";
              in_content := false;
            end;
        end
      | Pxp_types.E_char_data str -> begin
          if !in_content then
            content := !content ^ str
        end
      | _ -> ())

let () =
  parse element_func_list

実行結果

satoshi@xubuntu:~/workspace/ocaml-try/pxp$ ./parse_wiki
Title: Wikipedia:アップロードログ 2004年4月
Text: <ul><li>14:46 2004年4月30日 [[利用..
Title: Wikipedia:削除記録/過去ログ 2002年12月
Text: Below is a list of the most recent delet...
Title: アンパサンド
Text: {{記号文字|&amp;}}
[[Image:Trebuchet...
Title: Wikipedia:Sandbox
Text: #REDIRECT [[Wikipedia:サンドボック...
..snip.. 

エンコーディングの指定

<?xml 〜?>ディレクティブでUTF-8を指定してみたが、駄目だった。
configでエンコーディングを指定したら、正しく処理できた。
let config = let open Pxp_types in
  {default_config with encoding = `Enc_utf8}
自動でエンコーディングを認識させる方法はあるのかな?

文字列の連結処理

page要素10個分のxmlファイルのサイズは
-rw-rw-r-- 1 satoshi satoshi  533408 11月 28 23:56 jawiki_10.xml
たった500kb弱なのに、想定よりも処理に時間がかかっている。
satoshi@xubuntu:~/workspace/ocaml-try/pxp$ time ./parse_wiki > /dev/null

real    0m3.361s
user    0m3.168s
sys     0m0.180s
ちなみに実行環境はWindows8.1@Core i3のVirtualBox上のXubuntu14.04で、OCaml4.01.0を使っている。
重い環境だと思うが、メモリ不足にもなっていないのに、3秒以上もかかるのは何故だろう。
E_char_dataのイベントで文字を ^ で連結している処理が駄目なのかな?
      | Pxp_types.E_char_data str -> begin
          if !in_content then
            content := !content ^ str  ← ◆ここを () に変更
        end
文字列連結部分を () にしてみるとどうなるかな?
satoshi@xubuntu:~/workspace/ocaml-try/pxp$ time ./parse_wiki > /dev/null

real    0m0.087s
user    0m0.086s
sys     0m0.000s
おおよそ40倍早くなった。これが原因かー。
JavaのStringBuilderに相当するものは、OCamlでは何になるんだろう。

参考