模块 Stdlib.Dynarray

module Dynarray: Dynarray

非同步访问

对动态数组的并发访问必须进行同步(例如,使用 Mutex.t)。对动态数组的非同步访问是编程错误,可能导致动态数组状态无效,某些操作将在这种情况下失败,并抛出 Invalid_argument 异常。

动态数组

type !'a t 

包含类型为 'a 的值的动态数组。

动态数组 a 提供对从 0Dynarray.length a - 1(包含)的索引的恒定时间 getset 操作。它的 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 ia 的第 i 个元素,从索引 0 开始。

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

set a i xa 的第 i 个元素设置为 x

i 必须是有效索引。 set 不会向数组添加新元素 - 请参见 Dynarray.add_last 以添加元素。

val length : 'a t -> int

length a 是数组中元素的数量。

val is_empty : 'a t -> bool

is_empty a 如果 a 为空,则为 true,即如果 length a = 0

val get_last : 'a t -> 'a

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

val find_last : 'a t -> 'a option

find_last a 如果 a 为空,则为 None,否则为 Some (get_last a)

val copy : 'a t -> 'a t

copy aa 的浅拷贝,一个新的数组,包含与 a 相同的元素。

添加元素

注意:所有添加元素的操作都会引发 Invalid_argument 如果长度需要增长到超过 Sys.max_array_length.

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

add_last a x 在数组 a 的末尾添加元素 x

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

append_array a ba 的末尾添加 b 中的所有元素,以它们在 b 中出现的顺序。

例如

      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 bappend_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 xx 的每个元素添加到 a 的末尾。这与 iter (add_last a) x 相同。

例如,append_iter a List.iter [1;2;3] 会在 a 的末尾添加元素 12,然后是 3append_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 na 截断,使其最多包含 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 atruncate a 0,它删除 a 中的所有元素。

迭代

迭代函数遍历动态数组中的元素。 a 的遍历按递增索引顺序计算:从索引 0 的元素到索引 length a - 1 的元素。

在数组上迭代期间改变数组的长度(通过添加或删除元素)是编程错误。任何迭代函数如果检测到这种长度变化,都会失败,并抛出 Invalid_argument

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

iter f aa 的每个元素调用 f

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

iteri f aa 中索引 i 处的每个 x 调用 f i x

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

map f a 是一个新的数组,其元素的形式为 f x,对于 a 的每个元素 x

例如,如果 a 的元素是 x0x1x2,那么 b 的元素是 f x0f x1f x2

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

mapi f a 是一个新的数组,其元素的形式为 f i x,对于 a 中索引 i 处的每个元素 x

例如,如果 a 的元素是 x0x1x2,那么 b 的元素是 f 0 x0f 1 x1f 2 x2

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

fold_left f acc a 按顺序将 f 折叠到 a 上,从累加器 acc 开始。

例如,如果 a 的元素是 x0x1,那么 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) ...)),其中 x0x1、...、xna 的元素。

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

exists f a 如果 a 中的某个元素满足 f,则为 true

例如,如果 a 的元素是 x0x1x2,那么 exists f af x0 || f x1 || f x2

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

for_all f a 如果 a 中的所有元素都满足 f,则为 true。这包括 a 为空的情况。

例如,如果 a 的元素是 x0x1,那么 exists f af x0 && f x1 && f x2

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

filter f a 是一个新的数组,包含所有满足 fa 的元素。换句话说,它是一个数组 b,使得对于 a 中的每个元素 x(按顺序),如果 f xtrue,则 x 会被添加到 b 中。

例如,filter (fun x -> x >= 0) a 是一个新的数组,包含 a 中所有非负元素,按顺序排列。

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

filter_map f a 是一个新的数组,包含元素 y,使得 f x 对于 a 中的某个元素 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 0get a 1... get a (length a - 1) 的序列。

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

to_seq_reentrant aDynarray.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_revlength a 的值。

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

to_seq_rev_reentrant aDynarray.to_seq_rev 的可重入变体,这意味着即使在 a 的长度发生变化之后,您仍然可以访问其元素。

在序列中需要时,如果元素已从数组中删除,则会跳过这些元素。

性能高级主题

后备数组,容量

在内部,动态数组使用一个 **底层数组**(由 Array 模块提供的固定大小的数组),其长度大于或等于动态数组的长度。我们定义动态数组的 **容量** 为其底层数组的长度。

动态数组的容量在高级场景中是相关的,在这种场景中,需要推断动态数组程序的性能。

实现使用标准的指数式重新分配策略,该策略保证了摊销常数时间操作;特别是,在动态数组的生命周期内分配的所有底层数组的总容量最多与添加的元素总数成正比。

换句话说,用户无需关心容量和重新分配,默认情况下他们将获得合理的行为。但是,在某些性能敏感的场景中,以下函数可以帮助控制内存使用或保证最佳的重新分配次数。

val capacity : 'a t -> int

capacity aa 的底层数组的长度。

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 0clear a; fit_capacity a

无泄漏:内存活性保留

从动态数组 a 可达的用户提供的值,正是位置 0length a - 1 中的元素。特别是,没有用户提供的价值会被“泄漏”,因为它们出现在底层数组的位置 length a 或之后。

动态数组的内存布局

在当前实现中,'Dynarray.t 的底层数组不是一个 'a array,而是一个与 'a option array'a ref array 具有相同表示形式的东西。每个元素都在一个“框”中,在元素首次添加到数组时分配 - 有关更多详细信息,请参阅实现。

使用 'a array 会很麻烦,因为没有明显类型正确的方式来表示底层数组末尾的空闲空间 - 使用用户提供的价值要么会使 API 复杂化,要么会违反 无泄漏 保证。在不受同步的并发使用的情况下保持内存安全的约束使得这件事变得更加困难。已经讨论过各种不安全的方法来做到这一点,但目前还没有就标准实现达成共识。

在一个严重依赖动态数组的现实的自动定理证明程序中,我们测量了这种额外的“装箱”的开销,最多为 25%。我们相信,对于大多数使用 dynarray 的情况来说,开销要小得多,在许多情况下可以忽略不计,但您可能仍然希望使用自己的专门实现来提高性能。(如果您知道您不需要 无泄漏 保证,您还可以加快删除元素的速度。)

代码示例

用于可变优先级队列的最小堆

我们可以使用动态数组来实现一个可变优先队列。优先队列提供一个函数来添加元素,以及一个函数来提取最小元素 - 根据某个比较函数。

(* 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