函数式编程 – 不变性昂贵？

问题分两部分。 首先是概念。 接下来在Scala中更具体地看待同一个问题。

1. 在编程语言中只使用不可变的数据结构是否使实现某些algorithm/逻辑本质上在计算上更加昂贵？ 这引出了一个事实，即不变性是纯粹function性语言的核心原则。 还有其他因素会影响到这一点吗？
2. 我们来举一个更具体的例子。 通常在内存数据结构中使用可变操作来教授和实现快速sorting。 如何以PUREfunction的方式实现这样的事情，并且可变计算和存储开销相当于可变版本。 具体在斯卡拉。 下面列出了一些粗略的基准。

更多细节：

我来自命令式编程背景（C ++，Java）。 我一直在探索函数式编程，特别是Scala。

纯函数式编程的一些主要原则：

1. 职能是一等公民。
2. 函数没有副作用，因此对象/数据结构是不可变的 。

尽pipe现代的JVM对于创build对象非常有效，而且垃圾收集对于短期对象来说是非常便宜的，但是最小化对象创build的权利可能更好一些？ 至less在并发和locking不是问题的单线程应用程序中。 由于Scala是一个混合模式，如果有必要，可以select使用可变对象编写命令代码。 但是，作为一个花了很多年的人试图重用对象，并尽量减less分配。 我想对这个甚至不允许的思想学派有一个很好的理解。

作为一个具体的例子，我对本教程中的这段代码感到有点惊讶。 它有一个Java版本的Quicksort，后面跟着一个整齐的Scala实现。

这是我尝试对实现进行基准testing。 我没有做详细的分析。 但是，我的猜测是Scala版本比较慢，因为分配的对象数量是线性的（每个recursion调用一个）。 有什么方法可以使尾部优化成为可能？ 如果我是对的，Scala支持自回归调用的尾调用优化。 所以，它应该只是在帮助它。 我正在使用Scala 2.8。

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

斯卡拉版本

 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 

Answer 1

由于这里有一些误解 ，我想澄清一些观点。

• “in-place”quicksort并不是真正就地（并且quicksort 不是按照定义）。 它需要以recursion步骤的堆栈空间的forms进行额外的存储，在最好的情况下按照O （log n ）的顺序，但是在最坏的情况下是O （ n ）。

• 实现对数组进行操作的快速sorting的function变体会破坏目的。 数组永远不可改变。

• 快速sorting的“正确”function实现使用不可变列表。 它当然不是就地的，但它与程序就地版本具有相同的最坏情况渐近运行时间（ O （ n ^ 2））和空间复杂度（ O （ n ））。

  平均而言，其运行时间仍然与原位variables（ O （ n log n ））相当。 但是，它的空间复杂性仍然是O （ n ）。

---

function性quicksort实现有两个明显的缺点 。 在下面，我们来看看Haskell中的这个参考实现（我不知道Scala）： Haskell介绍 ：

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

1. 第一个缺点是select非常不灵活的枢轴元件 。 现代快速sorting实现的优势在很大程度上依赖于数据透视的明智select（比较Bentley 等人的 “devisesortingfunction” ）。 上述algorithm在这方面很差，这大大降低了平均性能。

2. 其次，这个algorithm使用列表连接 （而不是列表构造），这是一个O （ n ）操作。 这并不影响渐近的复杂性，但它是一个可衡量的因素。

第三个缺点是隐藏的：与“就地”变体不同，这个实现不断地从堆的内存中请求列表的内存单元格的内存，并且有可能在整个地方散布内存。 结果，这个algorithm的caching局部性非常差 。 我不知道现代函数式编程语言中的智能分配器是否可以缓解这个问题 – 但在现代机器上，caching未命中已经成为一个主要的性能杀手。

---

结论是什么？ 与其他人不同，我不会说快速sorting本质上是必要的，这就是为什么它在FP环境中performance不佳。 恰恰相反，我认为quicksort是一个function性algorithm的完美例子：它可以无缝地转换成一个不可变的环境，其渐近的运行时间和空间复杂度与程序实现一致，甚至程序实现都采用recursion。

但是这个algorithm在受限于一个不可变域的情况下仍然performance的更差。 其原因是该algorithm具有独特的性质，受益于许多（有时是低级的）微调，只能在数组上进行有效的微调。 一个天真的描述快速sorting错过了所有这些错综复杂（function和程序的变体）。

在阅读“devise一个sorting函数”后，我不能再考虑快速sorting一个优雅的algorithm。 有效地实施，这是一个笨重的混乱，一个工程师的工作，而不是一个艺术家（不贬低工程！这有它自己的审美）。

---

但我也想指出，这一点是特别为快速。 并不是每一种algorithm都适用于同样的低级调整。 很多algorithm和数据结构确实可以在一个不可变的环境中performance出来而没有性能损失。

不变性甚至可以通过消除昂贵的副本或跨线程同步的需要来降低性能成本。

那么，回答最初的问题，“ 不变性昂贵吗？ “ – 在快速sorting的特殊情况下，确实有一个成本是不变的结果。 但总的来说， 没有 。

Answer 2

作为函数式编程的基准，有一些错误的东西。 亮点包括：

