[java] 함수형 프로그래밍-불변성은 비용이 많이 듭니까? [닫은]

함수형 프로그래밍의 벤치 마크로서 이것에는 많은 문제가 있습니다. 주요 내용은 다음과 같습니다.

• boxed / unboxed해야 할 수있는 기본 요소를 사용하고 있습니다. 원시 객체를 래핑하는 오버 헤드를 테스트하려는 것이 아니라 불변성을 테스트하려는 것입니다.
• 제자리 작업이 비정상적으로 효과적인 (그리고 그럴 가능성이있는) 알고리즘을 선택했습니다. 변경 가능하게 구현 될 때 더 빠른 알고리즘이 있음을 보여주고 싶다면 이것은 좋은 선택입니다. 그렇지 않으면 오해의 소지가 있습니다.
• 잘못된 타이밍 기능을 사용하고 있습니다. 사용 System.nanoTime.
• 벤치 마크가 너무 짧아서 JIT 컴파일이 측정 된 시간의 중요한 부분이 아니라고 확신 할 수 없습니다.
• 배열은 효율적인 방식으로 분할되지 않습니다.
• 배열은 변경 가능하므로 FP와 함께 사용하는 것은 어쨌든 이상한 비교입니다.

따라서이 비교는 고성능 코드를 작성하기 위해 언어 (및 알고리즘)를 자세히 이해해야하는 훌륭한 예시입니다. 그러나 FP와 비 FP의 비교는 그리 좋지 않습니다. 원한다면 Computer Languages ​​Benchmark Game에서 Haskell vs. C ++를 확인하십시오 . 집으로 가져가는 메시지는 패널티가 일반적으로 2 또는 3 배 정도라는 것입니다.하지만 실제로는 다릅니다. (Haskell 사람들이 가능한 가장 빠른 알고리즘을 작성했다는 약속은 없지만 적어도 그들 중 일부는 아마도 시도했을 것입니다! 그런 다음 Haskell 중 일부는 C 라이브러리를 호출합니다 ….)

이제 Quicksort의보다 합리적인 벤치 마크를 원한다고 가정하고 이것이 아마도 FP 대 가변 알고리즘의 최악의 경우 중 하나임을 인식하고 데이터 구조 문제를 무시합니다 (즉, 변경 불가능한 배열을 가질 수있는 척).

object QSortExample {
  // Imperative mutable quicksort
  def swap(xs: Array[String])(a: Int, b: Int) {
    val t = xs(a); xs(a) = xs(b); xs(b) = t
  }
  def muQSort(xs: Array[String])(l: Int = 0, r: Int = xs.length-1) {
    val pivot = xs((l+r)/2)
    var a = l
    var b = r
    while (a <= b) {
      while (xs(a) < pivot) a += 1
      while (xs(b) > pivot) b -= 1
      if (a <= b) {
        swap(xs)(a,b)
        a += 1
        b -= 1
      }
    }
    if (l<b) muQSort(xs)(l, b)
    if (b<r) muQSort(xs)(a, r)
  }

  // Functional quicksort
  def fpSort(xs: Array[String]): Array[String] = {
    if (xs.length <= 1) xs
    else {
      val pivot = xs(xs.length/2)
      val (small,big) = xs.partition(_ < pivot)
      if (small.length == 0) {
        val (bigger,same) = big.partition(_ > pivot)
        same ++ fpSort(bigger)
      }
      else fpSort(small) ++ fpSort(big)
    }
  }

  // Utility function to repeat something n times
  def repeat[A](n: Int, f: => A): A = {
    if (n <= 1) f else { f; repeat(n-1,f) }
  }

  // This runs the benchmark
  def bench(n: Int, xs: Array[String], silent: Boolean = false) {
    // Utility to report how long something took
    def ptime[A](f: => A) = {
      val t0 = System.nanoTime
      val ans = f
      if (!silent) printf("elapsed: %.3f sec\n",(System.nanoTime-t0)*1e-9)
      ans
    }

    if (!silent) print("Scala builtin ")
    ptime { repeat(n, {
      val ys = xs.clone
      ys.sorted
    }) }
    if (!silent) print("Mutable ")
    ptime { repeat(n, {
      val ys = xs.clone
      muQSort(ys)()
      ys
    }) }
    if (!silent) print("Immutable ")
    ptime { repeat(n, {
      fpSort(xs)
    }) }
  }

  def main(args: Array[String]) {
    val letters = (1 to 500000).map(_ => scala.util.Random.nextPrintableChar)
    val unsorted = letters.grouped(5).map(_.mkString).toList.toArray

    repeat(3,bench(1,unsorted,silent=true))  // Warmup
    repeat(3,bench(10,unsorted))     // Actual benchmark
  }
}

기능적 Quicksort에 대한 수정 사항을 확인하여 가능한 경우 데이터를 한 번만 살펴보고 기본 제공 정렬과 비교합니다. 실행하면 다음과 같은 결과가 나타납니다.

Scala builtin elapsed: 0.349 sec
Mutable elapsed: 0.445 sec
Immutable elapsed: 1.373 sec
Scala builtin elapsed: 0.343 sec
Mutable elapsed: 0.441 sec
Immutable elapsed: 1.374 sec
Scala builtin elapsed: 0.343 sec
Mutable elapsed: 0.442 sec
Immutable elapsed: 1.383 sec

따라서 자신의 정렬을 작성하는 것이 나쁜 생각이라는 것을 배우는 것 외에도 후자가 다소 신중하게 구현되면 변경 불가능한 퀵 정렬에 대해 ~ 3 배의 패널티가 있음을 발견했습니다. (작은 것, 같은 것, 피벗보다 큰 것의 세 가지 배열을 반환하는 trisect 메서드를 작성할 수도 있습니다. 이렇게하면 속도가 약간 더 빨라질 수 있습니다.)