跳轉到內容

F# 程式設計/陣列

Add links
來自華夏公益教科書，自由的教科書
前一節：控制流 索引 下一節：可變集合
F#：陣列

陣列是一種普遍的、熟悉的資料結構，用於表示一組相關的、有序的值。與 F# 資料結構不同，陣列是可變的，這意味著陣列建立後，陣列中的值可以改變。

建立陣列

[編輯 | 編輯原始碼]

從概念上講，陣列類似於列表。自然地，陣列可以使用與列表相同的方式建立。

陣列字面量

[編輯 | 編輯原始碼]
> [| 1; 2; 3; 4; 5 |];;
val it : int array = [|1; 2; 3; 4; 5|]

陣列推導式

[編輯 | 編輯原始碼]

F# 使用與 列表推導式 相同的風格和格式，透過範圍和生成器支援陣列推導式。

> [| 1 .. 10 |];;
val it : int array = [|1; 2; 3; 4; 5; 6; 7; 8; 9; 10|]

> [| 1 .. 3 .. 10 |];;
val it : int array = [|1; 4; 7; 10|]

> [| for a in 1 .. 5 do
    yield (a, a*a, a*a*a) |];;
val it : (int * int * int) array
= [|(1, 1, 1); (2, 4, 8); (3, 9, 27); (4, 16, 64); (5, 25, 125)|]

System.Array 方法

[編輯 | 編輯原始碼]

System.Array 模組中有一些方法可以用來建立陣列。

val zeroCreate : int arraySize -> 'T []

建立一個包含 arraySize 個元素的陣列。陣列中的每個元素都包含特定資料型別的預設值（數字為 0，布林值為 false，引用型別為 null）。
> let (x : int array) = Array.zeroCreate 5;;
val x : int array

> x;;
val it : int array = [|0; 0; 0; 0; 0|]

val create : int -> 'T value -> 'T []

建立一個包含 arraySize 個元素的陣列。使用 value 初始化陣列中的每個元素。
> Array.create 5 "Juliet";;
val it : string [] = [|"Juliet"; "Juliet"; "Juliet"; "Juliet"; "Juliet"|]

