函数式编程 - 不可变性贵吗？[关闭]

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

1. 在实践中，使用只有不可变数据结构的编程语言是否会使某些算法/逻辑在计算上实质上更昂贵？这引出了不可变性是纯函数式语言的核心原则的事实。还有其他影响因素吗？

2. 让我们以一个更具体的例子来说明。快速排序通常使用对内存中的数据结构进行可变操作来进行教学和实现。如何以一种纯函数式的方式实现这样一个具有与可变版本相当的计算和存储开销的东西？特别是在Scala中。下面的一些简单的基准测试已经包含在内。

更多细节：

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

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

1. 函数是一等公民。

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

尽管现代JVM对于对象创建非常高效，短暂对象的垃圾回收成本非常低廉，但是减少对象创建可能仍然更好，对吧？至少在单线程应用程序中并发和锁定不是问题的情况下。由于Scala是一种混合范式，可以根据需要选择使用带有可变对象的命令式代码。但是，作为一个花了很多年尝试重用对象并减少分配的人，我想对不允许这种做法的思想流派有一个很好的理解。

作为一个具体的案例，我对这个教程中的代码片段感到有些惊讶。它有一个快速排序的Java版本，然后是一个看起来很不错的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