我正在学习 Scala,作为起点,我尝试编写一个归并排序算法。我对其合并部分的性能有问题。
我知道该网站上还有其他实现,但我想知道为什么我的实现效果不佳。
这是我的代码:
@tailrec
def merge(l1:List[Int], l2:List[Int], acc:List[Int]): List[Int] = {
if(l1.isEmpty || l2.isEmpty) l1 ++ l2 ++ acc
else if(l1.last> l2.last) merge(l1.init, l2, l1.last :: acc)
else merge(l1, l2.init, l2.last :: acc)
}
val a1 = List(1,4,65,52151)
val a2 = List(2,52,124,5251,124125125)
println(merge(a1, a2, List()))
你怎么能看到合并函数是尾递归的,并且(如果我没记错的话)我正在使用的列表方法应该花费恒定的时间。
对于包含 100000 个元素的列表,代码变得非常慢。
最佳答案
last
和 init
在 List 上的开销非常大:O(N)。高效的操作是 head
和 tail
:O(1)。如果您无法在开始时工作,请预先反转列表(O(N),但仅一次,而不是在每次迭代时),或者在最后反转输出,但您需要在列表的开头工作。
关于performance - 寻找 Scala 合并算法的瓶颈,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28115440/