函数式编程 - 不可变性昂贵吗？[已关闭]
2022-08-31 10:05:37
问题分为两部分。首先是概念性的。接下来在Scala中更具体地研究同样的问题。
- 在编程语言中仅使用不可变的数据结构是否会使实现某些算法/逻辑在实践中固有的计算成本更高？这就引出了一个事实，即不可变性是纯函数式语言的核心原则。还有其他因素会影响这一点吗？
- 让我们举一个更具体的例子。快速排序通常使用内存中数据结构上的可变操作进行教学和实现。如何以纯函数方式实现这样的事情，其计算和存储开销与可变版本相当。特别是在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 Code 用于比较实现
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
