1

Scala で Unicode 文字を含む文字列を逆にしようとしています。最速の方法を見つけたいです。これまでのところ、私はこのコードを持っています:

import scala.runtime.RichChar

def reverseInPlace(s: String): String = {
   val reverse = new Array[RichChar](s.length)   
   for (i <- (0 to (s.length >> 1))) {
     reverse(i) = s(s.length -i -1)
     reverse(s.length -i -1) = s(i)
   }
   return reverse.mkString
}

def reverseLeft(s: String): String = s.foldLeft("") ( (a,b) => 
    b + a
)

def reverseRight(s: String): String = s.foldRight("") ( (a,b) => 
    b + a
)


def time[R](iterations:Int, block: => R) = {
    val t0 = System.nanoTime()
    for ( i <- 0 to iterations){
       block    // call-by-name
    }
    val t1 = System.nanoTime()
    println("Elapsed time: " + (t1 - t0) + "ns")
}


time(1000, {
    reverseRight("Hello\u0041")
})

time(1000, {
    reverseInPlace("Hello\u0041")
})

time(1000, {
    reverseLeft("Hello\u0041")
})

time(1000, {
    "Hello\u0041".reverse
})

私のmacbook 2013では、次の結果が得られます。

Elapsed time: 37013000ns
Elapsed time: 23592000ns
Elapsed time: 11647000ns
Elapsed time: 5579000ns

しかし、それらの数字は偽の数字だと思います。scala、sbt、および JMH ライブラリを使用して関数を適切にベンチマークするのは誰ですか?

注: コメントから指摘されているように、Java でのマイクロ ベンチマークは深刻なビジネスです ( How do I write a correct micro-benchmark in Java? ) およびhttps://groups.google.com/d/msg/mechanical-sympathyを参照してください。 /m4opvy4xq3U/7lY8x8SvHgwJ . 外部ライブラリを使用せずにマイクロベンチマークを行うべきではない理由について。

4

1 に答える 1

3

これは、フレームワークを使用しないのではなく、Thyme を使用したソリューションです。これは、マイクロベンチマーク フレームワークをゾウのようではなくミクロに感じさせたかったためです。

scala -cp /jvm/Thyme.jar

REPL で実行するために必要なことはこれだけです。

次に、実際に機能する実装が必要です。2つ書きます。

初挑戦：

def revStr(s: String): String = {
  val points = for (i <- s.indices if !s(i).isLowSurrogate) yield s.codePointAt(i)
  new String(points.toArray.reverse,0,points.length)
}

それほど難しくありません。ただし、遅いかもしれません。おそらくボクシングが多いでしょう。より高速なバージョンを試してみましょう:

def reverseString(s: String): String = if (s.length < 2) s else {
  import java.lang.Character.{isLowSurrogate => lo, isHighSurrogate => hi}
  val chars = s.toCharArray
  var i = 0
  var j = s.length - 1
  var swapped = false
  while (i < j) {
    swapped = false
    val a = chars(i)
    val b = chars(j)
    if (lo(a) && j+1 < s.length && hi(chars(j+1))) {
      chars(j) = chars(j+1)
      chars(j+1) = a
      swapped = true
    }
    else chars(j) = a
    if (hi(b) && i > 0 && lo(chars(i-1))) {
      chars(i) = chars(i-1)
      chars(i-1) = b
      swapped = true
    }
    else chars(i) = b
    i += 1
    j -= 1
  }
  if (i==j) {
    val c = chars(i)
    if (lo(c) && j+1 < s.length && hi(chars(j+1))) {
      chars(j) = chars(j+1)
      chars(j+1) = c
    }
    else if (hi(c) && i > 0 && lo(chars(i-1))) {
      chars(i) = chars(i-1)
      chars(i-1) = c
    }
  }
  else if (!swapped && hi(chars(i)) && lo(chars(j))) {
    val temp = chars(i)
    chars(i) = chars(j)
    chars(j) = temp
  }
  new String(chars)
}

ああ。これは、使いやすさではなく速度のために書かれていますが、痛いです。

とにかく、これらをテストしてみましょう。ここでは完全なウォームアップを行っているわけではありませんが、アイデアは得られます。

scala> val th = new ichi.bench.Thyme
th: ichi.bench.Thyme = ichi.bench.Thyme@174580e6

scala> val testString = "This is a \ud800\udc00 test!"
testString: String = This is a  test!

scala> val wrong = th.pbench{ testString.reverse }
Benchmark (327660 calls in 115.2 ms)
  Time:    164.8 ns   95% CI 157.4 ns - 172.3 ns   (n=19)
  Garbage: 97.66 ns   (n=2 sweeps measured)
wrong: String = !tset ?? a si sihT

scala> val slow = th.pbench{ revStr(testString) }
Benchmark (163820 calls in 467.2 ms)
  Time:    749.0 ns   95% CI 742.5 ns - 755.5 ns   (n=18)
  Garbage: 2.112 us   (n=2 sweeps measured)
slow: String = !tset  a si sihT

scala> val fast = th.pbench{ reverseString(testString) }
Benchmark (327660 calls in 36.32 ms)
  Time:    58.19 ns   95% CI 58.10 ns - 58.27 ns   (n=18)
  Garbage: 12.21 ns   (n=1 sweeps measured)
fast: String = !tset  a si sihT

scala> val compare = th.pbenchOff(){revStr(testString)}{reverseString(testString)}
Benchmark comparison (in 430.7 ms)
Significantly different (p ~= 0)
  Time ratio:    0.09495   95% CI 0.08061 - 0.10928   (n=20)
    First     777.9 ns   95% CI 756.0 ns - 799.8 ns
    Second    73.86 ns   95% CI 62.90 ns - 84.81 ns
  Individual benchmarks not fully consistent with head-to-head (p ~= 0)
    First     742.9 ns   95% CI 742.0 ns - 743.9 ns
    Second    58.33 ns   95% CI 58.19 ns - 58.46 ns
compare: String = !tset  a si sihT

したがって、結論として、マイクロベンチマークを実行する場合は、少なくとも最小限のマイクロベンチマーク ツールを使用してください。

また、コード ポイントは煩わしく、配列の直接操作は高速です。

于 2014-04-10T22:27:54.027 に答える