Scala List.updated

Question

我很好奇List.updated.什么是运行时？它与仅仅更改ArrayBuffer中的一个元素相比如何？在后台,它如何处理复制所有列表？这是一个O(n)程序吗？如果是这样,是否存在一个不可变的数据结构,它具有更新的类似方法,而不是那么慢？

一个例子是:

val list = List(1,2,3)
val list2 = list.updated(2, 5) --> # list2 = (1,5,3)
var abuf = ArrayBuffer(1,2,3)
abuf(2) = 5 --> # abuf = (1,5,3)

Answer 1

1. 该方法的时间和存储器复杂性updated(index, value)是线性的index(不是根据列表的大小).index重建第一个单元格.

2. 更改一个元素ArrayBuffer具有恒定的时间和内存复杂性.后备阵列已就地更新,不会发生复制.

3. updated如果更新列表开头附近的元素,则此方法不会很慢.对于较大的序列,Vector有一种不同的方式来共享列表的公共部分,并且可能会减少复制.

Answer 2

List.updated 是O(n)运算(线性).

它调用线性List.splitAt操作在索引处拆分列表以获得两个列表(before, rest),然后通过附加元素before,更新元素然后添加元素来构建新列表rest.tail.

我不确定 - 这将不得不进行测试,但似乎如果更新的元素位于列表的开头,它可能非常有效,因为在理论上获取rest和追加rest.tail可以在恒定时间内完成.