こっぱみぢんこ

本屋には辛い時代

Book Center よむよむ日野駅前店。駅前とは名ばかりの3分ぐらい歩いたところにある本屋なのだが、閉店していた。バスで前を通っただけなので、潰れたのか改装なのか移転なのか正確なことは判らないのだが、様子から察するに潰れたんだろう。確か俺が大学生の頃に出来たはずだから、郊外の本屋にしては随分と長く持った方だと思うけど、まあ、こんな時代なんだよな。そもそも本が読まれなくなってきているのに、よく本を買う層はAmazonに奪われ、残り僅かな客も文字通りの駅前にできたくまざわ書店に奪われてしまったということか。

先日の最長重複文字列の問題も、この本屋で見つけたもの。閉店間近な店だからこそ、古い雑誌が整理もされずに残っていたんだろう。

そう言えば最長重複文字列の問題は、関数型プログラミングの特集で例題として載ってたんだよな。折角なので、関数型言語でも考えてみよう。具体的にはScalaで。これ、一度さらっと眺めて何となく判ったつもりになり、手軽に取り入れられそうなスタイル／考え方は取り入れたりしていたのだが、言語そのものはすっかり忘れてるんだよね。なので復習を兼ねて。

最長重複文字列（最も長く重複している部分文字列）を探すプログラムを作れ。例えば

Ask not what your country can do for you, but what you can do for your country.

であれば「 can do for you」が最長重複文字列となる。

方針は同じ。接尾辞リスト作って、ソートして、隣り合う要素から同じ部分を抜き出して、一番長いものを返す。

この方針をコードにしたのがこれ。


object T01 {

  def search(s: String) = toSameList(s.tails.toList.sorted).maxBy(_.length)

  def toSameList(list: List[String]) = list.zip(list.tail).map(t => getSamePart(t._1, t._2))

  def getSamePart(s1: String, s2: String) = s1.take(getSameLen(s1, s2))

  def getSameLen(s1: String, s2: String) = s1.zip(s2).takeWhile(t => t._1 == t._2).length

  def main(args: Array[String]) {
    println(search("Ask not what your country can do for you, but what you can do for your country."))
  }
}

短い。 JavaScript版が27行だったのに対して、Scala版は9行。テスト用の部分を除けば4行。

短く書けるのはライブラリが充実しているからでもあって、これがそのまま言語のパワーって訳ではないのだが、いや、ライブラリが充実できるのは言語のパワーがあればこそ、か。鶏と卵みたいなものか。ま、とにかく嵌ればかなり短く書けるということだな。

以下、各関数について。

search(s: String): String

渡された文字列 s の最長重複文字列を返す。

JavaScriptだと自分で書く必要があった、接尾辞リストを作ってソートするって処理がたった1行で済んでしまう。 s.tails.toList.sorted 文字列のリストから最長のものを選び出すのもやっぱり1行。 list.maxBy(_.length) 前者は充実したライブラリの威力で、後者は高階関数の威力。

toSameList(list: List[String]): List[String]

接尾辞リストから、隣同士の同じ文字列を取り出してリストを作る。

同じリストの隣同士をペアにするには list.zip(list.tail) とすればいい。結果だけ見ると簡単なのだが、慣れていないと、これだけのことを思いつくのに随分と時間がかかるんだよな。

getSamePart(s1: String, s2: String): String

渡された二つの文字列から、先頭から続く同じ文字列を取り出して返す。

実際には、二つの文字列を下請け関数に渡して同じ文字列の長さを取得し、その長さ分を先頭から切り出して返す。

getSameLen(s1: String, s2: String): Int

渡された二つの文字列から、先頭から続く同じ文字列の長さを返す。

文字列を文字のリストと見て二つの文字列を zip し、その結果であるペアのリストで、先頭からペアの値が同じものを取り出してリストを作る。この辺りの考え方は、Haskell版の模範解答そのまま。

ついでなので、最長N回重複の方も。


object T02 {

  def search(s: String, n: Int) = toSameList(s.tails.toList.sorted, n).maxBy(_.length)

  def toSameList(list: List[String], n: Int): List[String] = {
    n match {
      case 1 => list
      case _ => toSameList(list.zip(list.tail).map(t => getSamePart(t._1, t._2)), n - 1)
    }
  }

  def getSamePart(s1: String, s2: String) = s1.take(getSameLen(s1, s2))

  def getSameLen(s1: String, s2: String) = s1.zip(s2).takeWhile(t => t._1 == t._2).length

  def main(args: Array[String]) {
    println(search("Ask not what your country can do for you, but what you can do for your country.", 2))
  }
}

5行増えた。

さっきのとの違いは、 search に出現回数を指定する引数が増えたことと、 toSameList が再帰呼び出しになったこと。

これがScalaらしい記述スタイルなのかは判らないのだが、JavaScript版と比べると劇的にコードが短くなっている。 Javaと比べたら、コード量の改善の割合は更に大きなものになるだろう。慣れれば確実に生産性が上がるんだろうけど、現時点では、俺の生産性が酷いんだよな。時間のほとんどは、実はAPIドキュメントを漁ることで費やしていたりしてるのだ。何が用意されてて何が出来るのか、ほぼ知らない世界。スカラの知識がスッカラカンなんて洒落にもならない。

2013 08 20

本屋には辛い時代