函数式编程——不变性成本高昂吗？

Question

问题分为两部分。第一个是概念性的。接下来在 Scala 中更具体地研究同一问题。

1. 在编程语言中仅使用不可变数据结构是否会使实现某些算法/逻辑在实践中本质上计算成本更高？这说明不变性是纯函数式语言的核心原则。还有其他因素影响这个吗？
2. 让我们举一个更具体的例子。 快速排序通常是使用内存数据结构上的可变操作来教授和实现的。如何以一种纯粹的函数式方式实现这样的事情，并具有与可变版本相当的计算和存储开销。特别是在 Scala 中。我在下面列出了一些粗略的基准。

更多详细信息：

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

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

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

尽管现代 JVM 在对象创建方面非常高效，并且 垃圾收集对于短命对象来说非常便宜，最小化对象创建可能仍然更好，对吗？至少在并发和锁定不是问题的单线程应用程序中。由于 Scala 是一种混合范例，因此如果需要，可以选择使用可变对象编写命令式代码。但是，作为一个花了很多年尝试重用对象和最小化分配的人。我希望对思想流派有一个很好的理解，但他们甚至不允许这样做。

作为一个具体案例，我对本教程中的这段代码片段感到有点惊讶 6 。它有一个 Java 版本的 Quicksort，后面还有一个简洁的 Scala 实现。

这是我对实现进行基准测试的尝试。我还没有做过详细的分析。但是，我的猜测是 Scala 版本较慢，因为分配的对象数量是线性的（每个递归调用一个）。尾部调用优化是否有可能发挥作用？如果我是对的，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;
    }
}

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

Answer 1

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

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

• 实现对数组进行操作的快速排序的功能变体违背了目的。数组永远不是不可变的。

• 快速排序的“正确”功能实现使用不可变列表。它当然不是就地的，但它具有相同的最坏情况渐近运行时 (O(n^2)) 和空间复杂度 (O em>(n)) 作为程序就地版本。

  平均而言，其运行时间仍然与就地变体的运行时间相当（O(n log n))。然而，它的空间复杂度仍然是 O(n)。

---

函数式快速排序实现有两个明显的缺点。下面，让我们从 Haskell 介绍<中考虑 Haskell 中的参考实现（我不知道 Scala ...） /a>:

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

1. 第一个缺点是枢轴元素的选择，非常不灵活。现代快速排序实现的优势在很大程度上依赖于枢轴的明智选择（比较 “设计排序函数”，作者：Bentley 等人）。上面的算法在这方面很差，这大大降低了平均性能。

2. 其次，该算法使用列表串联（而不是列表构造），这是一个O(n)操作。这不会影响渐近复杂度，但它是一个可测量的因素。

第三个缺点有些隐藏：与“就地”变体不同，此实现不断地从堆中请求内存来存储列表的 cons 单元，并可能将内存分散到各处。因此，该算法的缓存局部性非常差。我不知道现代函数式编程语言中的智能分配器是否可以缓解这种情况 - 但在现代机器上，缓存未命中已成为主要的性能杀手。

---

结论是什么？与其他人不同，我不会说快速排序本质上是命令式的，这就是它在 FP 环境中表现不佳的原因。恰恰相反，我认为快速排序是函数式算法的完美示例：它无缝地转换为不可变的环境，其渐近运行时间和空间复杂度与过程实现相当，甚至其过程实现也采用了递归。

但当受限于不可变域时，该算法仍然表现较差。其原因是该算法具有受益于大量（有时是低级）微调的独特属性，而这些微调只能在数组上有效执行。对快速排序的简单描述忽略了所有这些复杂性（无论是在功能上还是在程序上）。

读完“设计排序函数”后，我不再认为快速排序是一种优雅的算法。如果实现得高效，它就会显得笨重、混乱，是工程师的作品，而不是艺术家的作品（不是贬低工程的价值！这有它自己的美感）。

---

但我还想指出，这一点是快速排序所特有的。并非每个算法都适合同样类型的低级调整。许多算法和数据结构确实可以在不可变环境中表达而不会造成性能损失。

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

因此，为了回答最初的问题，“不变性成本高昂吗？”——在快速排序的特定情况下，确实存在不变性导致的成本。但总的来说，不。

Answer 2

作为函数式编程的基准，存在很多问题。亮点包括：

