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)

通过不变性的概念,每次创建新列表并丢弃旧列表.因此,每次必须复制100万个元素的新列表以创建新列表时,此操作不是scala中的性能杀手.

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

Answer 1

是的,这是性能杀手,但这是一个拥有不可变结构的成本(这是惊人的,安全的,并使程序更少的错误).这就是为什么你应该经常避免附加清单,如果可以的话.有许多技巧可以避免这个问题(尝试使用累加器).

例如:

代替:

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只复制第一行一次,而不是为每一个附加复制它.

PS

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