代码之家  ›  专栏  ›  技术社区  ›  smartnut007

函数式编程-不变性代价高昂吗?[关闭]

  •  92
  • smartnut007  · 技术社区  · 14 年前

    这个问题分为两部分。首先是概念性的。接下来在Scala中更具体地讨论同一个问题。

    1. 在编程语言中只使用不可变的数据结构是否会使实现某些算法/逻辑在实际中的计算成本更高?这就引出了这样一个事实:不变性是纯函数式语言的核心原则。有其他因素影响吗?
    2. 让我们举一个更具体的例子。 Quicksort

    更多细节:

    纯函数式编程的一些基本原则:

    1. 职能是头等公民。
    2. 函数没有副作用,因此对象/数据结构 immutable .

    即使是现代的 JVMs garbage collection 对于生命周期短的物体来说是很便宜的,也许还是尽量减少物体的产生为好?至少在单线程应用程序中,并发和锁定不是问题。由于Scala是一个混合的范例,如果需要的话,可以选择用可变对象编写命令式代码。但是,作为一个花了很多年试图重用对象和最小化分配的人。我想很好的理解学校的思想,甚至不允许这样。

    作为一个具体的例子,我对 this tutorial 6 . 它有一个Java版本的Quicksort,后面是一个外观整洁的Scala实现。

    Java版本

    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 <)))
        }
    }
    

    比较实现的Scala代码

    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"))
    

    连续五次运行的时间(毫秒)

    Immutable/Functional/Scala    467    178    184    187    183
    Mutable/Imperative/Java        51     14     12     12     12
    
    9 回复  |  直到 9 年前
        1
  •  103
  •   Konrad Rudolph    14 年前

    因为有几个 我在这儿转转,想澄清一些问题。

    • 就地快速排序并不真正到位(快速排序是 根据定义)。它需要以堆栈空间的形式为递归步骤额外存储,其顺序为 O型 n个 )在最好的情况下,但是 ( )在最坏的情况下。

    • 实现对数组进行操作的quicksort函数变体会达不到目的。数组永远是不可变的。

    • quicksort的正确功能实现使用不可变列表。它当然不在适当的位置,但是它得到了相同的最坏情况渐近运行时( O型 ( ^ 2)和空间复杂度 O型 n个 ))作为程序就地版本。

      仍然 与就地变量相同( ( 日志 n个 O型 ( ).


    两个明显的缺点 功能快速排序实现的。在下面,让我们从 Haskell introduction :

    qsort []     = []
    qsort (x:xs) = qsort lesser ++ [x] ++ qsort greater
        where lesser  = (filter (< x) xs)
              greater = (filter (>= x) xs)
    
    1. 第一个缺点是 这是非常不灵活的。现代quicksort实现的优势在很大程度上依赖于对轴心的明智选择(比较 “Engineering a sort function” by Bentley et al. ). 上述算法在这方面很差,这会大大降低平均性能。

    2. 其次,该算法使用 (而不是列表结构)它是 O型 ( n个 )操作。这并不影响渐近复杂性,但它是一个可测量的因素。

    第三个缺点有些隐蔽:与就地变量不同,这个实现 不断从堆中请求内存 对于列表中的cons单元,可能会将内存分散到所有地方。因此,该算法具有 缓存位置差 . 我不知道现代函数式编程语言中的智能分配器是否能缓解这种情况,但在现代计算机上,缓存丢失已成为一个主要的性能杀手。


    结论是什么?

    但是这个算法 当被约束到不可变域时,性能更差。其原因是,该算法具有一个独特的特性,即受益于许多(有时是低级的)微调,这些微调只能在阵列上有效地执行。对quicksort的简单描述忽略了所有这些复杂性(在函数和过程变量中)。

    在阅读了工程排序函数之后,我不再认为快速排序是一种优雅的算法。有效实施,这是一个笨重的混乱,一个工程师的作品,而不是一个艺术家(不贬值工程!)!这有自己的审美观)。


    但我也要指出,这一点是特别的快速排序。并不是所有的算法都能接受同样的低级调整。很多算法和数据结构 可以 在不可变的环境中不损失性能。

    不变性甚至可以 不需要昂贵的拷贝或跨线程同步,从而降低性能成本。

    不变性昂贵吗? 在quicksort的特殊情况下,有一个成本确实是不变性的结果。但总的来说,

        2
  •  41
  •   igouy peenut    9 年前

    作为函数式编程的基准,这有很多问题。亮点包括:

    • 您使用的是原语,它可能必须被装箱/解除装箱。您不是要测试包装基本对象的开销,而是要测试不变性。
    • 您使用了错误的计时功能。使用 System.nanoTime
    • 基准测试太短了,您无法确信JIT编译不会成为度量时间的重要部分。
    • 数组没有以有效的方式拆分。
    • 数组是可变的,所以将它们与FP一起使用是一个奇怪的比较。

    因此,这个比较是一个很好的说明,为了编写高性能的代码,您必须详细理解您的语言(和算法)。但这不是一个很好的比较FP与非FP。如果你想的话,去看看 Haskell vs. C++ at the Computer Languages Benchmark Game

    现在,假设您确实需要一个更合理的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
      }
    }
    

    请注意对函数式快速排序的修改,以便尽可能只遍历一次数据,并与内置排序进行比较。当我们运行它时,会得到如下信息:

    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
    

    因此,除了知道尝试编写自己的排序是一个坏主意之外,我们还发现,如果对不可变的quicksort进行某种程度的谨慎实现,则它将受到大约3倍的惩罚。(还可以编写一个三等分方法,返回三个数组:小于、等于和大于轴的数组。这可能会稍微加快速度。)

        3
  •  10
  •   Community CDub    8 年前

    我不认为Scala版本实际上是尾部递归的,因为您正在使用 Array.concat

    另外,仅仅因为这是习惯性的Scala代码,并不意味着这是最好的方法。

    最好的方法是使用Scala内置的排序函数之一。这样你就得到了不变性保证,并且知道你有一个快速的算法。

    参见堆栈溢出问题 How do I sort an array in Scala?

        4
  •  8
  •   Daniel C. Sobral    14 年前

    不变性并不昂贵。如果您测量一个程序必须执行的任务的一小部分,并根据启动的易变性选择解决方案(例如测量快速排序),那么它肯定会很昂贵。

    让我们从另一个角度来考虑这个问题。让我们考虑这两个函数:

    // 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)
    }
    

    当您使用不可变的数据结构进行编程时,您可以对代码进行结构调整,以利用其优势。它不仅仅是数据类型,甚至是单个算法。程序将是 设计 以不同的方式。

    这就是为什么标杆管理通常毫无意义。要么你选择一种或另一种风格的自然算法,并且这种风格获胜,要么你对整个应用程序进行基准测试,这通常是不切实际的。

        5
  •  7
  •   Brian    14 年前

    排序数组是宇宙中最重要的任务。毫不奇怪,许多优雅的“不可变”策略/实现在“排序数组”微基准上失败。不过,这并不意味着不变性“总体上”是昂贵的。在许多任务中,不可变实现的性能与可变实现的性能相当,但数组排序通常不是其中之一。

        6
  •  7
  •   Vasil Remeniuk    14 年前

    如果你只是简单地将你的命令式算法和数据结构重写成函数式语言,这确实是昂贵和无用的。为了让事情变得更好,您应该使用函数式编程中的特性:数据结构持久性、惰性计算等。

        7
  •  7
  •   huynhjl bhericher    14 年前

    斯卡拉

    这是一个几乎和Java版本一样快的版本。;)

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

    此版本生成数组的副本,使用Java版本对其进行排序并返回副本。Scala不会强制您在内部使用不可变结构。

    因此Scala的好处是,您可以根据需要利用可变和不可变。缺点是,如果你做错事,你并不能真正得到不变性的好处。

        8
  •  7
  •   Kevin Wright    14 年前

    众所周知,QuickSort在执行时会更快,所以这很难进行公平的比较!

    说了这些。。。Array.concat?


    另一个 非常 这个 比较这两种方法时,最重要的问题是:“这种扩展到多个节点/核心的效果如何?”

    http://en.wikipedia.org/wiki/Quicksort#Parallelizations

    scala版本可以在函数递归之前简单地分叉,如果有足够的可用内核,它可以非常快速地对包含数十亿个条目的列表进行排序。

    与单线程命令式方法相比,这种方法有什么不同呢。。。

    因此,或许更重要的问题是:

    “考虑到单个核不会变得更快,同步/锁定对并行化来说是一个真正的挑战,可变性是否昂贵?”

        9
  •  2
  •   Ben Hardy    14 年前

    有人说,面向对象编程使用抽象来隐藏复杂性,而功能编程使用不可变来消除复杂性。在Scala的混合世界中,我们可以使用OO隐藏命令式代码,让应用程序代码变得一窍不通。实际上,集合库使用了大量的命令式代码,但这并不意味着我们不应该使用它们。正如其他人所说,小心使用,你真的得到了最好的两个世界在这里。