module Dynarray: Dynarray
非同步访问
对动态数组的并发访问必须进行同步(例如,使用 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
。
Invalid_argument
如果 n < 0
或 n > Sys.max_array_length
。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
.
Invalid_argument
如果 n < 0
或 n > Sys.max_array_length
。val get : 'a t -> int -> 'a
get a i
是 a
的第 i
个元素,从索引 0
开始。
Invalid_argument
如果索引无效val set : 'a t -> int -> 'a -> unit
set a i x
将 a
的第 i
个元素设置为 x
。
i
必须是有效索引。 set
不会向数组添加新元素 - 请参见 Dynarray.add_last
以添加元素。
Invalid_argument
如果索引无效。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 a
是 a
中索引 length a - 1
处的元素。
Invalid_argument
如果 a
为空。val find_last : 'a t -> 'a option
find_last a
如果 a
为空,则为 None
,否则为 Some (get_last a)
。
val copy : 'a t -> 'a t
copy a
是 a
的浅拷贝,一个新的数组,包含与 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 b
在 a
的末尾添加 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 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
的最后一个元素。
Not_found
在空数组上。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
Invalid_argument
如果 n < 0
。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
,对于 a
的每个元素 x
。
例如,如果 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
,对于 a
中索引 i
处的每个元素 x
。
例如,如果 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
exists f a
如果 a
中的某个元素满足 f
,则为 true
。
例如,如果 a
的元素是 x0
、x1
、x2
,那么 exists f a
是 f x0 || f x1 || f x2
。
val for_all : ('a -> bool) -> 'a t -> bool
for_all f a
如果 a
中的所有元素都满足 f
,则为 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
,使得 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 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
。
Invalid_argument
,如果请求的容量不在范围 0 .. Sys.max_array_length
内。例如,重新实现 Dynarray.of_array
而不用 Dynarray.init
let of_array arr =
let a = Dynarray.create () in
Dynarray.ensure_capacity a (Array.length arr);
Array.iter (fun v -> add_last a v) arr
使用 ensure_capacity
可以保证最多只进行一次重新分配,而不是可能进行多次重新分配。如果没有此 ensure_capacity
提示,重新调整大小的次数将是 arr
长度的对数,这会在 arr
很大时产生一个恒定的因子减速。val ensure_extra_capacity : 'a t -> int -> unit
ensure_extra_capacity a n
等于 ensure_capacity a (length a + n)
,它确保 a
有空间容纳 n
个额外的项。
Invalid_argument
,如果请求的总容量不在范围 0 .. Sys.max_array_length
内。一个用例是实现 Dynarray.append_array
let append_array a arr =
ensure_extra_capacity a (Array.length arr);
Array.iter (fun v -> add_last a v) arr
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
应该优先用于增加容量,因为它保留了这些摊销保证。
Invalid_argument
如果 n < 0
。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%。我们相信,对于大多数使用 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