ScalazというScalaのライブラリ内にCordというデータ構造があります。今日はこの話です。

Cordとは

以下は引用です。

A Cord is a purely functional data structure for efficiently storing and manipulating Strings that are potentially very long. Very similar to Rope[Char], but with better constant factors and a simpler interface since it’s specialized for Strings. 引用元：http://docs.typelevel.org/api/scalaz/stable/7.0.4/doc/index.html#scalaz.Cord

とても長い可能性のある文字列を効率的に格納・操作するための純粋関数型データ構造らしいです。

これだけではよく分かりませんが、長い文字列を扱う場合はStringよりCordの方が良さそうです。

実際に試してみることにします。

文字列の結合

import scalaz.Cord

object Main {
  def main(args: Array[String]) {
    var cord: Cord = Cord("ab")
    cord = cord :+ "c"
    println(cord) //abc

    var cord2: Cord = Cord("23")
    cord2 = "1" +: cord2
    println(cord2) //123

  }
}

:+または+:で行います。当然ながら関数型なので:+で文字列をアペンドしてもそれ自体は変わりません。ですので代入しています。

文字列の切り取りなど

import scalaz.Cord

object Main {
  def main(args: Array[String]) {
    var cord: Cord = Cord("abcdef")

    println(cord.drop(1)) // bcdef
    println(cord.tail) // bcdef 内部的にdrop(1)と同じ
    println(cord.take(3)) // abc
    println(cord.split(3)) // (abc,def) Tuple 2つのCodeになる
    println(cord.toList) // List(a,b,c,d,e,f)
  }
}

dropで先頭からn文字捨てます。tailは２文字目以降を返します。takeは先頭からn文字取ります。splitは指定indexで区切って2つのCordを作ります。toListはCharのListです。

結合の速度比較

StringとCordとStringBuilderで文字列結合の速度を比較してみようと思います。

以下のようなコードを用意し、実行してみます。

import scala.util.Random
import scalaz._

object Main {
  def main(args: Array[String]) {
    Random.setSeed(1)
    val loop: Int = 10000

    // loopの数だけ文字列を結合させて速度を測る

    // Cordの場合
    timeOf {
      var c: Cord = Cord("")

      for (i <- 0 until loop) {
        c = c :+ Random.nextString(1)
      }
    }

    // Stringの場合
    timeOf {
      var str: String = ""
      for (i <- 0 until loop) {
        str = str + Random.nextString(1)
      }
    }

    // StringBuilderの場合
    timeOf {
      val sb: StringBuilder = new StringBuilder("")

      for (i <- 0 until loop) {
        sb.append(Random.nextString(1))
      }
      sb.toString()
    }

  }

  def timeOf[A](f: => A): A = {
    val start = System.currentTimeMillis
    val result = f
    val end = System.currentTimeMillis
    println("[Time] %s ms".format(end - start))
    result
  }
}

上記のコードのloop部分を1万、10万、100万で変えて実行してみます。

	1万回	10万回	100万回
Cord	800 ms	1188 ms	7115 ms
String	234 ms	6376 ms	計測不能
StringBuilder	69 ms	30ms	351 ms

初め、Cordが思ったより早くなくて、あれ？と思ったのですが、本当に長い文字列となると話は別ですね。Stringでは話にならないレベルでもCordならなんとかなりました。StringBuilderは流石ですね。

色々パラメータ変えてみたりして試しましたが、個人的に長い文字列になる場合にCordを使うのではなく、appendする回数が多くなる可能性があるときにCord使うと良いのかなと思いました。