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

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

---

문제는 두 부분으로 나뉩니다. 첫 번째는 개념적입니다. 다음은 Scala에서 동일한 질문을보다 구체적으로 살펴 봅니다.

1. 프로그래밍 언어에서 변경 불가능한 데이터 구조 만 사용하면 실제로 특정 알고리즘 / 로직을 구현하는 데 본질적으로 계산 비용이 더 많이 듭니까? 이것은 불변성이 순전히 기능적인 언어의 핵심 신조라는 사실을 이끌어냅니다. 이에 영향을 미치는 다른 요인이 있습니까?
2. 좀 더 구체적인 예를 들어 보겠습니다. Quicksort 는 일반적으로 메모리 내 데이터 구조에서 변경 가능한 작업을 사용하여 학습되고 구현됩니다. 변경 가능한 버전과 비교 가능한 계산 및 저장 오버 헤드를 사용하여 PURE 기능적 방식으로 그러한 것을 어떻게 구현합니까? 특히 Scala에서. 아래에 몇 가지 조잡한 벤치 마크를 포함했습니다.

자세한 내용은:

저는 명령형 프로그래밍 배경 (C ++, Java)에서 왔습니다. 저는 함수형 프로그래밍, 특히 Scala를 탐구 해 왔습니다.

순수 함수형 프로그래밍의 몇 가지 기본 원칙 :

1. 기능은 일류 시민입니다.
2. 함수에는 부작용이 없으므로 객체 / 데이터 구조는 변경할 수 없습니다 .

현대의 JVM 은 객체 생성에 매우 효율적이고 가비지 수집 은 수명이 짧은 객체의 경우 매우 저렴하지만 객체 생성을 최소화하는 것이 여전히 낫습니다. 적어도 동시성과 잠금이 문제가되지 않는 단일 스레드 애플리케이션에서. Scala는 하이브리드 패러다임이므로 필요한 경우 변경 가능한 객체로 명령형 코드를 작성하도록 선택할 수 있습니다. 그러나 객체를 재사용하고 할당을 최소화하기 위해 수년을 보냈던 사람입니다. 나는 그것을 허용하지 않을 생각의 학교에 대해 잘 이해하고 싶습니다.

특정한 경우에, 이 튜토리얼 6에 있는 이 코드 스 니펫에 약간 놀랐습니다 . Java 버전의 Quicksort와 깔끔하게 보이는 Scala 구현이 있습니다.

여기에 구현을 벤치마킹하려는 시도가 있습니다. 상세한 프로파일 링을하지 않았습니다. 그러나 제 생각에는 할당 된 개체 수가 선형 (재귀 호출 당 하나씩)이기 때문에 Scala 버전이 더 느립니다. 테일 콜 최적화가 작동 할 가능성이 있습니까? 내가 맞다면 Scala는 자체 재귀 호출에 대한 테일 호출 최적화를 지원합니다. 그래서 그것은 단지 그것을 돕고 있어야합니다. Scala 2.8을 사용하고 있습니다.

자바 버전

public class QuickSortJ {

    public static void sort(int[] xs) {
      sort(xs, 0, xs.length -1 );
    }

    static void sort(int[] xs, int l, int r) {
      if (r >= l) return;
      int pivot = xs[l];
      int a = l; int b = r;
      while (a <= b){
        while (xs[a] <= pivot) a++;
        while (xs[b] > pivot) b--;
        if (a < b) swap(xs, a, b);
      }
      sort(xs, l, b);
      sort(xs, a, r);
    }

    static void swap(int[] arr, int i, int j) {
      int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
    }
}

Scala 버전

object QuickSortS {

  def sort(xs: Array[Int]): Array[Int] =
    if (xs.length <= 1) xs
    else {
      val pivot = xs(xs.length / 2)
      Array.concat(
        sort(xs filter (pivot >)),
        xs filter (pivot ==),
        sort(xs filter (pivot <)))
    }
}

구현을 비교하기위한 스칼라 코드

import java.util.Date
import scala.testing.Benchmark

class BenchSort(sortfn: (Array[Int]) => Unit, name:String) extends Benchmark {

  val ints = new Array[Int](100000);

  override def prefix = name
  override def setUp = {
    val ran = new java.util.Random(5);
    for (i <- 0 to ints.length - 1)
      ints(i) = ran.nextInt();
  }
  override def run = sortfn(ints)
}

val benchImmut = new BenchSort( QuickSortS.sort , "Immutable/Functional/Scala" )
val benchMut   = new BenchSort( QuickSortJ.sort , "Mutable/Imperative/Java   " )

benchImmut.main( Array("5"))
benchMut.main( Array("5"))

결과

연속 5 회 실행에 대한 시간 (밀리 초)

Immutable/Functional/Scala    467    178    184    187    183
Mutable/Imperative/Java        51     14     12     12     12

---

여기에 몇 가지 오해 가 있기 때문에 몇 가지 요점을 명확히하고 싶습니다.

