Scala 不可变列表内部实现

Question

假设我有一个包含 1 到 100 万个元素的巨大列表。

val initialList = List(1,2,3,.....1 million)
and 
val myList = List(1,2,3)

现在，当我在 myList 上应用 foldLeft 等操作时，将 initialList 作为起始值，例如

val output = myList.foldLeft(initialList)(_ :+ _)

// result ==>> List(1,2,3,.....1 million, 1 , 2 , 3)

现在我的问题来了，两个列表都是不可变的，生成的中间列表是

List(1,2,3,.....1 million, 1)
List(1,2,3,.....1 million, 1 , 2)
List(1,2,3,.....1 million, 1 , 2 , 3)

根据不变性的概念，每次都会创建一个新列表并丢弃旧列表。所以这个操作在 scala 中不是性能杀手，因为每次必须复制一个包含 100 万个元素的新列表来创建一个新列表。

如果我错了请纠正我，因为我试图理解不可变列表的内部实现。提前致谢。

Answer 1

是的，这是性能杀手，但这是拥有不可变结构的代价（这是惊人的、安全的并且使程序的错误更少）。这就是为什么你应该尽可能避免附加列表。有很多技巧可以避免这个问题（尝试使用 accumulators）。

例如：

而不是：

val initialList = List(1,2,3,.....1 million)
val myList = List(1,2,3,...,100)
val output = myList.foldLeft(initialList)(_ :+ _)

你可以这样写：

val initialList = List(1,2,3,.....1 million)
val myList = List(1,2,3,...,100)
val output = List(initialList,myList).flatten

Flatten 被实施为只复制第一行一次，而不是每次附加都复制它。

P.S.

至少将元素添加到列表前面的速度很快（O(1)），因为可以共享旧列表。让我们看看这个例子：您可以看到内存共享如何用于不可变链表。计算机只保留一份 (b,c,d) 结尾。但是如果你想将 bar 附加到 baz 的末尾，你不能修改 baz，因为你会破坏 foo、bar 和 raz！这就是为什么你必须复制第一个列表。

Answer 2

附加到 List 不是一个好主意，因为 List 的附加成本是线性的。所以，如果你能

要么添加到列表中（列表有固定的时间添加）
或选择另一个可高效追加的集合。那将是 Queue

有关大多数 Scala 集合上每个操作的性能特征列表，请参阅：

https://docs.scala-lang.org/overviews/collections/performance-characteristics.html

请注意，根据您的要求，您还可以创建自己的 更智能 集合，例如

Scala 不可变列表内部实现

Scala immutable list internal implementation

functional-programming

scala

immutability

而不是：

你可以这样写：