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
。
Invalid_argument
異常,如果 n
超出 0 到 (length a - 1)
的範圍。val set : 'a array -> int -> 'a -> unit
set a n x
會原地修改陣列 a
,將編號為 n
的元素替換為 x
。您也可以使用 a.(n) <- x
來代替 set a n x
。
Invalid_argument
異常,如果 n
超出 0 到 length a - 1
的範圍。val make : int -> 'a -> 'a array
make n x
返回一個長度為 n
的新陣列,並以 x
初始化。這個新陣列的所有元素最初在物理上都等於 x
(在 ==
謂詞的意義上)。因此,如果 x
是可變的,它將在陣列的所有元素之間共享,並且通過其中一個陣列條目修改 x
將同時修改所有其他條目。
Invalid_argument
異常,如果 n < 0
或 n > Sys.max_array_length
。如果 x
的值是浮點數,則最大尺寸僅為 Sys.max_array_length / 2
。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
應用於整數 0
到 n-1
的結果製成表格。
Invalid_argument
異常,如果 n < 0
或 n > Sys.max_array_length
。如果 f
的返回類型是 float
,則最大尺寸僅為 Sys.max_array_length / 2
。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)
來存取。
Invalid_argument
異常,如果 dimx
或 dimy
為負數或大於 Sys.max_array_length
。如果 e
的值是浮點數,則最大尺寸僅為 Sys.max_array_length / 2
。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)
來存取。
Invalid_argument
異常,如果 dimx
或 dimy
為負數或大於 Sys.max_array_length
。如果 f
的返回類型是 float
,則最大尺寸僅為 Sys.max_array_length / 2
。val append : 'a array -> 'a array -> 'a array
append v1 v2
返回一個新的陣列,其中包含陣列 v1
和 v2
的串聯。
Invalid_argument
異常,如果 length v1 + length v2 > Sys.max_array_length
。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
中編號從 pos
到 pos + len - 1
的元素。
Invalid_argument
異常,如果 pos
和 len
未指定 a
的有效子陣列;也就是說,如果 pos < 0
,或 len < 0
,或 pos + len > length a
。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
儲存在編號從 pos
到 pos + len - 1
的元素中。
Invalid_argument
異常,如果 pos
和 len
未指定 a
的有效子陣列。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
的元素開始。即使 src
和 dst
是同一個陣列,並且來源和目的地區塊重疊,此函數也能正常運作。
Invalid_argument
異常,如果 src_pos
和 len
未指定 src
的有效子陣列,或者如果 dst_pos
和 len
未指定 dst
的有效子陣列。val to_list : 'a array -> 'a list
to_list a
返回 a
的所有元素的列表。
val of_list : 'a list -> 'a array
of_list l
返回一個新的陣列,其中包含 l
的元素。
Invalid_argument
異常,如果 l
的長度大於 Sys.max_array_length
。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_map
是 ArrayLabels.fold_left
和 ArrayLabels.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
應用於 a
和 b
的所有元素。
Invalid_argument
異常,如果陣列的大小不同。val map2 : f:('a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array
map2 ~f a b
將函數 f
應用於 a
和 b
的所有元素,並建構一個以 f
返回的結果構成的陣列:[| f a.(0) b.(0); ...; f a.(length a - 1) b.(length b - 1)|]
。
Invalid_argument
異常,如果陣列的大小不同。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
相同,但適用於雙參數謂詞。
Invalid_argument
異常,如果兩個陣列的長度不同。val exists2 : f:('a -> 'b -> bool) -> 'a array -> 'b array -> bool
與 ArrayLabels.exists
相同,但適用於雙參數謂詞。
Invalid_argument
異常,如果兩個陣列的長度不同。val mem : 'a -> set:'a array -> bool
如果且唯如果 a
與 set
的一個元素結構相等(即 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
中的所有 x
、y
、z
,以下條件必須成立:
cmp x y
> 0 若且唯若 cmp y x
< 0cmp x y
>= 0 且 cmp y z
>= 0,則 cmp x z
>= 0當 sort
返回時,a
包含與之前相同的元素,只是重新排序過,使得對於所有 a
的有效索引 i 和 j,
cmp a.(i) a.(j)
>= 0 若且唯若 i >= jval 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.sort
或 ArrayLabels.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
的每個欄位的值不是 2
、3
、4
就是 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 位元架構上,取得或設定欄位涉及兩個單獨的記憶體存取。在存在資料競爭的情況下,使用者可能會在任何操作中觀察到撕裂。