模組 Stdlib.ArrayLabels

module ArrayLabels: ArrayLabels

type 'a t = 'a array 

陣列類型的別名。

val length : 'a array -> int

返回給定陣列的長度(元素數量)。

val get : 'a array -> int -> 'a

get a n 返回陣列 a 中編號為 n 的元素。第一個元素的編號為 0。最後一個元素的編號為 length a - 1。您也可以使用 a.(n) 來代替 get a n

val set : 'a array -> int -> 'a -> unit

set a n x 會原地修改陣列 a,將編號為 n 的元素替換為 x。您也可以使用 a.(n) <- x 來代替 set a n x

val make : int -> 'a -> 'a array

make n x 返回一個長度為 n 的新陣列,並以 x 初始化。這個新陣列的所有元素最初在物理上都等於 x(在 == 謂詞的意義上)。因此,如果 x 是可變的,它將在陣列的所有元素之間共享,並且通過其中一個陣列條目修改 x 將同時修改所有其他條目。

val create_float : int -> float array

create_float n 返回一個長度為 n 的新浮點數陣列,且資料未初始化。

val init : int -> f:(int -> 'a) -> 'a array

init n ~f 返回一個長度為 n 的新陣列,其中編號為 i 的元素初始化為 f i 的結果。換句話說,init n ~f 會按順序將 f 應用於整數 0n-1 的結果製成表格。

val make_matrix : dimx:int -> dimy:int -> 'a -> 'a array array

make_matrix ~dimx ~dimy e 返回一個二維陣列(陣列的陣列),其中第一維為 dimx,第二維為 dimy。這個新矩陣的所有元素最初在物理上都等於 e。矩陣 m 的元素 (x,y) 可以使用 m.(x).(y) 來存取。

val init_matrix : dimx:int -> dimy:int -> f:(int -> int -> 'a) -> 'a array array

init_matrix ~dimx ~dimy ~f 返回一個二維陣列(陣列的陣列),其中第一維為 dimx,第二維為 dimy,索引 (x,y) 處的元素使用 f x y 初始化。矩陣 m 的元素 (x,y) 可以使用 m.(x).(y) 來存取。

val append : 'a array -> 'a array -> 'a array

append v1 v2 返回一個新的陣列,其中包含陣列 v1v2 的串聯。

val concat : 'a array list -> 'a array

ArrayLabels.append 相同,但會串聯陣列列表。

val sub : 'a array -> pos:int -> len:int -> 'a array

sub a ~pos ~len 返回一個長度為 len 的新陣列,其中包含陣列 a 中編號從 pospos + len - 1 的元素。

val copy : 'a array -> 'a array

copy a 返回 a 的副本,也就是一個包含與 a 相同元素的新陣列。

val fill : 'a array -> pos:int -> len:int -> 'a -> unit

fill a ~pos ~len x 會原地修改陣列 a,將 x 儲存在編號從 pospos + len - 1 的元素中。

val blit : src:'a array -> src_pos:int -> dst:'a array -> dst_pos:int -> len:int -> unit

blit ~src ~src_pos ~dst ~dst_pos ~len 從陣列 src 中編號為 src_pos 的元素開始複製 len 個元素到陣列 dst,從編號為 dst_pos 的元素開始。即使 srcdst 是同一個陣列,並且來源和目的地區塊重疊,此函數也能正常運作。

val to_list : 'a array -> 'a list

to_list a 返回 a 的所有元素的列表。

val of_list : 'a list -> 'a array

of_list l 返回一個新的陣列,其中包含 l 的元素。

迭代器

val iter : f:('a -> unit) -> 'a array -> unit

iter ~f a 依次將函數 f 應用於 a 的所有元素。它等效於 f a.(0); f a.(1); ...; f a.(length a - 1); ()

val iteri : f:(int -> 'a -> unit) -> 'a array -> unit

ArrayLabels.iter 相同,但該函數的第一個參數會應用於元素的索引,第二個參數則為元素本身。

val map : f:('a -> 'b) -> 'a array -> 'b array

map ~f a 將函數 f 應用於 a 的所有元素,並建構一個以 f 返回的結果構成的陣列:[| f a.(0); f a.(1); ...; f a.(length a - 1) |]

val map_inplace : f:('a -> 'a) -> 'a array -> unit

map_inplace ~f a 將函數 f 應用於 a 的所有元素,並原地更新它們的值。

val mapi : f:(int -> 'a -> 'b) -> 'a array -> 'b array

ArrayLabels.map 相同,但該函數的第一個參數會應用於元素的索引,第二個參數則為元素本身。

val mapi_inplace : f:(int -> 'a -> 'a) -> 'a array -> unit

ArrayLabels.map_inplace 相同,但該函數的第一個參數會應用於元素的索引,第二個參數則為元素本身。

val fold_left : f:('acc -> 'a -> 'acc) -> init:'acc -> 'a array -> 'acc

fold_left ~f ~init a 計算 f (... (f (f init a.(0)) a.(1)) ...) a.(n-1),其中 n 是陣列 a 的長度。

val fold_left_map : f:('acc -> 'a -> 'acc * 'b) -> init:'acc -> 'a array -> 'acc * 'b array

fold_left_mapArrayLabels.fold_leftArrayLabels.map 的組合,它會在對 f 的呼叫中傳遞累加器。

val fold_right : f:('a -> 'acc -> 'acc) -> 'a array -> init:'acc -> 'acc

fold_right ~f a ~init 計算 f a.(0) (f a.(1) ( ... (f a.(n-1) init) ...)),其中 n 是陣列 a 的長度。

兩個陣列的迭代器

val iter2 : f:('a -> 'b -> unit) -> 'a array -> 'b array -> unit

iter2 ~f a b 將函數 f 應用於 ab 的所有元素。

val map2 : f:('a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array

map2 ~f a b 將函數 f 應用於 ab 的所有元素,並建構一個以 f 返回的結果構成的陣列:[| f a.(0) b.(0); ...; f a.(length a - 1) b.(length b - 1)|]

陣列掃描

val for_all : f:('a -> bool) -> 'a array -> bool

for_all ~f [|a1; ...; an|] 檢查陣列的所有元素是否滿足謂詞 f。也就是說,它會返回 (f a1) && (f a2) && ... && (f an)

val exists : f:('a -> bool) -> 'a array -> bool

exists ~f [|a1; ...; an|] 檢查陣列中是否至少有一個元素滿足謂詞 f。也就是說,它會返回 (f a1) || (f a2) || ... || (f an)

val for_all2 : f:('a -> 'b -> bool) -> 'a array -> 'b array -> bool

ArrayLabels.for_all 相同,但適用於雙參數謂詞。

val exists2 : f:('a -> 'b -> bool) -> 'a array -> 'b array -> bool

ArrayLabels.exists 相同,但適用於雙參數謂詞。

val mem : 'a -> set:'a array -> bool

如果且唯如果 aset 的一個元素結構相等(即 set 中存在一個 x 使得 compare a x = 0),則 mem a ~set 為真。

val memq : 'a -> set:'a array -> bool

ArrayLabels.mem 相同,但使用物理相等性而不是結構相等性來比較陣列元素。

val find_opt : f:('a -> bool) -> 'a array -> 'a option

find_opt ~f a 返回陣列 a 中滿足謂詞 f 的第一個元素,如果陣列 a 中沒有滿足 f 的值,則返回 None

val find_index : f:('a -> bool) -> 'a array -> int option

find_index ~f a 返回 Some i,其中 i 是陣列 a 中滿足 f x 的第一個元素的索引(如果存在這樣的元素)。

如果不存在這樣的元素,則返回 None

val find_map : f:('a -> 'b option) -> 'a array -> 'b option

find_map ~f a 依序將 f 應用於 a 的元素,並返回 Some v 形式的第一個結果,如果沒有任何結果,則返回 None

val find_mapi : f:(int -> 'a -> 'b option) -> 'a array -> 'b option

find_map 相同,但謂詞的第一個參數(從 0 開始計數)會應用於元素的索引,第二個參數則為元素本身。

成對陣列

val split : ('a * 'b) array -> 'a array * 'b array

split [|(a1,b1); ...; (an,bn)|] 會產生 ([|a1; ...; an|], [|b1; ...; bn|])

val combine : 'a array -> 'b array -> ('a * 'b) array

combine [|a1; ...; an|] [|b1; ...; bn|] 會產生 [|(a1,b1); ...; (an,bn)|]。如果兩個陣列的長度不同,則會引發 Invalid_argument

排序與隨機排序

val sort : cmp:('a -> 'a -> int) -> 'a array -> unit

根據比較函數,以遞增順序排序陣列。比較函數必須在兩個參數相等時返回 0,第一個參數大於第二個參數時返回正整數,第一個參數小於第二個參數時返回負整數(詳見下方完整規範)。例如,compare 是一個合適的比較函數。呼叫 sort 後,陣列會原地以遞增順序排序。sort 保證在常數堆積空間和(最多)對數堆疊空間中執行。

目前的實作使用堆積排序。它在常數堆疊空間中執行。

比較函數的規範:令 a 為陣列,cmp 為比較函數。對於 a 中的所有 xyz,以下條件必須成立:

  • cmp x y > 0 若且唯若 cmp y x < 0
  • cmp x y >= 0 且 cmp y z >= 0,則 cmp x z >= 0

sort 返回時,a 包含與之前相同的元素,只是重新排序過,使得對於所有 a 的有效索引 i 和 j,

  • cmp a.(i) a.(j) >= 0 若且唯若 i >= j
val stable_sort : cmp:('a -> 'a -> int) -> 'a array -> unit

ArrayLabels.sort 相同,但排序演算法是穩定的(即比較相等的元素會保持其原始順序),且不保證在常數堆積空間中執行。

目前的實作使用合併排序。它使用一個長度為 n/2 的臨時陣列,其中 n 是陣列的長度。它通常比目前的 ArrayLabels.sort 實作更快。

val fast_sort : cmp:('a -> 'a -> int) -> 'a array -> unit

ArrayLabels.sortArrayLabels.stable_sort 相同,取決於哪一個在典型輸入上更快。

val shuffle : rand:(int -> int) -> 'a array -> unit

shuffle ~rand a 使用 rand 作為隨機性來源,隨機排列 a 的元素。排列的分布是均勻的。

rand 必須是這樣一種函數:呼叫 rand n 會返回一個在範圍 [0; n-1] 內均勻分布的隨機數。Random.int 可以用於此目的(不要忘記初始化產生器)。

陣列與序列

val to_seq : 'a array -> 'a Seq.t

以遞增順序迭代陣列。迭代期間對陣列的修改將反映在序列中。

val to_seqi : 'a array -> (int * 'a) Seq.t

以遞增順序迭代陣列,同時產生元素的索引。迭代期間對陣列的修改將反映在序列中。

val of_seq : 'a Seq.t -> 'a array

從產生器建立一個陣列

陣列與並行安全

從多個網域並行存取陣列時必須小心:存取陣列永遠不會使程式崩潰,但未同步的存取可能會產生令人驚訝的(非循序一致的)結果。

原子性

每個存取多個陣列元素的陣列操作都不是原子的。這包括迭代、掃描、排序、分割和組合陣列。

例如,考慮以下程式

let size = 100_000_000
let a = ArrayLabels.make size 1
let d1 = Domain.spawn (fun () ->
   ArrayLabels.iteri ~f:(fun i x -> a.(i) <- x + 1) a
)
let d2 = Domain.spawn (fun () ->
  ArrayLabels.iteri ~f:(fun i x -> a.(i) <- 2 * x + 1) a
)
let () = Domain.join d1; Domain.join d2

執行此程式碼後,陣列 a 的每個欄位的值不是 234 就是 5。如果需要原子性,則使用者必須實作自己的同步機制(例如,使用 Mutex.t)。

資料競爭

如果兩個網域僅存取陣列的不相交部分,則觀察到的行為等效於來自兩個網域的操作的某些循序交錯。

當兩個網域在沒有同步的情況下存取同一個陣列元素,且至少有一個存取是寫入時,會發生資料競爭。在沒有資料競爭的情況下,觀察到的行為等效於來自不同網域的操作的某些循序交錯。

應盡可能使用同步來調解對陣列元素的存取,以避免資料競爭。

事實上,在存在資料競爭的情況下,程式不會崩潰,但觀察到的行為可能不等效於來自不同網域的操作的任何循序交錯。儘管如此,即使存在資料競爭,讀取操作也會返回先前對該位置的某次寫入的值(浮點數陣列有一些例外)。

浮點數陣列

在存在資料競爭的情況下,浮點數陣列有兩個額外的注意事項。

首先,blit 操作可能會逐位元組複製陣列。這種 blit 操作與另一個操作之間的資料競爭可能會由於撕裂而產生令人驚訝的值:部分寫入與其他操作交錯可能會建立在循序執行中不存在的浮點數值。

例如,在

let zeros = Array.make size 0.
let max_floats = Array.make size Float.max_float
let res = Array.copy zeros
let d1 = Domain.spawn (fun () -> Array.blit zeros 0 res 0 size)
let d2 = Domain.spawn (fun () -> Array.blit max_floats 0 res 0 size)
let () = Domain.join d1; Domain.join d2

結束時,res 陣列可能包含既不是 0. 也不是 max_float 的值。

其次,在 32 位元架構上,取得或設定欄位涉及兩個單獨的記憶體存取。在存在資料競爭的情況下,使用者可能會在任何操作中觀察到撕裂。