F# 程式設計/可變集合

F# : 可變集合

.NET BCL 自帶一套可變集合，它們位於 System.Collections.Generic 名稱空間中。這些內建集合與 F# 中的不可變對應物非常相似。

`List<'T>` 類

List<'T> 類表示一個強型別物件列表，可以透過索引訪問。從概念上講，這使得 List<'T> 類類似於陣列。但是，與陣列不同，List 可以調整大小，不需要在宣告時指定其大小。

.NET 列表使用 new 關鍵字建立，並呼叫列表的建構函式，如下所示

> open System.Collections.Generic;;
> let myList = new List<string>();;

val myList : List<string>

> myList.Add("hello");;
val it : unit = ()
> myList.Add("world");;
val it : unit = ()
> myList.[0];;
val it : string = "hello"
> myList |> Seq.iteri (fun index item -> printfn "%i: %s" index myList.[index]);;
0: hello
1: world

很容易看出 .NET 列表是可變的，因為它們的 Add 方法返回 unit，而不是返回另一個列表。

底層實現

在幕後，List<'T> 類只是一個用於陣列的精美包裝器。當構造 List<'T> 時，它會在記憶體中建立一個包含 4 個元素的陣列。新增前 4 個專案是 O(1) 操作。但是，一旦需要新增第 5 個元素，列表就會將內部陣列的大小加倍，這意味著它必須重新分配新記憶體並複製現有列表中的元素；這是一個 O(n) 操作，其中 n 是列表中的專案數。

List<'T>.Count 屬性返回當前儲存在集合中的專案數，List<'T>.Capacity 集合返回底層陣列的大小。以下程式碼示例演示瞭如何調整底層陣列的大小

open System
open System.Collections.Generic

let items = new List<string>()

let printList (l : List<_>) =
    printfn "l.Count: %i, l.Capacity: %i" l.Count l.Capacity
    printfn "Items:"
    l |> Seq.iteri (fun index item ->
        printfn "    l.[%i]: %s" index l.[index])
    printfn "-----------"

let main() =
    printList items
    
    items.Add("monkey")
    printList items
    
    items.Add("kitty")
    items.Add("bunny")
    printList items
    
    items.Add("doggy")
    items.Add("octopussy")
    items.Add("ducky")
    printList items
    
    printfn "Removing entry for \"doggy\"\n--------\n"
    items.Remove("doggy") |> ignore
    printList items
    
    printfn "Removing item at index 3\n--------\n"
    items.RemoveAt(3)
    printList items
    
    Console.ReadKey(true) |> ignore
            
main()

l.Count: 0, l.Capacity: 0
Items:
-----------
l.Count: 1, l.Capacity: 4
Items:
    l.[0]: monkey
-----------
l.Count: 3, l.Capacity: 4
Items:
    l.[0]: monkey
    l.[1]: kitty
    l.[2]: bunny
-----------
l.Count: 6, l.Capacity: 8
Items:
    l.[0]: monkey
    l.[1]: kitty
    l.[2]: bunny
    l.[3]: doggy
    l.[4]: octopussy
    l.[5]: ducky
-----------
Removing entry for "doggy"
--------

l.Count: 5, l.Capacity: 8
Items:
    l.[0]: monkey
    l.[1]: kitty
    l.[2]: bunny
    l.[3]: octopussy
    l.[4]: ducky
-----------
Removing item at index 3
--------

l.Count: 4, l.Capacity: 8
Items:
    l.[0]: monkey
    l.[1]: kitty
    l.[2]: bunny
    l.[3]: ducky
-----------

如果事先知道列表的最大大小，可以透過呼叫 List<'T>(size : int) 建構函式來避免效能下降。以下示例演示瞭如何在不調整內部陣列大小的情況下將 1000 個專案新增到列表中

> let myList = new List<int>(1000);;

val myList : List<int>

> myList.Count, myList.Capacity;;
val it : int * int = (0, 1000)
> seq { 1 .. 1000 } |> Seq.iter (fun x -> myList.Add(x));;
val it : unit = ()
> myList.Count, myList.Capacity;;
val it : int * int = (1000, 1000)

