查找 Scala 合并算法中的瓶颈

Question

我正在学习 Scala，作为起点，我正在尝试编写 mergeSort 算法。我对它的合并部分的性能有疑问。

我知道此站点上还有其他实现，但我想知道为什么我的实现效果不佳。

这是我的代码：

@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 个元素的列表，代码变得非常慢。

Answer 1

查找瓶颈的最佳方法是使用分析器。我知道 netbeans 有一个免费的；如果您可以获得 jprofiler 或 yourkit，它们会非常好用。在这种特定情况下，我会指出 last 和 init 是 O(n)，因为 List 是一个（单）链表。

Answer 2

last 和 init 在列表上非常昂贵：O(N)。有效的操作是 head 和 tail：O(1)。如果您不能在开始时工作，请先反转列表（O(N) 但仅一次，而不是每次迭代），或者在最后反转您的输出，但您需要在列表的开头工作。

查找 Scala 合并算法中的瓶颈

Find bottleneck in Scala merge algorithm

algorithm

performance

scala