模組 Dynarray

module Dynarray: sig .. end

動態陣列。

Array 模組提供固定長度的陣列。Dynarray 提供長度可以隨時間變化的陣列，透過在陣列末尾新增或移除元素來實現。

這通常用於累積事先未知數量或在計算過程中會變化的元素，同時也提供對任意位置元素的快速存取。

    let dynarray_of_list li =
      let arr = Dynarray.create () in
      List.iter (fun v -> Dynarray.add_last arr v) li;
      arr

Buffer 模組提供類似的功能，但它專門用於將字元累積到動態調整大小的字串中。

Stack 模組提供後進先出的資料結構，可以輕鬆地在動態陣列之上實作。

警告。 在目前的實作中，動態陣列的記憶體佈局與 Array 的記憶體佈局不同。請參閱 記憶體佈局 章節以取得更多資訊。

非同步存取

對動態陣列的並行存取必須同步（例如使用 Mutex.t）。對動態陣列進行非同步存取是一種程式設計錯誤，可能會導致動態陣列狀態無效，在這種狀態下，某些操作會失敗並產生 Invalid_argument 例外。

動態陣列

type !'a t

包含 'a 類型值的動態陣列。

動態陣列 a 在介於 0 和 Dynarray.length a - 1 之間的索引上提供常數時間的 get 和 set 操作。其 Dynarray.length 可以透過在陣列末尾新增或移除元素來隨時間變更。

如果動態陣列 a 的索引在 0 .. length a - 1 範圍內，我們稱之為有效索引，否則為無效索引。

val create : unit -> 'a t

create () 是一個新的空陣列。

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

make n x 是一個長度為 n 的新陣列，並以 x 填滿。

val init : int -> (int -> 'a) -> 'a t

init n f 是一個長度為 n 的新陣列 a，使得 get a i 為 f i。換句話說，a 的元素依序為 f 0、f 1、f 2... 最後是 f (n - 1)，並依此順序評估。

這類似於 Array.init。

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

get a i 是 a 的第 i 個元素，從索引 0 開始。

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

set a i x 將 a 的第 i 個元素設定為 x。

i 必須是有效的索引。set 不會將新元素加入陣列 - 請參閱 Dynarray.add_last 來新增元素。

val length : 'a t -> int

length a 是陣列中的元素數量。

val is_empty : 'a t -> bool

如果 a 為空，也就是 length a = 0，則 is_empty a 為 true。

val get_last : 'a t -> 'a

get_last a 是 a 中索引 length a - 1 的元素。

val find_last : 'a t -> 'a option

如果 a 為空，則 find_last a 為 None，否則為 Some (get_last a)。

val copy : 'a t -> 'a t

copy a 是 a 的淺層副本，一個包含與 a 相同元素的新陣列。

新增元素

注意：如果長度需要成長超過 Sys.max_array_length，則所有新增元素的操作都會引發 Invalid_argument 例外。

val add_last : 'a t -> 'a -> unit

add_last a x 將元素 x 加入陣列 a 的末尾。

val append_array : 'a t -> 'a array -> unit

append_array a b 將 b 的所有元素按照它們在 b 中出現的順序加入 a 的末尾。

例如

      let a = Dynarray.of_list [1;2] in
      Dynarray.append_array a [|3; 4|];
      assert (Dynarray.to_list a = [1; 2; 3; 4])
    
val append_list : 'a t -> 'a list -> unit

與 Dynarray.append_array 類似，但使用列表。

val append : 'a t -> 'a t -> unit

append a b 類似於 append_array a b，但 b 本身是一個動態陣列，而不是固定大小的陣列。

警告：append a a 是一種程式設計錯誤，因為它會同時迭代 a 並向其中新增元素 - 請參閱下方的 迭代 章節。它會因 Invalid_argument 例外而失敗。如果你真的想將 a 的副本附加到自身，可以使用 Dynarray.append_array a (Dynarray.to_array a)，它會將 a 複製到暫時陣列中。

val append_seq : 'a t -> 'a Seq.t -> unit

與 Dynarray.append_array 類似，但使用序列。

警告：append_seq a (to_seq_reentrant a) 會同時遍歷 a 並向其中新增元素；這些操作的順序未指定，可能會導致無限迴圈 - 新元素可能會由 to_seq_reentrant a 產生並一遍又一遍地被新增。

val append_iter : 'a t -> (('a -> unit) -> 'x -> unit) -> 'x -> unit

append_iter a iter x 將 x 的每個元素新增到 a 的末尾。這等同於 iter (add_last a) x。

例如，append_iter a List.iter [1;2;3] 會依序在 a 的末尾新增元素 1、2 和 3。append_iter a Queue.iter q 會新增佇列 q 中的元素。

