Scala 列表.更新
我对 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)
I am curious about List.updated. What is it's runtime? And how does it compare to just changing one element in an ArrayBuffer? In the background, how does it deal with copying all of the list? Is this an O(n) procedure? If so, is there an immutable data structure that has an updated like method without being so slow?
An example is:
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)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
updated(index, value)方法的时间和内存复杂度与index呈线性关系（而不是与列表的大小相关）。重新创建第一个index单元格。更改 ArrayBuffer 中的元素具有恒定的时间和内存复杂度。支持数组就地更新，不会发生复制。
如果您更新列表开头附近的元素，此
updated方法并不慢。对于较大的序列，Vector有不同的方式来共享列表的公共部分，并且可能会减少复制。The time and memory complexity of the
updated(index, value)method is linear in terms ofindex(not in terms of the size of the list). The firstindexcells are recreated.Changing an element in an
ArrayBufferhas constant time and memory complexity. The backing array is updated in place, no copying occurs.This
updatedmethod is not slow if you update elements near the beginning of the list. For larger sequences,Vectorhas a different way to share common parts of the list and will probably do less copying.List.updated 是一个 O(n) 操作（线性）。
它调用线性
List.splitAt操作在索引处拆分列表以获得两个列表(before, rest)，然后通过附加 < 中的元素来构建一个新列表code>before，更新后的元素，然后是rest.tail中的元素。我不确定 - 这必须进行测试，但似乎如果更新的元素位于列表的开头，则它可能非常有效，因为理论上获取
rest并附加rest.tail可以在恒定时间内完成。List.updatedis an O(n) operation (linear).It calls the linear
List.splitAtoperation to split the list at the index to get two list(before, rest), then builds a new list by appending the elements inbefore, the updated element and then the elements inrest.tail.I'm not sure - this would have to be tested, but it seems that if the updated element was at the start of the list, it may be pretty efficient as in theory getting
restand appendingrest.tailcould be done in constant time.我认为性能将是 O(n)，因为列表不存储每个元素的索引并实现为到下一个 el 的链接 -> el2-> el3` 所以只有 list.head 操作的速度是 O(1) 一样快。
您应该将 IndexedSeq 与最常见的实现 Vector 一起用于此目的。
虽然它不复制任何数据，所以实际上只有 1 个值在内存中更新。
一般来说，所有 scala 不可变集合不会在修改或创建更新的新实例时复制所有数据。这是与 Java 集合的主要区别。
I suppose performance would be O(n) since list doesn't store index to each element and implemented as links to next
el-> el2 -> el3` so only list.head operation are O(1) as fast.You should use IndexedSeq for that purpose with most common implmentation Vector.
Although it doesn't copy any data so only 1 value are actually updated in memory.
In general all scala immutable collections dosn't copy all data on modification or creation of updated new instance. It is key difference with Java collections.