Оптимизация рекурсивной функции

Question

Я пытаюсь решить проблему 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) } сделает.