移除元素

val pop_last_opt : 'a t -> 'a option

pop_last_opt a 移除並傳回 a 的最後一個元素，如果陣列為空，則傳回 None。

val pop_last : 'a t -> 'a

pop_last a 移除並傳回 a 的最後一個元素。

val remove_last : 'a t -> unit

remove_last a 移除 a 的最後一個元素（如果有的話）。如果 a 為空，則不執行任何操作。

val truncate : 'a t -> int -> unit

truncate a n 將 a 截斷為最多有 n 個元素。

它會移除索引大於或等於 n 的元素。如果 n >= length a，則不執行任何操作。

truncate a n 等同於

      if n < 0 then invalid_argument "...";
      while length a > n do
        remove_last a
      done
    
val clear : 'a t -> unit

clear a 等於 truncate a 0，它會移除 a 的所有元素。

迭代

迭代函式會遍歷動態陣列的元素。對 a 的遍歷會以遞增的索引順序計算：從索引 0 的元素到索引 length a - 1 的元素。

在對陣列進行迭代期間變更陣列的長度（透過新增或移除元素）是一種程式設計錯誤。如果任何迭代函式偵測到此類長度變更，則會因 Invalid_argument 例外而失敗。

val iter : ('a -> unit) -> 'a t -> unit

iter f a 會對 a 的每個元素呼叫 f。

val iteri : (int -> 'a -> unit) -> 'a t -> unit

iteri f a 會針對 a 中每個索引為 i 的 x 呼叫 f i x。

val map : ('a -> 'b) -> 'a t -> 'b t

map f a 是一個新陣列，其元素形式為 f x，其中 x 為 a 的每個元素。

例如，如果 a 的元素為 x0、x1、x2，則 b 的元素為 f x0、f x1、f x2。

val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t

mapi f a 是一個新陣列，其元素形式為 f i x，其中 x 為 a 中索引為 i 的每個元素。

例如，如果 a 的元素為 x0、x1、x2，則 b 的元素為 f 0 x0、f 1 x1、f 2 x2。

val fold_left : ('acc -> 'a -> 'acc) -> 'acc -> 'a t -> 'acc

fold_left f acc a 會按照順序將 f 折疊到 a 上，從累加器 acc 開始。

例如，如果 a 的元素為 x0、x1，則 fold f acc a 為

      let acc = f acc x0 in
      let acc = f acc x1 in
      acc
    
val fold_right : ('a -> 'acc -> 'acc) -> 'a t -> 'acc -> 'acc

fold_right f a acc 計算 f x0 (f x1 (... (f xn acc) ...))，其中 x0、x1、...、xn 為 a 的元素。

val exists : ('a -> bool) -> 'a t -> bool

如果 a 的某些元素滿足 f，則 exists f a 為 true。

例如，如果 a 的元素為 x0、x1、x2，則 exists f a 為 f x0 || f x1 || f x2。

val for_all : ('a -> bool) -> 'a t -> bool

如果 a 的所有元素都滿足 f，則 for_all f a 為 true。這包括 a 為空的情況。

例如，如果 a 的元素為 x0、x1，則 exists f a 為 f x0 && f x1 && f x2。

val filter : ('a -> bool) -> 'a t -> 'a t

filter f a 是一個新陣列，包含所有滿足 f 的 a 的元素。換句話說，它是一個陣列 b，使得對於 a 中的每個元素 x （按順序），如果 f x 為 true，則將 x 加入 b。

例如，filter (fun x -> x >= 0) a 是一個新的陣列，包含 a 中所有非負數元素（依順序）。

val filter_map : ('a -> 'b option) -> 'a t -> 'b t

filter_map f a 會產生一個新的元素陣列 y，條件是對於 a 陣列中的每個元素 x，f x 的結果為 Some y。換句話說，它是一個陣列 b，對於 a 中每個依序的元素 x：

  • 如果 f x = Some y，則將 y 加入 b。
  • 如果 f x = None，則不將任何元素加入 b。

例如，filter_map int_of_string_opt inputs 會從 inputs 中的字串讀取整數，並傳回一個新的整數陣列，忽略無法轉換為整數的字串。

轉換為其他資料結構

注意：如果長度需要超出 Sys.max_array_length，of_* 函數會引發 Invalid_argument 異常。

除了特別標示為「可重入」的 to_* 函數外，其他函數都會迭代其動態陣列參數。特別要注意的是，如果在執行過程中動態陣列的長度發生變化，則會造成程式錯誤，並且轉換函數如果觀察到這種變化，將會引發 Invalid_argument 異常。

val of_array : 'a array -> 'a t

of_array arr 會傳回與固定大小陣列 a 對應的動態陣列。此操作會透過複製的方式在 O(n) 時間內完成。

val to_array : 'a t -> 'a array

to_array a 會傳回與動態陣列 a 對應的固定大小陣列。這個操作會始終配置一個新的陣列並將元素複製到其中。

val of_list : 'a list -> 'a t

of_list l 會傳回一個陣列，其中包含與 l 相同順序的元素。

val to_list : 'a t -> 'a list

to_list a 會傳回一個列表，其中包含陣列 a 中的元素。

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

of_seq seq 會傳回一個陣列，其中包含與 seq 相同的元素。

它會遍歷 seq 一次，並且只有在 seq 是有限的情況下才會終止。

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

to_seq a 會傳回元素序列 get a 0、get a 1... get a (length a - 1)。

val to_seq_reentrant : 'a t -> 'a Seq.t

to_seq_reentrant a 是 Dynarray.to_seq 的可重入變體，表示在 a 的長度變更後，仍然可以存取其元素。

請求結果序列的第 i 個元素（可能發生零次、一次或多次），將會在請求時存取 a 的第 i 個元素。如果此時 a 的元素少於 i 個，則序列會停止。

val to_seq_rev : 'a t -> 'a Seq.t

to_seq_rev a 會傳回元素序列 get a (l - 1)、get a (l - 2)... get a 0，其中 l 是呼叫 to_seq_rev 時的 length a。

val to_seq_rev_reentrant : 'a t -> 'a Seq.t

to_seq_rev_reentrant a 是 Dynarray.to_seq_rev 的可重入變體，表示在 a 的長度變更後，仍然可以存取其元素。

在序列中請求時，從陣列中移除的元素將會被跳過。

效能進階主題

底層陣列、容量

在內部，動態陣列使用一個後備陣列（由 Array 模組提供的固定大小陣列），其長度大於或等於動態陣列的長度。我們將動態陣列的容量定義為其後備陣列的長度。

動態陣列的容量在進階情境中非常重要，用於推論動態陣列程式的效能。

實作使用標準的指數式重新配置策略，可保證分攤的常數時間操作；特別是，在動態陣列的生命週期中配置的所有後備陣列的總容量，最差的情況下也與加入的元素總數成正比。

換句話說，使用者無需關心容量和重新配置，而且它們預設會獲得合理的行為。但是，在某些對效能敏感的情況下，可以使用以下函數來幫助控制記憶體使用量或保證最佳的重新配置次數。

val capacity : 'a t -> int

capacity a 會傳回 a 的後備陣列長度。

val ensure_capacity : 'a t -> int -> unit

ensure_capacity a n 可確保 a 的容量至少為 n。

val ensure_extra_capacity : 'a t -> int -> unit

ensure_extra_capacity a n 等於 ensure_capacity a (length a + n)，它可確保 a 有空間容納 n 個額外項目。

val fit_capacity : 'a t -> unit

fit_capacity a 會在必要時重新配置後備陣列，使產生的容量剛好等於 length a，末尾沒有額外的空白空間。這對於確保不會在長期使用的陣列上浪費記憶體非常有用。

請注意，呼叫 fit_capacity 會破壞預設重新配置策略提供的分攤複雜度保證。在陣列上重複呼叫它可能會導致二次複雜度，無論是在時間還是在配置的字總數方面。

如果您知道動態陣列已達到其最終長度，而且將來會保持固定，則只要呼叫 to_array 並僅保留產生的固定大小陣列即可。當您需要保留動態陣列以進行將來的重新調整大小時，fit_capacity 會很有用。

val set_capacity : 'a t -> int -> unit

set_capacity a n 會在必要時重新配置後備陣列，使產生的容量剛好等於 n。特別是，會移除索引等於或大於 n 的所有元素。

與 Dynarray.fit_capacity 一樣，此函數會破壞重新配置策略提供的分攤複雜度保證。在陣列上重複呼叫它可能會導致二次複雜度，無論是在時間還是在配置的字總數方面。

這是一個進階函數；特別是，應該優先使用 Dynarray.ensure_capacity 來增加容量，因為它可以保留這些分攤保證。

val reset : 'a t -> unit

reset a 會清除 a，並將其後備陣列替換為空陣列。

它等同於 set_capacity a 0 或 clear a; fit_capacity a。

無記憶體洩漏：保留記憶體存活性

可以從動態陣列 a 存取的使用者提供的值正好是位置 0 到 length a - 1 中的元素。特別是，沒有使用者提供的值會因為出現在後備陣列中的位置 length a 或更後面的位置而「洩漏」。

動態陣列的記憶體佈局

在目前的實作中，'a Dynarray.t 的後備陣列並非 'a array，而是與 'a option array 或 'a ref array 具有相同表示形式的東西。每個元素都位於「方塊」中，該方塊會在第一次將元素新增至陣列時配置 – 請參閱實作了解更多詳細資訊。

使用 'a array 會很棘手，因為沒有明顯的類型正確方式來表示後備陣列末尾的空白空間 – 使用使用者提供的值會使 API 複雜化，或違反 不洩漏 保證。在不同步的並行使用下保持記憶體安全會使情況更加困難。目前已討論過各種不安全的方式來完成此操作，但目前尚未對標準實作達成共識。

在一個嚴重依賴動態陣列的真實自動定理證明程式上，我們測量到這個額外「裝箱」的額外負荷最多為 25%。我們認為，對於動態陣列的大部分用途而言，這個額外負荷要小得多，在許多情況下可忽略不計，但是您仍然可能希望使用自己的特殊實作來提高效能。（如果您知道您不需要 不洩漏 保證，您也可以加快刪除元素的速度。）

程式碼範例

可變優先佇列的最小堆積

我們可以使用動態陣列來實作可變的優先佇列。優先佇列提供一個新增元素的函數，以及一個根據某個比較函數來擷取最小元素的函數。

(* We present our priority queues as a functor
   parametrized on the comparison function. *)
module Heap (Elem : Map.OrderedType) : sig
  type t
  val create : unit -> t
  val add : t -> Elem.t -> unit
  val pop_min : t -> Elem.t option
end = struct

  (* Our priority queues are implemented using the standard "min heap"
     data structure, a dynamic array representing a binary tree. *)
  type t = Elem.t Dynarray.t
  let create = Dynarray.create

 (* The node of index [i] has as children the nodes of index [2 * i + 1]
    and [2 * i + 2] -- if they are valid indices in the dynarray. *)
  let left_child i = 2 * i + 1
  let right_child i = 2 * i + 2
  let parent_node i = (i - 1) / 2

  (* We use indexing operators for convenient notations. *)
  let ( .!() ) = Dynarray.get
  let ( .!()<- ) = Dynarray.set

  (* Auxiliary functions to compare and swap two elements
     in the dynamic array. *)
  let order h i j =
    Elem.compare h.!(i) h.!(j)

  let swap h i j =
    let v = h.!(i) in
    h.!(i) <- h.!(j);
    h.!(j) <- v

  (* We say that a heap respects the "heap ordering" if the value of
     each node is smaller than the value of its children. The
     algorithm manipulates arrays that respect the heap algorithm,
     except for one node whose value may be too small or too large.

     The auxiliary functions [heap_up] and [heap_down] take
     such a misplaced value, and move it "up" (respectively: "down")
     the tree by permuting it with its parent value (respectively:
     a child value) until the heap ordering is restored. *)

  let rec heap_up h i =
    if i = 0 then () else
    let parent = parent_node i in
    if order h i parent < 0 then
      (swap h i parent; heap_up h parent)

  and heap_down h ~len i =
    let left, right = left_child i, right_child i in
    if left >= len then () (* no child, stop *) else
    let smallest =
      if right >= len then left (* no right child *) else
      if order h left right < 0 then left else right
    in
    if order h i smallest > 0 then
      (swap h i smallest; heap_down h ~len smallest)

  let add h s =
    let i = Dynarray.length h in
    Dynarray.add_last h s;
    heap_up h i

  let pop_min h =
    if Dynarray.is_empty h then None
    else begin
      (* Standard trick: swap the 'best' value at index 0
         with the last value of the array. *)
      let last = Dynarray.length h - 1 in
      swap h 0 last;
      (* At this point [pop_last] returns the 'best' value,
         and leaves a heap with one misplaced element at position 0. *)
      let best = Dynarray.pop_last h in
      (* Restore the heap ordering -- does nothing if the heap is empty. *)
      heap_down h ~len:last 0;
      Some best
    end
end

此範例的來源生產程式碼包含在堆積變空時釋放後備陣列的邏輯，前提是容量高於特定閾值。可以透過從 pop 呼叫以下函數來完成此操作。

let shrink h =
  if Dynarray.length h = 0 && Dynarray.capacity h > 1 lsl 18 then
    Dynarray.reset h

可以使用 Heap 函子來實作排序函數，方法是將所有元素加入優先佇列，然後依序擷取它們。

let heap_sort (type a) cmp li =
  let module Heap = Heap(struct type t = a let compare = cmp end) in
  let heap = Heap.create () in
  List.iter (Heap.add heap) li;
  List.map (fun _ -> Heap.pop_min heap |> Option.get) li