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 中不是性能 killer 吗，因为每次都必须复制 100 万个元素的新列表来创建新列表。

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

Answer 1

是的，这是性能 killer ，但这是拥有不可变结构的代价(这是惊人的、安全的并且使程序的错误少得多)。这就是为什么如果可以的话，你应该经常避免附加列表。有很多技巧可以避免这个问题(尝试使用 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 被实现为只复制第一行一次，而不是每次追加都复制它。

附言

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