`LinkedList<'T>` 類

LinkedList<'T> 表示一個雙向連結的節點序列，它允許高效的 O(1) 插入和刪除，支援向前和向後遍歷，但它的實現阻止了高效的隨機訪問。連結列表具有一些有價值的方法

(* Prepends an item to the LinkedList *)
val AddFirst : 'T -> LinkedListNode<'T>

(* Appends an items to the LinkedList *)
val AddLast : 'T -> LinkedListNode<'T>

(* Adds an item before a LinkedListNode *)
val AddBefore : LinkedListNode<'T> -> 'T -> LinkedListNode<'T>

(* Adds an item after a LinkedListNode *)
val AddAfter : LinkedListNode<'T> -> 'T -> LinkedListNode<'T>

請注意，這些方法返回一個 LinkedListNode<'T>，而不是一個新的 LinkedList<'T>。新增節點實際上會更改 LinkedList 物件

> open System.Collections.Generic;;
> let items = new LinkedList<string>();;

val items : LinkedList<string>

> items.AddLast("AddLast1");;
val it : LinkedListNode<string>
= System.Collections.Generic.LinkedListNode`1[System.String]
    {List = seq ["AddLast1"];
     Next = null;
     Previous = null;
     Value = "AddLast1";}
> items.AddLast("AddLast2");;
val it : LinkedListNode<string>
= System.Collections.Generic.LinkedListNode`1[System.String]
    {List = seq ["AddLast1"; "AddLast2"];
     Next = null;
     Previous = System.Collections.Generic.LinkedListNode`1[System.String];
     Value = "AddLast2";}
> let firstItem = items.AddFirst("AddFirst1");;

val firstItem : LinkedListNode<string>

> let addAfter = items.AddAfter(firstItem, "addAfter");;

val addAfter : LinkedListNode<string>

> let addBefore = items.AddBefore(addAfter, "addBefore");;

val addBefore : LinkedListNode<string>

> items |> Seq.iter (fun x -> printfn "%s" x);;
AddFirst1
addBefore
addAfter
AddLast1
AddLast2

Stack<'T> 和 Queue<'T> 類是連結列表的特例（可以認為它們是連結列表，但對可以在哪裡新增和刪除專案有限制）。

`Stack<'T>` 類

Stack<'T> 僅允許程式設計師在列表的開頭新增/推入和刪除/彈出專案，這使其成為一個後進先出 (LIFO) 資料結構。Stack<'T> 類可以被認為是 F# 列表的可變版本。

> stack.Push("First");; (* Adds item to front of the list *)
val it : unit = ()
> stack.Push("Second");;
val it : unit = ()
> stack.Push("Third");;
val it : unit = ()
> stack.Pop();; (* Returns and removes item from front of the list *)
val it : string = "Third"
> stack.Pop();;
val it : string = "Second"
> stack.Pop();;
val it : string = "First"

可以用這種資料結構表示一疊硬幣。如果我們將硬幣一層疊一層地疊起來，堆疊中的第一枚硬幣在堆疊的底部，堆疊中的最後一枚硬幣出現在頂部。我們從上到下移除硬幣，所以最後新增到堆疊的硬幣是最先移除的硬幣。

`Queue<'T>` 類

Queue<'T> 僅允許程式設計師將專案追加/入隊到列表的末尾，並從列表的開頭刪除/出隊，這使其成為一個先進先出 (FIFO) 資料結構。

> let queue = new Queue<string>();;

val queue : Queue<string>

> queue.Enqueue("First");; (* Adds item to the rear of the list *)
val it : unit = ()
> queue.Enqueue("Second");;
val it : unit = ()
> queue.Enqueue("Third");;
val it : unit = ()
> queue.Dequeue();; (* Returns and removes item from front of the queue *)
val it : string = "First"
> queue.Dequeue();;
val it : string = "Second"
> queue.Dequeue();;
val it : string = "Third"

一隊人可以用佇列來表示：人們把自己新增到佇列的末尾，並從佇列的開頭移除。第一個站在佇列中的人是第一個被服務的人。

`HashSet<'T>` 和 `Dictionary<'TKey, 'TValue>` 類

HashSet<'T> 和 Dictionary<'TKey, 'TValue> 類是 F# 集合和對映資料結構的可變模擬，幷包含許多相同的功能。

使用 HashSet<'T>

open System
open System.Collections.Generic

let nums_1to10 = new HashSet<int>()
let nums_5to15 = new HashSet<int>()

let main() =
    let printCollection msg targetSet =
        printf "%s: " msg
        targetSet |> Seq.sort |> Seq.iter(fun x -> printf "%O " x)
        printfn ""
        
    let addNums min max (targetSet : ICollection<_>) =
        seq { min .. max } |> Seq.iter(fun x -> targetSet.Add(x))
        
    addNums 1 10 nums_1to10
    addNums 5 15 nums_5to15
    
    printCollection "nums_1to10 (before)" nums_1to10
    printCollection "nums_5to15 (before)" nums_5to15
    
    nums_1to10.IntersectWith(nums_5to15) (* mutates nums_1to10 *)
    printCollection "nums_1to10 (after)" nums_1to10
    printCollection "nums_5to15 (after)" nums_5to15
    
    Console.ReadKey(true) |> ignore
            
main()

nums_1to10 (before): 1 2 3 4 5 6 7 8 9 10
nums_5to15 (before): 5 6 7 8 9 10 11 12 13 14 15
nums_1to10 (after): 5 6 7 8 9 10
nums_5to15 (after): 5 6 7 8 9 10 11 12 13 14 15

使用 Dictionary<'TKey, 'TValue>

> open System.Collections.Generic;;
> let dict = new Dictionary<string, string>();;

val dict : Dictionary<string,string>

> dict.Add("Garfield", "Jim Davis");;
val it : unit = ()
> dict.Add("Farside", "Gary Larson");;
val it : unit = ()
> dict.Add("Calvin and Hobbes", "Bill Watterson");;
val it : unit = ()
> dict.Add("Peanuts", "Charles Schultz");;
val it : unit = ()
> dict.["Farside"];; (* Use the '.[key]' operator to retrieve items *)
val it : string = "Gary Larson"

.NET BCL 與 F# 集合之間的差異

.NET BCL 中內建的集合與其 F# 模擬之間的主要區別當然在於可變性。BCL 集合的可變性會極大地影響其實現和時間複雜度

.NET 資料結構	插入	刪除	查詢	F# 資料結構	插入	刪除	查詢
`列表`	O(1) / O(n)*	O(n)	O(1)（按索引）/ O(n)（線性）	沒有內建的等效項
`連結列表`	O(1)	O(1)	O(n)	沒有內建的等效項
`堆疊`	O(1)	O(1)	O(n)	`列表`	O(1)	n/a	O(n)
`佇列`	O(1)	O(1)	O(n)	沒有內建的等效項
`雜湊集`	O(1) / O(n)*	O(1)	O(1)	`集合`	O(log n)	O(log n)	O(log n)
`字典`	O(1) / O(n)*	O(1)	O(1)	`對映`	O(log n)	O(log n)	O(log n)

* 這些類構建在內部陣列之上。當新增專案時，它們可能會遇到效能下降，因為內部陣列會定期調整大小。

注意：上面的大 O 符號指的是插入/刪除/檢索操作相對於資料結構中專案數量的時間複雜度，而不是相對於其他資料結構評估操作所需時間的相對數量。例如，按索引訪問陣列與按鍵訪問字典具有相同的時間複雜度，O(1)，但操作不一定在相同的時間內發生。

前一頁：陣列

索引

下一頁：輸入和輸出

List<'T> 類

底層實現

LinkedList<'T> 類

Stack<'T> 類

Queue<'T> 類

HashSet<'T> 和 Dictionary<'TKey, 'TValue> 類