在scala中以固定时间连接列表？

| 在Scala中，是否有内置函数或外部库可用于在恒定时间内连接两个列表（或数组，向量，列表缓冲区等）？这样的操作可能会破坏/变异两个原始列表。据我所知，我看到的所有用于连接列表的功能都是线性运行的。非常感谢。

已邀请:

4 个回复

长拳

有一个具有concat方法的UnrolledBuffer接受了另一个UnrolledBuffer并在O(1)中返回它们的串联。它对参数缓冲区具有破坏性-调用此方法后，第二个缓冲区将为空。

遣莫捅炭

功能语言中解决常数时间追加的经典方法（至少回到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来说应该很简单。

孝箱捆讨

我当时以为ѭ6可以提供固定时间的追加，因为您可以将一个列表的末尾加入另一个列表的开头，而不必遍历任何一个。但是，scala.collections.mutable.DoubleLinkedList或ѭ8neither都不能这样工作。原因可能是a.append(b)会同时修改a和b，这是意外的。

坝镰补翔奋

这是一个支持恒定时间串联的简单不变数据结构。它只是表明有可能，但并不旨在实际使用。用于检索元素的“ 10”实现运行时非常糟糕，可以通过使用迭代器遍历树来轻松地进行改进。我想知道是否有更好的数据结构？

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

要回复问题请先登录或注册

在scala中以固定时间连接列表？

4 个回复

发起人

list

scala

data_structures

concatenation

问题状态

在scala中以固定时间连接列表？

与内容相关的链接

4 个回复

发起人

list

scala

data_structures

concatenation

问题状态