Модуль Dynarray

module Dynarray: sig .. end

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

Несинхронизированные обращения

Одновременные обращения к динамическим массивам должны быть синхронизированы (например, с помощью Mutex.t). Несинхронизированные обращения к динамическому массиву являются программистской ошибкой, которая может привести к некорректному состоянию динамического массива, в котором некоторые операции завершатся с исключением Invalid_argument.

Динамические массивы

type !'a t 

val create : unit -> 'a t

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

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

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

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

val length : 'a t -> int

val is_empty : 'a t -> bool

val get_last : 'a t -> 'a

val find_last : 'a t -> 'a option

val copy : 'a t -> 'a t

Добавление элементов

Примечание: все операции добавления элементов возбуждают Invalid_argument если длина должна увеличиться до Sys.max_array_length.

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

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

      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

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

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

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

Удаление элементов

val pop_last_opt : 'a t -> 'a option

val pop_last : 'a t -> 'a

val remove_last : 'a t -> unit

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

      if n < 0 then invalid_argument "...";
      while length a > n do
        remove_last a
      done
    

val clear : 'a t -> unit

Итерация

Функции итерации обрабатывают элементы динамического массива. Итерации по a вычисляются в порядке возрастания индексов: от элемента с индексом 0 до элемента с индексом length a - 1.

Это программистская ошибка изменять длину массива (добавляя или удаляя элементы) во время итерации по массиву. Любая функция итерации завершится с Invalid_argument если она обнаружит такое изменение длины.

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

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

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

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

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

      let acc = f acc x0 in
      let acc = f acc x1 in
      acc
    

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

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

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

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

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

Преобразования в другие структуры данных

Примечание: функции of_* вызывают исключение Invalid_argument если длина должна вырасти за пределы Sys.max_array_length.

Функции to_*, кроме явно помеченных как «рекурсивные», итерируют по аргументу dynarray. В частности, это ошибка программирования, если длина dynarray изменяется во время их выполнения, и функции преобразования вызывают исключение Invalid_argument если они наблюдают такое изменение.

val of_array : 'a array -> 'a t

val to_array : 'a t -> 'a array

val of_list : 'a list -> 'a t

val to_list : 'a t -> 'a list

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

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

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

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

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

Расширенные темы производительности

Поддерживающий массив, ёмкость

Внутренне, динамический массив использует поддерживающий массив (массив фиксированной длины, предоставляемый модулем Array), длина которого больше или равна длине динамического массива. Мы определяем ёмкость динамического массива как длину его поддерживающего массива.

Ёмкость динамического массива важна в расширенных сценариях, когда необходимо рассуждать о производительности программ с динамическими массивами:

• Использование памяти динамическим массивом пропорционально его ёмкости, а не длине.
• Когда свободных ячеек в конце поддерживающего массива нет, добавление элементов требует выделения нового, большего поддерживающего массива.

Реализация использует стандартную стратегию экспоненциального перераспределения, которая гарантирует амортизированное постоянное время операции; в частности, общая ёмкость всех поддерживающих массивов, выделенных за время жизни динамического массива, в худшем случае пропорциональна общему числу добавленных элементов.

Другими словами, пользователям не нужно беспокоиться о ёмкости и перераспределении, и они получат приемлемое поведение по умолчанию. Однако в некоторых сценариях, чувствительных к производительности, приведенные ниже функции могут помочь контролировать использование памяти или гарантировать оптимальное число перераспределений.

val capacity : 'a t -> int

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

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

val fit_capacity : 'a t -> unit

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

val reset : 'a t -> unit

Отсутствие утечек памяти: сохранение актуальности памяти

Значения, предоставленные пользователем и доступные из динамического массива a , — это ровно элементы в позициях 0 по length a - 1. В частности, никакие значения, предоставленные пользователем, не «утечка» путем присутствия в базовом массиве в позиции length a или позже.

Макет памяти dynarrays

В текущей реализации базовый массив '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