• 您正在使用可能必须装箱/拆箱的基元。 你不是试图testing包装原始对象的开销，你试图testing不变性。
• 你已经select了一个algorithm就地操作是非常有效的（可以certificate）。 如果你想表明存在可变的实现algorithm，那么这是一个不错的select。 否则，这很可能是误导。
• 您正在使用错误的计时function。 使用System.nanoTime 。
• 基准太短，您不能确信JIT汇编不会成为测量时间的重要组成部分。
• 数组不是以有效的方式分割的。
• 数组是可变的，所以在FP中使用它们是一个奇怪的比较。

所以，这个比较是一个很好的例子，您必须详细了解您的语言（和algorithm），才能编写高性能的代码。 但是FP和非FP的比较并不是很好。 如果你想这样做，请在计算机语言基准游戏中查看Haskell vs. C ++ 。 这里的信息是惩罚通常不会超过2或3的因数，但这取决于实际情况。 （没有承诺Haskell人写出了最快的algorithm，但是至less有一些可能被尝试过！然后，Haskell再次调用C库…）

现在，假设你想要一个更合理的Quicksort基准，认识到这可能是FP与可变algorithm的最差情况之一，而忽略数据结构问题（假设我们可以有一个不可变的数组）：

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

注意对Quicksortfunction的修改，所以如果可能的话只经过一次数据，并且与内置sorting进行比较。 当我们运行它时，我们得到如下的东西：

 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 

所以，除了学习如果试图写出你自己的types是一个坏主意，我们发现如果后者被谨慎实施，那么对于不可变的快速sorting会有3倍的惩罚。 （你也可以写一个返回三个数组的三等分方法：小于，等于和大于数据的数组，这可能会稍微加快一点。）

Answer 3

我不认为Scala版本实际上是recursion的，因为你正在使用Array.concat 。

另外，只是因为这是惯用的Scala代码，这并不意味着它是最好的方式来做到这一点。

最好的办法是使用Scala的内置分类function。 这样你得到不变性保证，并知道你有一个快速的algorithm。

请参阅堆栈溢出问题如何sortingScala中的数组？ 举一个例子。

Answer 4

排列数组就像是宇宙中最重要的任务。 毫不奇怪，许多优雅的“不可变的”策略/实现在“排列数组”的微基准上失败了。 但这并不意味着不变性一般而言是昂贵的。 有许多任务中不可变的实现可以执行与可变的实现相比较，但是数组sorting通常不是其中的一个。

Answer 5

如果只是简单地将命令式algorithm和数据结构改写成function语言，那么这确实会很昂贵而且毫无用处。 为了使事情发生，你应该使用function性编程中可用的function：数据结构持久性，懒惰评估等。

Answer 6

斯卡拉不变性的代价

这里的版本几乎和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 } } 

这个版本创build了一个数组的副本，使用Java版本对其进行sorting并返回副本。 斯卡拉不强迫你在内部使用不可变的结构。

所以Scala的好处是你可以在你认为合适的时候利用可变性和不可变性。 缺点是，如果你做错了，你不会得到不变的好处。

Answer 7

不变性并不昂贵。 如果您测量一个程序必须完成的任务的一小部分，那么确定会很昂贵，并根据可变性select一个解决scheme来引导 – 比如测量快速sorting。

简而言之，使用纯function语言时不会快速sorting。

我们从另一个angular度来考虑。 我们来考虑这两个函数：

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

基准testing，你会发现使用可变数据结构的代码有更糟的性能，因为它需要复制数组，而不可变的代码不需要担心。

当您使用不可变的数据结构进行编程时，您可以构build代码以充分利用其优势。 这不仅仅是数据types，甚至是单个algorithm。 该scheme将以不同的方式进行devise 。

这就是为什么基准通常是毫无意义的。 要么你select一种或另一种风格自然的algorithm，并且风格是胜利的，或者你对整个应用程序进行基准testing，这往往是不切实际的。

Answer 8

快速sorting在现场完成时会更快，所以这是一个不太公平的比较！

话虽如此… Array.concat？ 如果没有其他的东西，那么当你尝试在函数式algorithm中使用它时，你会展示如何为命令式编程优化的集合types特别慢; 几乎任何其他select会更快！

---

另一个非常重要的考虑因素，也许是比较这两种方法时最重要的问题是：“这个扩展到多个节点/核心的程度如何？

机会是，如果你正在寻找一个不可改变的快速sorting，那么你这样做，因为你实际上想要一个并行的快速sorting。 维基百科对此有一些引用： http : //en.wikipedia.org/wiki/Quicksort#Parallelizations

scala版本可以在函数recursion之前简单地分叉，如果你有足够的内核可用，它可以很快地对包含数十亿条目的列表进行sorting。

现在，我的系统中的GPU有128个内核，只要我能运行Scala代码就可以了，而且这个系统是在当前一代的两倍之后的简单的桌面系统上。

这将如何与我想知道的单线程命令方法相叠加…

也许更重要的问题是：

“鉴于个人核心不会变得更快，同步/locking对并行化提出了真正的挑战，可变性是否昂贵？”

Answer 9

有人说，面向对象编程使用抽象来隐藏复杂性，function性编程使用不变性来消除复杂性。 在Scala的混合世界中，我们可以使用OO来隐藏命令代码，使应用程序代码不会更聪明。 事实上，集合库使用了大量的命令式代码，但这并不意味着我们不应该使用它们。 正如其他人所说，小心使用，你真的在​​这里两全其美。