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

Question

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

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

Answer 1

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

Answer 2

Классический (возвращаясь по крайней мере к Хьюзу '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.

Answer 3

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

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

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

Answer 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)
  }
}