scala - 递归函数的优化

Question

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

我的解决方案(如下)太慢了。它使几乎一半的测试用例超时。

@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 并将结果保存在变量中。但即便如此，它仍然是线性的。最好只是传递长度，而不是每次都计算它。

• 您可能还想考虑使用 quickselect algorithm用于在 O(logN) 时间内查找中位数。

• if(n % 2 != 0) n/2 else n/2 - 1 与 (n-1)/2 相同...并不是说它会影响你的性能(一旦你修复了 .length 的东西)，但只是看起来很奇怪。您也不需要 List(x) 的特殊情况。只需 { xs => xs((xs.length-1)/2) } 即可。