使用不可變列表時在內存中會發生什麼？

Question

使用不可變列表時在內存中會發生什麼？

是否在調用List.Append時執行深度複製？

什麼是用於描述F＃列表的此操作的Big-O符號？

當將一個節點添加到列表的末尾時，它仍然是O（1）嗎？

如果不是，那麼如果使用不可變列表會違反鏈表的預期性能，爲什麼使用不可變列表會有用？

考慮下面的語句：

_modules <- _modules |> List.append moduleItems 

源代碼：

type CreationViewModel() = 
    inherit ViewModelBase() 

    let mutable (_modules:Module list) = [] 

    member this.Modules 
     with get()  = _modules 
     and set(value) = _modules <- value 

    member this.Add moduleItem = 
     _modules <- moduleItem :: _modules 

    member this.AddList moduleItems = 
     _modules <- _modules |> List.append moduleItems 

Answer 1

當List.append被調用，本身沒有複製的項目，但指針是第一清單需要。

這是因爲列表結構看起來像

a::b::c::..... 

因此，當您連接兩個列表中，您從

a::b::c::d::[] and e::f::g::h::[] 

去

a::b::c::d::e::f::g::h::[] 

這需要重寫第一個列表。

因此，它是O(n)其中n是第一個列表

Answer 2

F＃列表是單鏈表的大小，就像下面的定義。

type SList<'a> = 
| Cons of 'a * SList<'a> 
| Nil 

所以，添加新元素添加到列表的開頭爲O完成（1）的時候，通過創建新的頭元件和具有它引用現有尾部元件（一個或多個）。

> Cons ("something", Nil);; 
val it : SList<string> = Cons ("something", Nil) 

這可能是用於創建一個列表如下：

> let test = Cons (1, Cons (2, Cons (3, Nil)));; 
val test : SList<int> = Cons (1,Cons (2,Cons (3,Nil))) 

但是，添加了新的元素到列表的末尾需要遍歷整個列表，找到結束，這需要O （N）時間，以便讓最後一個節點引用新的最後一個節點。

一個簡單的實現可以定義如下。即使它將列表複製兩次，它仍然是O（N），因爲成本與列表的大小呈線性關係。

let rec fold f state = function 
    | Cons(v,xs) -> fold f (f state v) xs 
    | Nil -> state 

let reverse xs = 
    fold (fun st v -> Cons (v, st)) Nil xs 

let append x xs = 
    reverse (Cons (x, (reverse xs))) 

請注意，如上定義的列表是不可變的。

在頭部添加一個新元素引用了一個永遠不會修改的現有尾部，所以尾部可以在多個列表（每個具有不同的頭元素）之間安全地共享。

將一個元素添加到列表的末尾會生成一個新列表，以便保留原始列表的不變性：將最後一個元素更改爲指向新的最後一個元素意味着更新上一個元素以指向更新後的元素，等等列表中的每個元素。

那麼，爲什麼F＃列表中沒有雙向鏈接呢？

除了歷史原因（ML只提供單鏈表），我相信一個不變的雙向鏈表實現將需要複製的要麼末添加元素時，整個列表由於需要調整每個節點的next和prev元素用於任一操作，因此總是會花費O（N）時間的。

一個不可變的單鏈表只在追加到最後時支付O（N），所以通常更高效。

由於最後一點，與不可變列表一起工作的代碼通常會避免依次追加多個元素，即O（M * N）。相反，這樣的代碼通常會反轉O（N）成本列表，爲O（1）成本向頭部（向後端）添加若干元素，然後反轉結果以恢復原始排序，從而形成整體O（N ）操作。