ScalaのRegexParsersで書いたパーサのチューニング方法 #1

注記: 各テストで、ScalaのRegexParsersがすごく遅くなる件の原因と対策 - Qiitaの対策を施したCharSequenceをParserに与えています。

---

CSVパーサを書きます。

まず素直に定義してみます。

Parser.scala

import util.parsing.combinator.RegexParsers

trait Parser extends RegexParsers {
  override val skipWhitespace = false

  lazy val line          : Parser[Result.Element] = ls  ^^^ Result.Row(Nil) | row <~ ls
  lazy val lastLine      : Parser[Result.Element] = eof ^^^ Result.Row(Nil) | row <~ eof | invalidString
  lazy val row           : Parser[Result.Element] = repsep( field, fs ) ^^ { Result.Row(_) }
  lazy val invalidString : Parser[Result.Element] = """.+""".r ^^ { Result.InvalidString(_) }

  def field : Parser[String]
  def fs    : Parser[String]
  def ls    : Parser[String]
  val eof   : Parser[String] = """\z""".r
}

Parser1.scala

class Parser1 extends Parser {

  lazy val fs : Parser[String] = "\t"
  lazy val ls : Parser[String] = "(\r\n|\r|\n)".r

  //長さ0以上の文字列。
  lazy val field             = quoted_field | raw_value

  //QUOTEに囲まれていること。前後にスペースによるパディングが存在してもよい。
  lazy val quoted_field      = padding ~> quote ~> quoted_value <~ quote <~ padding

  //QUOTE以外の文字, エスケープされたQUOTEからなる長さ0以上の文字列。
  lazy val quoted_value      = rep( escaped_quote | not_quote | ls | fs ) ^^ { _.mkString }

  //QUOTE, fs, ls以外から開始し、fs, ls以外が後続する、長さ0以上の文字列。
  lazy val raw_value         = ( not_quote_and_fs ~ rep( not_fs )).? ^^ { case Some(head ~ tail) => head :: tail mkString; case None => "" }

  lazy val padding           = rep( space )
  lazy val escaped_quote     = quote ~ quote ^^^ quote
  lazy val not_quote         = not( quote ) ~> char
  lazy val not_fs            = not( fs ) ~> char
  lazy val not_quote_and_fs  = not( guard(quote) | fs ) ~> char

  lazy val char            = ".".r
  lazy val space           = ' '
  lazy val quote           = '"'
}

1文字1文字をParserがチェックしてていて、想像がつくとおり、すごく遅いです。

> sbt "run Reader3WithParser1 test2.tsv"
total row: 12000
total field: 36000
total char: 47448571
total sec: 39.3310
row (per/sec): 305.1028
field (per/sec): 915.3085
char (per/sec): 1206391.1250

パフォーマンスを改善するためには、

なるべくParserが文字列をチェックする回数を減らすことが重要です。つまり、正規表現で表現可能できる部分をなるべくRegexで定義してしまいます。

Parser2.scala

class Parser2 extends Parser {

  lazy val fs : Parser[String] = "\t"
  lazy val ls : Parser[String] = "(\r\n|\r|\n)".r

  //長さ0以上の文字列。
  lazy val field        : Parser[String] = quoted_field | raw_value

  //QUOTEに囲まれていること。前後にスペースによるパディングが存在してもよい。
  lazy val quoted_field : Parser[String] = " *\"".r ~> quoted_value <~ "\" *".r

  //QUOTE以外の文字, エスケープされたQUOTEからなる長さ0以上の文字列。
  lazy val quoted_value : Parser[String] = rep( "\"\"" ^^^ "\"" | "[^\"]+".r ) ^^ { _.mkString }

  //QUOTE, fs, ls以外から開始し、fs, ls以外が後続する、長さ0以上の文字列。
  lazy val raw_value    : Parser[String] = "([^\t\"\r\n][^\t\r\n]*)?".r
}

> sbt "run Reader3WithParser2 test2.tsv"
total row: 12000
total field: 36000
total char: 47448571
total sec: 3.3910
row (per/sec): 3538.7791
field (per/sec): 10616.3369
char (per/sec): 13992501.0000

いきなり爆速になりました。CSVはルールが単純で、raw_value, quoted_valueをシンプルに記述できたことが効きました。

VS OrangeSignal CSV で 17% 高速です!!

> sbt "run OrangeSignal test2.tsv"
total row: 12001
total field: 36001
total char: 47448571
total sec: 3.9770
row (per/sec): 3017.6013
field (per/sec): 9052.3008
char (per/sec): 11930745.0000

Parserを定義するRegexをハードコードしてしまうと、

可読性や柔軟性がかなり損なわれますが、後者については正規表現を使いこなすことでなんとかなることが多いです。
例えばここのCSVパーサの例において、任意のパターンをフィールドや行の区切りとして与えることは、正規表現のNegative Lookaheadを使えば可能です。

Parser3.scala

class Parser3 extends Parser {

  val LS = "(\r\n|\r|\n)"
  val FS = "\t"

  val ls : Parser[String] = new Regex(LS)
  val fs : Parser[String] = new Regex(FS)

  //長さ0以上の文字列。
  lazy val field        : Parser[String] = quoted_field | raw_field

  //QUOTEに囲まれていること。前後にスペースによるパディングが存在してもよい。
  lazy val quoted_field : Parser[String] = " *\"".r ~> quoted_value <~ "\" *".r

  //QUOTE以外の文字, エスケープされたQUOTEからなる長さ0以上の文字列。
  lazy val quoted_value : Parser[String] = rep( "\"\"" ^^^ "\"" | """[^"]+""".r ) ^^ { _.mkString }

  //QUOTE, fs, ls以外から開始し、fs, ls以外が後続する、長さ0以上の文字列。
  lazy val raw_field    : Parser[String] = s"""(((?!$FS)(?!$LS)[^"])((?!$FS)(?!$LS).)*)?""".r
}

ここで注意しなければいけないことは、先読み否定の((?!ab)(?!b).)+は、abとｂにはマッチしますが、aにはマッチしないことです。Parser3.LSの定義が(\r\n|\r|\n)になっているのはそのためで、もしこれが(\r\n|\n)だった場合、Parser3.raw_fieldの定義は(((?!\t)(?!(\r\n|\n))[^"])((?!\t)(?!(\r\n|\n)).)*)?になってしまい、Parser.lineだと\r\r\nのようなパターン、Parser.lastLineだとCSVファイルが\rで終わっている場合に、フィールド値に\rが紛れ込むバグが発生します。

どうですか？　簡単ですね！

正規表現にはその他様々な機能が備わっています。

どんどんBNFから正規表現に置き換えていきましょう！　楽しくなってきますよ