val init : int arraySize -> (int index -> 'T) initializer -> 'T []

建立一個包含 arraySize 個元素的陣列。使用 initializer 函式初始化陣列中的每個元素。
> Array.init 5 (fun index -> sprintf "index: %i" index);;
val it : string []
= [|"index: 0"; "index: 1"; "index: 2"; "index: 3"; "index: 4"|]

使用陣列

[編輯 | 編輯原始碼]

陣列中的元素透過它們的索引（即陣列中的位置）訪問。陣列索引始終從 0 開始，到 array.length - 1 結束。例如，讓我們來看下面的陣列。

let names = [| "Juliet"; "Monique"; "Rachelle"; "Tara"; "Sophia" |]
(* Indexes:        0         1           2         3        4 *)

此列表包含 5 個專案。第一個索引是 0，最後一個索引是 4。

我們可以使用 .[index] 運算子（也稱為索引運算子）訪問陣列中的專案。以下是 fsi 中相同的陣列。

> let names = [| "Juliet"; "Monique"; "Rachelle"; "Tara"; "Sophia" |];;

val names : string array

> names.[2];;
val it : string = "Rachelle"

> names.[0];;
val it : string = "Juliet"

陣列例項具有一個 Length 屬性，該屬性返回陣列中的元素數量。

> names.Length;;
val it : int = 5

> for i = 0 to names.Length - 1 do
    printfn "%s" (names.[i]);;
Juliet
Monique
Rachelle
Tara
Sophia

陣列是可變的資料結構，這意味著我們可以在程式中的任何時刻為陣列中的元素分配新的值。

> names;;
val it : string array = [|"Juliet"; "Monique"; "Rachelle"; "Tara"; "Sophia"|]

> names.[4] <- "Kristen";;
val it : unit = ()

> names;;
val it : string array = [|"Juliet"; "Monique"; "Rachelle"; "Tara"; "Kristen"|]

如果您嘗試訪問陣列範圍之外的元素，您將得到一個異常。

> names.[-1];;
System.IndexOutOfRangeException: Index was outside the bounds of the array.
   at <StartupCode$FSI_0029>.$FSI_0029._main()
stopped due to error

> names.[5];;
System.IndexOutOfRangeException: Index was outside the bounds of the array.
   at <StartupCode$FSI_0030>.$FSI_0030._main()
stopped due to error

陣列切片

[編輯 | 編輯原始碼]

F# 支援一些有用的運算子，允許程式設計師使用 .[start..finish] 運算子返回陣列的“切片”或子陣列，其中 start 和 finish 引數之一可以省略。

> let names = [|"0: Juliet"; "1: Monique"; "2: Rachelle"; "3: Tara"; "4: Sophia"|];;

val names : string array

> names.[1..3];; (* Grabs items between index 1 and 3 *)
val it : string [] = [|"1: Monique"; "2: Rachelle"; "3: Tara"|]

> names.[2..];; (* Grabs items between index 2 and last element *)
val it : string [] = [|"2: Rachelle"; "3: Tara"; "4: Sophia"|]

> names.[..3];; (* Grabs items between first element and index 3 *)
val it : string [] = [|"0: Juliet"; "1: Monique"; "2: Rachelle"; "3: Tara"|]

請注意，陣列切片會生成一個新陣列，而不是更改現有陣列。這需要分配新的記憶體並將元素從源陣列複製到目標陣列。如果效能是重中之重，一般來說，使用一些索引調整檢視陣列的各個部分更為有效。

多維陣列

[編輯 | 編輯原始碼]

多維陣列實際上是陣列的陣列。從概念上講，使用這些型別的陣列與使用上面所示的單維陣列沒有太大區別。多維陣列有兩種形式：矩形陣列和鋸齒陣列。

矩形陣列

[編輯 | 編輯原始碼]

矩形陣列（也稱為網格或矩陣）是陣列的陣列，其中所有內部陣列都具有相同的長度。以下是在 fsi 中的一個簡單的 2x3 矩形陣列。

> Array2D.zeroCreate<int> 2 3;;
val it : int [,] = [|[|0; 0; 0|]; [|0; 0; 0|]|]

此陣列有 2 行，每行有 3 列。要訪問此陣列中的元素，您可以使用 .[row,col] 運算子。

> let grid = Array2D.init<string> 3 3 (fun row col -> sprintf "row: %i, col: %i" row col);;

val grid : string [,]

> grid;;
val it : string [,]
= [|[|"row: 0, col: 0"; "row: 0, col: 1"; "row: 0, col: 2"|];
    [|"row: 1, col: 0"; "row: 1, col: 1"; "row: 1, col: 2"|];
    [|"row: 2, col: 0"; "row: 2, col: 1"; "row: 2, col: 2"|]|]

> grid.[0, 1];;
val it : string = "row: 0, col: 1"

> grid.[1, 2];;
val it : string = "row: 1, col: 2"

以下是一個簡單的程式，演示如何使用和遍歷多維陣列。

open System

let printGrid grid =
    let maxY = (Array2D.length1 grid) - 1
    let maxX = (Array2D.length2 grid) - 1
    
    for row in 0 .. maxY do
        for col in 0 .. maxX do
            if grid.[row, col] = true then Console.Write("* ")
            else Console.Write("_ ")
        Console.WriteLine()

let toggleGrid (grid : bool[,]) =
    Console.WriteLine()
    Console.WriteLine("Toggle grid:")
    
    let row =
        Console.Write("Row: ")
        Console.ReadLine() |> int
        
    let col =
        Console.Write("Col: ")
        Console.ReadLine() |> int
    
    grid.[row, col] <- (not grid.[row, col])

let main() =
    Console.WriteLine("Create a grid:")
    let rows =
        Console.Write("Rows: ")
        Console.ReadLine() |> int
        
    let cols =
        Console.Write("Cols: ")
        Console.ReadLine() |> int
        
    let grid = Array2D.zeroCreate<bool> rows cols
    printGrid grid
    
    let mutable go = true
    while go do
        toggleGrid grid
        printGrid grid
        Console.Write("Keep playing (y/n)? ")
        go <- Console.ReadLine() = "y"
    
    Console.WriteLine("Thanks for playing")
            
main()

此程式輸出以下內容。

Create a grid:
Rows: 2
Cols: 3
_ _ _
_ _ _

Toggle grid:
Row: 0
Col: 1
_ * _
_ _ _
Keep playing (y/n)? y

Toggle grid:
Row: 1
Col: 1
_ * _
_ * _
Keep playing (y/n)? y

Toggle grid:
Row: 1
Col: 2
_ * _
_ * *
Keep playing (y/n)? n

Thanks for playing

除了 Array2D 模組外，F# 還擁有 Array3D 模組，以支援 3 維陣列。

注意 可以使用 System.Array.CreateInstance 方法建立超過 3 維的陣列，但通常建議避免建立具有大量元素或維度的陣列，因為這很難管理，而且還會很快消耗機器上的所有可用記憶體。

鋸齒陣列

[編輯 | 編輯原始碼]

鋸齒陣列是陣列的陣列，但陣列中的每一行不需要都具有相同數量的元素。

> [| for a in 1 .. 5 do yield [| 1 .. a |] |];;
val it : int array array
= [|[|1|];
    [|1; 2|];
    [|1; 2; 3|];
    [|1; 2; 3; 4|];
    [|1; 2; 3; 4; 5|]|]

您可以使用 .[index] 運算子訪問陣列中的專案。由於每個元素都包含另一個數組，因此經常會看到類似於 .[row].[col] 的程式碼。

> let jagged = [| for a in 1 .. 5 do yield [| 1 .. a |] |]
for arr in jagged do
    for col in arr do
        printf "%i " col
    printfn "";;

val jagged : int array array

1 
1 2 
1 2 3 
1 2 3 4 
1 2 3 4 5

> jagged.[2].[2];;
val it : int = 3

> jagged.[4].[0];;
val it : int = 1
注意： 請注意，矩形陣列的資料型別是 'a[,]，但鋸齒陣列的資料型別是 'a array array。這是因為矩形陣列以“扁平”方式儲存資料，而鋸齒陣列實際上是指向陣列的指標的陣列。由於這兩種型別的陣列在記憶體中儲存方式不同，因此 F# 將 'a[,] 和 'a array array 視為兩種不同的、不可互換的資料型別。因此，矩形陣列和鋸齒陣列在元素訪問方面具有略微不同的語法。
矩形陣列的儲存方式略微更有效，通常比鋸齒陣列效能更高，儘管在大多數應用程式中可能沒有明顯的差異。但是，在 基準測試 中值得注意的是兩者之間的效能差異。

使用 Array 模組

[編輯 | 編輯原始碼]

有兩個陣列模組，System.Array 和 Microsoft.FSharp.Collections.Array，分別由 .NET BCL 設計人員和 F# 的建立者開發。F# Array 模組中的許多方法和函式類似於 List 模組中的方法和函式。

val append : 'T[] first -> 'T[] second -> 'T[]

返回一個新陣列，該陣列的元素由第一個陣列後跟第二個陣列組成。

val choose : ('T item -> 'U option) -> 'T[] input -> 'U[]

過濾和對映陣列，返回一個新陣列，該陣列包含所有返回 Some 的元素。

val copy : 'T[] input -> 'T[]

返回輸入陣列的副本。

val fill : 'T[] input -> int start -> int end -> 'T value -> unit

將 value 分配給開始和結束索引之間的所有元素。

val filter : ('T -> bool) -> 'T[] -> 'T[]

返回一個新陣列，該陣列包含從輸入陣列中過濾出來的專案。

val fold : ('State -> 'T -> 'State) -> 'State -> 'T[] input -> 'State

從左到右累積陣列。

val foldBack : ('T -> 'State -> 'State) -> 'T[] input -> 'State -> 'State

從右到左累積陣列。

val iter : ('T -> unit) -> 'T[] input -> unit

將函式應用於輸入陣列的所有元素。

val length : 'T[] -> int

返回陣列中的專案數。

val map : ('T -> 'U) -> 'T[] -> 'U[]

將對映函式應用於輸入陣列中的每個元素，以返回一個新陣列。

val rev : 'T[] input -> 'T[]

返回一個新陣列，其中專案以相反順序排列。

val sort : 'T[] -> 'T[]

對陣列的副本進行排序。

val sortInPlace : 'T[] -> unit

對陣列進行就地排序。請注意，sortInPlace 方法返回 unit，表示 sortInPlace 會改變原始陣列。

val sortBy : ('T -> 'T -> int) -> 'T[] -> 'T[]

根據排序函式對陣列的副本進行排序。

val sub : 'T[] -> int start -> int end -> 'T[]

根據給定的開始和結束索引返回子陣列。

陣列和列表之間的區別

[edit | edit source]
  • 列表
    • 不可變，允許新列表與其他列表共享節點。
    • 列表字面量。
    • 模式匹配。
    • 支援對映和摺疊。
    • 線性查詢時間。
    • 無法隨機訪問元素，只能“向前”遍歷。
  • 陣列
    • 陣列字面量。
    • 常數查詢時間。
    • 良好的空間區域性性確保高效的查詢時間。
    • 索引表示每個元素相對於其他元素的位置，使陣列成為隨機訪問的理想選擇。
    • 支援對映和摺疊。
    • 可變性阻止陣列與陣列中的其他元素共享節點。
    • 不可調整大小。

記憶體表示

[edit | edit source]

陣列中的專案在記憶體中表示為記憶體中的相鄰值。例如，假設我們建立了以下 int 陣列

[| 15; 5; 21; 0; 9 |]

在記憶體中表示，我們的陣列類似於

Memory Location: |  100 |  104 |  108 |  112 |  116
          Value: |   15 |    5 |   21 |    0 |    9
          Index: |    0 |    1 |    2 |    3 |    4

每個 int 佔用 4 位元組的記憶體。由於我們的陣列包含 5 個元素，作業系統分配 20 位元組的記憶體來儲存此陣列（4 位元組 * 5 個元素 = 20 位元組）。陣列中的第一個元素佔用記憶體 100-103，第二個元素佔用記憶體 104-107，依此類推。

我們知道陣列中的每個元素都由其在陣列中的索引或位置標識。實際上，索引是一個偏移量：由於陣列從記憶體位置 100 開始，並且陣列中的每個元素都佔用固定數量的記憶體，因此作業系統可以使用以下公式知道記憶體中每個元素的確切地址

索引為 n 的元素的起始記憶體地址 = 陣列的起始位置 + (n * 資料型別長度)
索引為 n 的元素的結束記憶體地址 = 起始記憶體地址 + 資料型別長度

通俗地說，這意味著我們可以在常數時間內訪問陣列的第 n 個元素，即 O(1) 個操作。這與列表形成對比，在列表中訪問第 n 個元素需要 O(n) 個操作。

瞭解陣列中的元素佔用相鄰的記憶體位置後，我們可以推斷出陣列的兩個屬性

  1. 建立陣列需要程式設計師事先指定陣列的大小，否則作業系統將不知道要分配多少個相鄰的記憶體位置。
  2. 陣列不可調整大小，因為第一個元素之前的或最後一個元素之後的記憶體位置可能儲存其他應用程式使用的資料。只有透過分配新的記憶體塊並將所有元素從舊陣列複製到新陣列中才能“調整”陣列的大小。
前一節：控制流 索引 下一節：可變集合
摘自 "https://wikibook.tw/w/index.php?title=F_Sharp_Programming/Arrays&oldid=4414775"
華夏公益教科書