Scala List.updated

Question

私はList.updatedについて興味があります。ランタイムは何ですか？そして、それはArrayBuffer内の1つの要素を変更することと比べてどうですか？バックグラウンドでは、リスト全体をどのようにコピーするのですか？これは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

Iがリストの各要素にインデックスを格納し、次elへのリンクとして実装されないので、性能はO（N）であろうと仮定 - > EL2 - > el3`これだけlist.head操作はO（1）と高速です。 そのためには、ほとんどの一般的な実装ベクターでIndexedSeqを使用する必要があります。

実際には1つの値しかメモリ内で更新されないため、データはコピーされませんが、 一般に、すべてのスケーラ不変なコレクションは、更新された新しいインスタンスの変更または作成に関するすべてのデータをコピーしません。 Javaコレクションとの主な違いです。

Answer 3

List.updatedは、O（n）演算（線形）です。

それは2つのリスト(before, rest)を取得するには、インデックスのリストを分割するために、線形List.splitAt操作を呼び出し、その後、更新要素とrest.tailで、その後の要素をbefore内の要素を付加することによって、新しいリストを作成します。

これはテストする必要がありますが、更新された要素がリストの先頭にある場合、理論的にはrestを取得し、rest.tailを追加するとかなり効率的になる可能性があります一定時間。