scala - Scala 中的结构共享列表

Question

我有一个关于 Scala 中列表的结构共享的问题。我在网上看过这句话

List implements structural sharing of the tail list. This means that many operations are either zero- or constant-memory cost.

但我真的不明白如何减少列表操作的时间和内存成本。例如

val mainList = List(3, 2, 1)
val with4 =    4 :: mainList // O(1)

如果我们想用 4 时间创建另一个列表，则只需 O(1)，并且内存成本为 1，但是对于列表的操作会有什么不同？我的意思是使用 length() 或 reverse() ...它仍然是 O(n) 正常吗？任何人都可以解释一下我吗？如果可以的话，也许一个例子会非常有帮助。谢谢!

Answer 1

由于结构共享，列表上运行时间为常数 (O(1)) 的操作包括前置 (::)、头和尾。大多数其他操作都是线性时间 (O(n))。

你的例子是正确的 4::myList 是常数时间，myList.head 和 mylist.tail 也是如此，其他的东西比如 length 和 reverse 是线性时间。

这就是为什么 List 在大多数情况下不是一个特别好的集合，除非您只使用这些操作，因为其他一切都是 O(n)。

您可以引用http://docs.scala-lang.org/overviews/collections/performance-characteristics.html了解不同集合的运行时特征的概述。