Какова временная и пространственная сложность экстрактора головы / хвоста Scala?

Question

Какова временная и пространственная сложность для этого:

def isPalindrome[A](x: Seq[A]): Boolean = x match {
  case h +: middle :+ t => h == t && isPalindrome(middle)
  case _ => true
}

Зависит ли это от реализации Seq? поскольку IndexedSeq должен иметь O(1) хвост против O(n) за LinearSeqs? Является ли сложность пространства O(n) из-за рекурсивного стека вызовов или Scala выполняет автоматическую оптимизацию вызовов?

import scala.annotation.tailrec

@tailrec def isPalindrome[A](x: Seq[A]): Boolean = x match {
  case h +: middle :+ t => h == t && isPalindrome(middle)
  case _ => true
}

Answer 1

Зависит ли это от реализации Seq? Так как у IndexedSeq должен быть хвост O(1) против O(n) для LinearSeqs?

Я бы обычно так предположил, однако экстрактор на самом деле O(n), Экстрактор для любого Seq является scala.collection.:+ у которого есть O(n) для списка до последнего и O(n) за последние. Код для этих двух:

  def init: Repr = {
    if (isEmpty) throw new UnsupportedOperationException("empty.init")
    var lst = head
    var follow = false
    val b = newBuilder
    b.sizeHint(this, -1)
    for (x <- this) { // O(n)
      if (follow) b += lst
      else follow = true
      lst = x
    }
    b.result
  }

  def last: A = {
    var lst = head
    for (x <- this) // O(n)
      lst = x
    lst
  }

Является ли сложность пространства O(n) из-за рекурсивного стека вызовов или Scala выполняет автоматическую оптимизацию вызовов?

Я вижу, что код имеет эту оптимизацию. Это имеет смысл, потому что t && isPalindrome(middle) позволяет Scala закрыть текущий стек вызовов, передать t к следующему стеку, чтобы быть &&с помощью, и, следовательно, это возможность оптимизации хвостовой рекурсии.

Постоянное время соответствия

С помощью Vector мы можем достичь O(1) время:

object ends {
  def unapply[T](t: Vector[T]): Option[(T, Vector[T], T)] =
    if (t.length < 2) None
    else Some((t.head, t.drop(1).dropRight(1), t.last))
}

def isPalindrome[A](x: Vector[A]): Boolean = x match {
  case ends(i, middle, l) => i == l && isPalindrome(middle)
  case _ => true
}