跳转到内容

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://wikibooks.cn/w/index.php?title=F_Sharp_Programming/Arrays&oldid=4414775"
华夏公益教科书