sma*_*007 93 java functional-programming scala
问题分为两部分.第一个是概念性的.接下来在Scala中更具体地看待同一个问题.
我来自命令式编程背景(C++,Java).我一直在探索函数式编程,特别是Scala.
纯函数式编程的一些主要原则:
尽管现代JVM对于创建对象非常有效,并且垃圾收集对于短期对象来说非常便宜,但是最小化对象创建可能更好吗？至少在并发和锁定不是问题的单线程应用程序中.由于Scala是一种混合范例,如果需要,可以选择使用可变对象编写命令式代码.但是,作为一个花了很多年时间试图重用对象并最小化分配的人.我希望对那些甚至不允许这样的思想流派有一个很好的理解.
作为一个特例,我对本教程中的 代码片段感到有些惊讶6.它有一个Java版本的Quicksort,后面是一个整洁的Scala实现.
这是我尝试对实现进行基准测试.我没有做过详细的剖析.但是,我的猜测是Scala版本较慢,因为分配的对象数是线性的(每个递归调用一个).尾调用优化是否有可能发挥作用？如果我是对的,Scala支持自我递归调用的尾调用优化.所以,它应该只是帮助它.我正在使用Scala 2.8.
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 <)))
}
}
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
Kon*_*lph 103
由于这里有一些误解,我想澄清一些观点.
"就地"快速排序并非真正到位(并且快速排序不是根据定义就位).它需要以递归步骤的堆栈空间形式的额外存储,在最佳情况下为O(log n),但在最坏的情况下为O(n).
实现在阵列上运行的快速排序的功能变体会破坏目的.数组永远不会是不可变的.
quicksort的"正确"功能实现使用不可变列表.它当然不是就地,但它具有相同的最坏情况渐近运行时(O(n ^ 2))和空间复杂度(O(n))作为程序就地版本.
平均而言,其运行时间仍然与就地变量(O(n log n))的运行时间相当.然而,它的空间复杂性仍然是O(n).
功能快速排序实现有两个明显的缺点.在下面,让我们从Haskell介绍中考虑Haskell中的这个参考实现(我不知道Scala ......):
qsort [] = []
qsort (x:xs) = qsort lesser ++ [x] ++ qsort greater
where lesser = (filter (< x) xs)
greater = (filter (>= x) xs)
第一个缺点是枢轴元件的选择,这是非常不灵活的.现代快速配置实施的优势在很大程度上依赖于对枢轴的明智选择(比较Bentley 等人的 "工程分类功能").在这方面,上述算法很差,这大大降低了平均性能.
其次,该算法使用列表连接(而不是列表构造),这是O(n)操作.这不会影响渐近复杂度,但它是一个可衡量的因素.
第三个缺点在某种程度上是隐藏的:与"就地"变体不同,该实现不断地从堆中请求列表的cons单元的内存,并且可能在整个地方散布内存.结果,该算法具有非常差的缓存局部性.我不知道现代函数式编程语言中的智能分配器是否能够缓解这一点 - 但在现代机器上,缓存未命中已成为主要的性能杀手.
结论是什么？与其他人不同,我不会说快速排序本质上是必要的,这就是它在FP环境中表现不佳的原因.恰恰相反,我认为quicksort是一个功能算法的完美例子:它无缝转换为不可变环境,其渐近运行时间和空间复杂度与程序实现相同,甚至其程序实现也采用递归.
但是当约束到不可变域时,该算法仍然表现更差.其原因在于该算法具有受益于许多(有时是低级)微调的特殊属性,这些微调只能在阵列上有效地执行.对快速排序的简单描述错过了所有这些错综复杂的功能(包括功能和程序变体).
阅读"工程排序功能"后,我再也不能认为quicksort是一种优雅的算法.有效地实施,这是一个笨重的混乱,工程师的工作,而不是艺术家的(不是贬低工程!这有自己的美学).
但我还要指出,这一点特别适用于快速排序.并非每种算法都适用于相同类型的低级调整.实际上可以表达许多算法和数据结构而不会在不可变环境中丢失性能.
通过消除昂贵的副本或跨线程同步的需要,不变性甚至可以降低性能成本.
那么,回答最初的问题," 不变性是不是很昂贵？" - 在快速排序的特殊情况下,成本确实是不变性的结果.但总的来说,没有.
Rex*_*err 41
作为函数式编程的基准,这有很多问题.亮点包括:
System.nanoTime.因此,这种比较是一个很好的例子,您必须详细了解您的语言(和算法)才能编写高性能代码.但这并不是FP与非FP的非常好的比较.如果你想要,请在计算机语言基准游戏中查看Haskell与C++.带回家的消息是惩罚通常不超过2或3左右,但实际上取决于.(没有承诺Haskell人员已经编写了最快的算法,但至少其中一些可能尝试了!然后,一些Haskell调用C库....)
现在,假设您确实需要一个更合理的Quicksort基准测试,认识到这可能是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
}
}
请注意对功能Quicksort的修改,以便它尽可能地遍历数据,并与内置排序进行比较.当我们运行它时,我们得到类似的东西:
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方法:那些小于,那些相等的那些,以及那些大于数据的数组.这可能会加快一点.)
Tre*_*eyE 10
我不认为Scala版本实际上是尾递归,因为你正在使用Array.concat.
另外,仅仅因为这是惯用的Scala代码,这并不意味着它是最好的方法.
最好的方法是使用Scala的内置排序功能之一.这样你就获得了不变性保证,并且知道你有一个快速的算法.
请参阅Stack Overflow问题如何在Scala中对数组进行排序？举个例子.
不变性并不昂贵.如果你测量一个程序必须完成的一小部分任务,肯定会很昂贵,并选择一个基于可变性来启动的解决方案 - 比如测量快速排序.
简而言之,在使用纯函数式语言时,不要快速排序.
让我们从另一个角度考虑这个问题.让我们考虑这两个函数:
// 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)
}
基准测试,您会发现使用可变数据结构的代码性能要差得多,因为它需要复制数组,而不可变代码不需要关注它.
使用不可变数据结构进行编程时,可以构建代码以利用其优势.它不仅仅是数据类型,甚至不是单个算法.该计划将以不同的方式设计.
这就是为什么基准测试通常没有意义的原因.您可以选择对某种风格或其他风格自然的算法,并且该风格获胜,或者您对整个应用程序进行基准测试,这通常是不切实际的.
对数组进行排序就像是宇宙中最重要的任务.毫不奇怪,许多优雅的"不可变"策略/实现在"排序阵列"微基准测试中表现不佳.然而,这并不意味着"一般"的不变性是昂贵的.有许多任务,其中不可变实现将与可变实现相比,但数组排序通常不是其中之一.
如果您只是将命令式算法和数据结构重写为函数式语言,那么它确实会非常昂贵且毫无用处.为了使事物发光,您应该使用仅在函数式编程中可用的功能:数据结构持久性,惰性评估等.
众所周知,QuickSort在就地完成时速度更快,因此这不是一个公平的比较!
说了...... Array.concat？如果没有别的,那么当你尝试在功能算法中使用它时,你会展示为命令式编程优化的集合类型是如何特别慢的; 几乎任何其他选择都会更快!
另一个非常重要的考虑因素,也许是比较两种方法时最重要的问题是:"它如何向多个节点/核心扩展？"
如果你正在寻找一个不可变的快速排序,你可能会这样做,因为你真的想要一个并行的快速排序.维基百科对此主题有一些引用:http://en.wikipedia.org/wiki/Quicksort#Parallelizations
scala版本可以在函数recurses之前简单地进行分叉,如果有足够的可用内核,它可以非常快速地对包含数十亿条目的列表进行排序.
现在,如果我可以在其上运行Scala代码,我系统中的GPU可以使用128个内核,这是在当前一代落后两年的简单桌面系统上.
我想知道如何与单线程命令式方法相媲美......
也许更重要的问题是:
"鉴于单个内核不会更快,并且同步/锁定对并行化提出了真正的挑战,可变性是否昂贵？"
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的好处是您可以根据需要利用可变性和不变性.缺点是如果你做错了,你就不会真正获得不变性的好处.