Объединить списки в постоянное время в scala?

В Scala существует ли встроенная функция или внешняя библиотека для объединения двух списков (или массивов, или векторов, или listbuffers и т.д.) в постоянное время? Такая операция, по-видимому, уничтожит/изменяет два первоначальных списка. Насколько мне известно, все функции, которые я вижу для конкатенации списков, выполняются в линейном времени.

Большое спасибо.

Ответ 1

Существует UnrolledBuffer, у которого метод concat принимает другой UnrolledBuffer и возвращает их конкатенацию в O(1). Это разрушительно для буфера аргументов - второй буфер будет пустым после вызова этого метода.

Ответ 2

Классика (возврат по крайней мере Hughes '84) подход в функциональных языках для решения постоянной времени добавляется через "списки различий" , где добавление к списку кодируется как составная функция.

Здесь эскиз в Haskell:

newtype DList a = DL { unDL :: [a] -> [a] }

Таким образом, DList - это функция из списков в списки. Некоторые формы введения:

-- The empty list is the identity function
empty       = DL id    

-- Singletons are the compositions of the cons function
singleton   = DL . (:)

-- Appending two lists is just composition
append xs ys = DL (unDL xs . unDL ys)

Полная реализация в Hackage и должна быть тривиальной для перевода на Scala.

Ответ 3

Я думал, что DoubleLinkedList может предлагать приложение с постоянным временем, так как вы могли бы присоединиться к концу одного списка к началу другого, не пройдя ни одного.

Однако не работают scala.collections.mutable.DoubleLinkedList или java.util.List.

Вероятно, причина в том, что это означало бы, что a.append(b) изменит как a, так и b, что было бы неожиданным.

Ответ 4

Вот простая неизменяемая структура данных, которая поддерживает постоянную конкатенацию времени. Это просто показывает, что это возможно, но не предназначено для практического использования. Реализация items для извлечения элементов имеет довольно плохое время выполнения и может быть легко улучшена путем перехода к дереву с помощью итератора.

Мне интересно, есть ли какие-то лучшие структуры данных?

sealed abstract class Tree[+T] {
  def items: List[T]
  def append[U >: T](v: U): Tree[U] = this append Leave(v)
  def append[U >: T](other: Tree[U]) = Node(this, other)
}

case class Node[+T](val left: Tree[T], val right: Tree[T]) extends Tree[T] {
  def items = left.items ++ right.items
}

case class Leave[+T](val value: T) extends Tree[T] {
  def items = List(value)
}

case object EmptyTree extends Tree[Nothing] {
  def items = Nil
}

object ConstantTimeConcatenation {
  def main(args: Array[String]) {
    val first = EmptyTree append 1 append 2 append 3
    val second = EmptyTree append 4 append 5
    val both = first append second // runs in linear time
    println(both.items)
  }
}