函数式编程——不可变性代价高昂吗？
问题分为两部分。第一个是概念上的。下一节将在 Scala 中更具体地讨论同样的问题。
- 在编程语言中仅使用不可变的数据结构是否会使实现某些算法/逻辑在实践中本质上计算成本更高？这引出了一个事实，即不可变性是纯函数式语言的核心原则。还有其他影响因素吗？
- 让我们举一个更具体的例子。快速排序通常使用内存中数据结构上的可变操作来教授和实现。如何以 PURE 函数方式实现这样的东西，其计算和存储开销与可变版本相当。特别是在 Scala 中。我在下面列出了一些粗略的基准。
更多详情:
我来自一个命令式编程背景(C + + ，Java) ，我一直在探索函数式编程，特别是 Scala。
纯函数式编程的一些基本原则:
- 职能是一等公民。
- 函数没有副作用，因此对象/数据结构是 永恒不变。
尽管现代的 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
最佳答案