• "in-place"quicksort는 실제로 in-place가 아닙니다 (그리고 quicksort는 정의에 의해 in-place 가 아닙니다 ). 재귀 단계를위한 스택 공간 형태의 추가 스토리지가 필요합니다. 이는 최상의 경우 O (log n ) , 최악의 경우 O ( n ) 순서입니다.

• 배열에서 작동하는 Quicksort의 기능적 변형을 구현하면 목적을 달성 할 수 없습니다. 배열은 불변하지 않습니다.

• Quicksort의 "적절한"기능 구현은 변경 불가능한 목록을 사용합니다. 물론 제자리는 아니지만 절차 적 제자리 버전 과 동일한 최악의 점근 런타임 ( O ( n ^ 2)) 및 공간 복잡성 ( O ( n ))을가집니다.

  평균적으로 실행 시간은 현재 위치 변형 ( O ( n log n )) 의 실행 시간 과 동일합니다 . 그러나 공간 복잡도는 여전히 O ( n )입니다.

---

기능적 퀵 정렬 구현 에는 두 가지 명백한 단점 이 있습니다. 다음에서는 Haskell 도입부 에서 Haskell (나는 Scala를 모릅니다 ...)의이 참조 구현을 고려해 보겠습니다 .

qsort []     = []
qsort (x:xs) = qsort lesser ++ [x] ++ qsort greater
    where lesser  = (filter (< x) xs)
          greater = (filter (>= x) xs)

1. 첫 번째 단점 은 매우 유연하지 않은 피벗 요소를 선택 하는 것입니다. 최신 퀵 정렬 구현의 강점은 현명한 피벗 선택에 크게 의존합니다 ( Bentley 등의 "정렬 기능 엔지니어링" 비교 ). 위의 알고리즘은 그 점에서 열악하므로 평균 성능이 상당히 저하됩니다.

2. 둘째,이 알고리즘은 O ( n ) 연산 인 목록 연결 (목록 생성 대신 )을 사용합니다. 이것은 점근 적 복잡성에 영향을주지 않지만 측정 가능한 요소입니다.

세 번째 단점은 다소 숨겨져 있습니다. "in-place"변형과 달리이 구현 은 목록의 cons 셀에 대해 힙에서 메모리를 지속적으로 요청 하고 잠재적으로 모든 곳에 메모리를 분산시킵니다. 결과적으로이 알고리즘은 캐시 지역성 이 매우 낮습니다 . 현대 함수형 프로그래밍 언어의 스마트 할당자가이 문제를 완화 할 수 있는지는 모르겠습니다.하지만 현대 컴퓨터에서는 캐시 미스가 주요 성능 킬러가되었습니다.

---

결론은 무엇입니까? 다른 사람들과 달리 퀵 정렬은 본질적으로 필수적이며 FP 환경에서 제대로 수행되지 않는 이유입니다. 오히려 나는 퀵 정렬이 기능적 알고리즘의 완벽한 예라고 주장합니다. 불변 환경으로 원활하게 변환되고 점근 적 실행 시간과 공간 복잡성이 절차 적 구현과 동등하며 절차 적 구현조차 재귀를 사용합니다.

그러나이 알고리즘 은 변경 불가능한 도메인으로 제한 될 때 여전히 성능이 저하됩니다. 그 이유는 알고리즘이 배열에서만 효율적으로 수행 할 수있는 많은 (때로는 낮은 수준의) 미세 조정의 이점을 누릴 수있는 독특한 속성을 가지고 있기 때문입니다. Quicksort에 대한 순진한 설명은 이러한 모든 복잡성을 놓치고 있습니다 (기능 및 절차 변형 모두에서).

"정렬 기능 엔지니어링"을 읽은 후에는 더 이상 퀵 정렬을 우아한 알고리즘이라고 생각할 수 없습니다. 효율적으로 구현하면 엔지니어의 작품이 아니라 투박한 엉망입니다 (엔지니어링의 가치를 떨어 뜨리는 것이 아닙니다! 이것은 자체적 인 미학을 가지고 있습니다).

---

그러나 나는 또한이 점이 퀵 정렬에만 해당된다는 점을 지적하고 싶습니다. 모든 알고리즘이 동일한 종류의 저수준 조정을 수행 할 수있는 것은 아닙니다. 많은 알고리즘과 데이터 구조 가 불변 환경에서 성능 손실없이 실제로 표현 될 수 있습니다.

그리고 불변성 은 값 비싼 복사본이나 스레드 간 동기화의 필요성을 제거하여 성능 비용을 낮출 수도 있습니다 .

그래서 원래의 질문에 대답하기 위해“ 불변성은 비용이 많이 듭니까? ”– 퀵 정렬의 특별한 경우에는 실제로 불변성의 결과 인 비용이 있습니다. 그러나 일반적으로, 전혀 .

---

함수형 프로그래밍의 벤치 마크로 여기에는 여러 가지 잘못된 점이 있습니다. 주요 내용은 다음과 같습니다.

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

