递归函数的优化

Question

我正在尝试为hackerrank上的函数式编程解决Messy Medians问题。

我的解决方案（如下）太慢了。它几乎使测试用例超时。

@tailrec
def calculate(steps: List[Int], states: List[List[Int]]): List[Int] = {

  steps match {
    case x::xs =>
      if(x > 0) {
        states match { //apend state
          case Nil => calculate(xs, List(x) :: states)
          case y :: _ => calculate(xs, (x :: y) :: states)
        }
      } else {
        calculate(xs, states.drop(-x-1).head :: states) //rollback state
      }
    case Nil => states
      .reverse
      .map { // calculate median
        case List(x) => x
        case xs => xs.sorted.apply(if (xs.length % 2 != 0) xs.length/2 else xs.length/2 - 1)
      }
  }
}

我该如何优化？最多可能有100000个输入状态。当我使用TreeSet而不是List用于状态时，它开始工作得更快，但是后来在有重复编号的情况下，它停止工作了。Scala中是否有排序列表？

Answer 1

我没有阅读算法（或问题），因此，我无法说出您的解决方案的正确性，但是以下是我在代码中发现的一些问题：

• 的结果与的结果xs.sorted.length相同xs.length，那只是浪费。

• List.apply是线性时间。如果要按索引随机访问，请使用IndexedSeq代替List

• List.length也是线性的。如果您要切换到IndexedSeq，这无关紧要，但是您应该在将来牢记这一点。至少xs.length一次，一次也不要多次，并将结果保存在变量中。但是即使那样，它仍然是线性的。最好只是传递长度，而不是每次都计算长度。

• 您可能还需要考虑使用快速选择算法来查找O（logN）时间的中位数。

• if(n % 2 != 0) n/2 else n/2 - 1与(n-1)/2... 是同一回事，不是因为它会影响您的表现（一旦您解决了问题.length），但是看起来很奇怪。您也不需要List(x)那里有特殊情况。只是{ xs => xs((xs.length-1)/2) }会做。