• 您正在使用基元，可能必须对其进行装箱/拆箱。您并不是在尝试测试包装原始对象的开销，而是在尝试测试不变性。
• 您选择了一种算法，其中就地操作异常有效（并且已证明如此）。如果你想证明存在可变实现时速度更快的算法，那么这是一个不错的选择；否则，这可能会产生误导。
• 您使用了错误的计时功能。使用 System.nanoTime。
• 该基准测试太短，您无法确信 JIT 编译不会占测量时间的重要部分。
• 数组没有以有效的方式分割。
• 数组是可变的，因此将它们与 FP 一起使用无论如何都是一个奇怪的比较。

因此，这个比较很好地说明了您必须详细了解您的语言（和算法）才能编写高性能代码。但这并不是 FP 与非 FP 的很好比较。如果您需要，请查看 Haskell 与 C++，网址为计算机语言基准游戏。最重要的信息是，惩罚通常不会超过 2 或 3 倍左右，但这实际上取决于情况。 （也不能保证 Haskell 人员已经编写了最快的算法，但至少其中一些可能尝试过！再说一次，一些 Haskell 调用 C 库......）

现在，假设您确实想要一个更合理的基准快速排序，认识到这可能是 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

因此，除了了解到尝试编写自己的排序是一个坏主意之外，我们发现，如果不可变的快速排序稍微谨慎地实现，那么它会受到大约 3 倍的惩罚。 （您还可以编写一个返回三个数组的 trisect 方法：小于、等于和大于主元的数组。这可能会稍微加快速度。）

Answer 3

我不认为 Scala 版本实际上是尾递归，因为您使用的是 Array.concat。

另外，仅仅因为这是惯用的 Scala 代码，并不意味着它是最好的方法。

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

请参阅 Stack Overflow 问题如何在 Scala 中对数组进行排序？举个例子。

Answer 4

不变性并不昂贵。如果您测量程序必须执行的一小部分任务，并选择基于启动可变性的解决方案（例如测量快速排序），那么成本肯定会很高。

简而言之，使用纯函数式语言时不会进行快速排序。

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

// 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，你会发现使用可变数据结构的代码性能要差得多，因为它需要复制数组，而不可变代码不需要关心这一点。

当您使用不可变数据结构进行编程时，您可以构建代码以利用其优势。这不仅仅是数据类型，甚至是单独的算法。该计划将以不同的方式设计。

这就是为什么基准测试通常毫无意义的原因。要么选择适合一种风格或另一种风格的算法，并且该风格获胜，要么对整个应用程序进行基准测试，这通常是不切实际的。

Answer 5

对数组进行排序是宇宙中最紧迫的任务。许多优雅的“不可变”策略/实现在“排序数组”微基准测试中表现不佳，这并不奇怪。但这并不意味着“一般来说”不变性是昂贵的。在许多任务中，不可变实现的执行效果与可变实现相当，但数组排序通常不是其中之一。

Answer 6

如果您只是将命令式算法和数据结构重写为函数式语言，那么它确实是昂贵且无用的。为了让事情变得更加精彩，您应该使用仅在函数式编程中可用的功能：数据结构持久性、惰性求值等。

Answer 7

Scala 中不变性的成本

这是一个几乎与 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 的好处是您可以根据需要利用可变性和不变性。缺点是，如果你做错了，你就无法真正获得不变性的好处。

Answer 8

众所周知，就地排序而言，快速排序速度更快，因此这并不是一个公平的比较！

话虽如此...Array.concat？
如果没有别的事，您将展示当您尝试在函数算法中使用针对命令式编程优化的集合类型时，它是如何特别慢的；几乎任何其他选择都会更快！

---

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

如果您正在寻找不可变的快速排序，那么您这样做很可能是因为您实际上需要并行快速排序。维基百科对此主题有一些引用： http://en.wikipedia.org/wiki/Quicksort#Parallelizations scala 版本可以在函数

递归之前简单地进行 fork，如果您有足够的可用核心，则可以非常快速地对包含数十亿条目的列表进行排序。

现在，如果我可以在上面运行 Scala 代码，我系统中的 GPU 有 128 个可用核心，而这是在一个简单的桌面系统上，比当前一代落后两年。

我想知道这与单线程命令式方法相比如何......

因此，也许更重要的问题是：

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

Answer 9

有人说，面向对象编程使用抽象来隐藏复杂性，而函数式编程使用不变性来消除复杂性。在 Scala 的混合世界中，我们可以使用面向对象来隐藏命令式代码，从而使应用程序代码一无所知。事实上，集合库使用了大量命令式代码，但这并不意味着我们不应该使用它们。正如其他人所说，小心使用，您确实可以两全其美。