따라서이 비교는 고성능 코드를 작성하기 위해 언어 (및 알고리즘)를 자세히 이해해야하는 훌륭한 예시입니다. 그러나 FP와 비 FP의 비교는 그리 좋지 않습니다. 원하는 경우 Computer Languages ​​Benchmark Game에서 Haskell 대 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 메서드를 작성할 수도 있습니다. 이렇게하면 속도가 약간 더 빨라질 수 있습니다.)

---

I don't think the Scala version is actually tail recursive, since you are using Array.concat.

Also, just because this is idiomatic Scala code, this doesn't mean it is the best way to do it.

The best way to do this would be to use one of Scala's built-in sorting functions. That way you get the immutability guarantee and know you have a speedy algorithm.

See Stack Overflow question How do I sort an array in Scala? for an example.

---

Immutability is not expensive. It sure can be expensive if you measure a small subset of the tasks a program have to do, and pick a solution based on mutability to boot -- such as measuring quicksort.

To put it simply, you don't quicksort when using purely functional languages.

Let's consider this from another angle. Let's consider these two functions:

// Version using mutable data structures
def tailFrom[T : ClassManifest](arr: Array[T], p: T => Boolean): Array[T] = {
  def posIndex(i: Int): Int = {
    if (i < arr.length) {
      if (p(arr(i)))
        i
      else
        posIndex(i + 1)
    } else {
      -1
    }
  }

  var index = posIndex(0)

  if (index < 0) Array.empty
  else {
    var result = new Array[T](arr.length - index)
    Array.copy(arr, index, result, 0, arr.length - index)
    result
  }
}

// Immutable data structure:

def tailFrom[T](list: List[T], p: T => Boolean): List[T] = {
  def recurse(sublist: List[T]): List[T] = {
    if (sublist.isEmpty) sublist
    else if (p(sublist.head)) sublist
    else recurse(sublist.tail)
  }
  recurse(list)
}

Benchmark THAT, and you'll find that the code using mutable data structures has much worse performance, because it needs to copy the array, while the immutable code need not concern itself with that.

When you program with immutable data structures, you structure your code to take advantage of its strengths. It is not simply the data type, or even individual algorithms. The program will be designed in a different manner.

Which is why benchmarking is usually meaningless. Either you choose algorithms that are natural to one style or another, and that style wins, or you benchmark the whole application, which is often impractical.

---

Sorting an array is, like, the most imperative task in the universe. It is not surprising that many elegant 'immutable' strategies/implementations fail poorly on a 'sort an array' microbenchmark. This does not imply that immutability is expensive "in general", though. There are many tasks where immutable implementations will perform comparably to mutable ones, but array sorting often is not one of them.

---

If you're simply rewriting your imperative algorithms and data structures into functional language it indeed will be expensive and useless. To make the things shine, you should use the features available only in functional programming: data stuctures persistence, lazy evaluations etc.

---

The cost of immutability in Scala

Here is a version that is nearly as fast than the Java one. ;)

object QuickSortS {
  def sort(xs: Array[Int]): Array[Int] = {
    val res = new Array[Int](xs.size)
    xs.copyToArray(res)
    (new QuickSortJ).sort(res)
    res
  }
}

This version makes a copy of the array, sorts it in place using the Java version and returns the copy. Scala does not force you to use immutable structure internally.

So the benefit of Scala is that you can leverage mutability and immutability as you see fit. The disadvantage is that if you do that wrong you don't really get the benefits of immutability.

---

QuickSort is known to be faster when done in-place, so this is hardly a fair comparison!

Having said that... Array.concat? If nothing else, you're showing how a collection type optimised for imperative programming is particularly slow when you try and use it in a functional algorithm; almost any other choice would be faster!

---

Another very important point to consider, perhaps the most important issue when comparing the two approaches is: "how well does this scale out to multiple nodes/cores?"

Chances are, if you're looking for an immutable quicksort then you're doing so because you actually want a parallel quicksort. Wikipedia has some citations on this subject: http://en.wikipedia.org/wiki/Quicksort#Parallelizations

The scala version can simply fork before the function recurses, allowing it to very quickly sort a list containing billions of entries if you have enough cores available.

Right now, the GPU in my system has 128 cores available to me if I could just run the Scala code on it, and this is on a simple desktop system two years behind the current generation.

How would that stack up against the single-threaded imperative approach I wonder...

Perhaps the more important question is therefore:

"Given that individual cores aren't going to get any faster, and synchronisation/locking presents a real challenge for parallelisation, is mutability expensive?"

---

It's been said that OO programming uses abstraction to hide complexity, and functional programming uses immutability to remove complexity. In the hybrid world of Scala we can use OO to hide the imperative code leaving application code none the wiser. Indeed the collections libraries use plenty of imperative code but that doesn't mean we shouldn't use them. As others have said, used with care, you really get the best of both worlds here.

참고URL : https://stackoverflow.com/questions/4101924/functional-programming-is-immutability-expensive