java - 函数式编程 - 不变性昂贵吗？

Question

就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持，但这个问题可能会引起辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the help center为指导。




8年前关闭。




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

在编程语言中仅使用不可变数据结构是否会使实现某些算法/逻辑在实践中固有的计算成本更高？这引出了这样一个事实，即不变性是纯函数式语言的核心原则。是否有其他因素影响这一点？

让我们举一个更具体的例子。 Quicksort通常使用内存数据结构上的可变操作来教授和实现。如何以与可变版本相当的计算和存储开销的纯函数方式实现这样的事情。特别是在 Scala 中。我在下面列出了一些粗略的基准。

更多详情:

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

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

函数是一等公民。

函数没有副作用，因此对象/数据结构是 immutable .

即使现代 JVMs非常有效地创建对象和 garbage collection对于短期对象来说非常便宜，最好尽量减少对象创建，对吗？至少在并发和锁定不是问题的单线程应用程序中。由于 Scala 是一种混合范式，如果需要，可以选择使用可变对象编写命令式代码。但是，作为一个花了很多年试图重用对象和最小化分配的人。我想很好地理解甚至不允许这样做的思想流派。

作为一个特定的案例，我对 this tutorial 中的这段代码感到有些惊讶。 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;
    }
}

斯卡拉版本

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(n))。

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

功能性快速排序实现有两个明显的缺点。下面，让我们考虑一下来自 Haskell introduction 的 Haskell 中的这个引用实现(我不会 Scala ……) :

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

第一个缺点是枢轴元件的选择，非常不灵活。现代快速排序实现的优势在很大程度上依赖于枢轴的智能选择(比较 “Engineering a sort function” by Bentley et al.)。上述算法在这方面很差，这大大降低了平均性能。

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

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

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

但是当约束到不可变域时，该算法的性能仍然更差。这样做的原因是该算法具有受益于许多(有时是低级)微调的特殊属性，这些微调只能在数组上有效地执行。对快速排序的幼稚描述忽略了所有这些复杂性(在功能和程序变体中)。

阅读“设计排序函数”后，我不再认为快速排序是一种优雅的算法。有效地实现，这是一个笨重的烂摊子，工程师的作品，而不是艺术家的作品(不是贬低工程!这有它自己的审美)。

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

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

所以，要回答原来的问题，“不变性昂贵吗？ ”——在快速排序的特殊情况下，成本确实是不变性的结果。但总的来说，否 .