您提出了多个问题。我尝试按逻辑顺序回答这些问题:
Stream 版本中没有堆栈溢出
你并没有真正问这个问题,但它导致了一些有趣的观察。
在您使用的 Stream 版本中 #:: merge(...)
在 - 的里面merge
功能。通常这将是一个递归调用,并且可能会导致足够大的输入数据的堆栈溢出。但在本例中并非如此。运营商#::(a,b)
实施于class ConsWrapper[A]
(有一个隐式转换)并且是同义词cons.apply[A](hd: A, tl: ⇒ Stream[A]): Cons[A]
。正如您所看到的,第二个参数是按名称调用的,这意味着它是延迟计算的。
这意味着merge
返回一个新创建的类型对象cons
最终将再次调用合并。换句话说:递归不是发生在栈上,而是发生在堆上。通常你有足够的堆。
使用堆进行递归是处理非常深的递归的好技术。但它比使用堆栈慢得多。所以你用速度换取了递归深度。这是主要原因,为什么使用Stream
太慢了。
第二个原因是,为了获取长度Stream
,Scala 必须具体化整个Stream
。但在排序过程中Stream
无论如何,它都必须实现每个元素,所以这不会造成太大伤害。
List版本没有堆栈溢出
当您将 Stream 更改为 List 时,您实际上是在使用堆栈进行递归。现在可能会发生堆栈溢出。但对于排序,通常的递归深度为log(size)
,通常是底数的对数2
。因此,要对 40 亿个输入项进行排序,您将需要大约 32 个堆栈帧。默认堆栈大小至少为 320k(在 Windows 上,其他系统具有更大的默认值),这为大量递归留下了空间,从而为大量输入数据进行排序。
更快的功能实现
这取决于 :-)
您应该使用堆栈,而不是堆进行递归。您应该根据输入数据决定您的策略:
- 对于小数据块,使用一些直接的算法对它们进行排序。算法的复杂性不会影响您,并且您可以通过将所有数据放入缓存中来获得大量性能。当然,你仍然可以手工代码分类网络对于给定的尺寸。
- 如果您有数字输入数据,则可以使用基数排序并将工作处理到处理器或 GPU 上的向量单元(更复杂的算法可以在GPU Gems).
- 对于中等大小的数据块,您可以使用分而治之的策略将数据拆分到多个线程(前提是您有多个核心!)
- 对于巨大的数据块,使用合并排序并将其拆分为适合内存的块。如果需要,您可以将这些块分布在网络上并在内存中排序。
不要使用交换并使用缓存。如果可以的话,使用可变数据结构并就地排序。我认为函数式排序和快速排序不能很好地结合在一起。为了使排序非常快,您必须使用有状态操作(例如,可变数组上的就地合并排序)。
我通常在我的所有程序上尝试这样做:尽可能使用纯函数式风格,但在可行的情况下对小部分使用有状态操作(例如,因为它具有更好的性能,或者代码只需要处理大量状态,并且在以下情况下变得更好可读)我用var
s 而不是val
s).