Модуль 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 предоставляет структуру данных типа «последним пришёл — первым ушёл» (LIFO), которую легко реализовать на основе динамических массивов.

Начиная с 5.2
Предупреждение unsynchronized_access. Несинхронизированный доступ к динамическим массивам является ошибкой программирования.

Несинхронизированный доступ

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

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

type !'a t

Динамический массив, содержащий значения типа 'a.

Динамический массив a обеспечивает выполнение операций get и set за константное время для индексов от 0 до Dynarray.length a - 1 включительно. Его длина 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 — это новый массив a длины n, такой что 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 — это i-й элемент a, начиная с индекса 0.

Вызывает Invalid_argument, если индекс недопустим

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

set a i x устанавливает значение i-го элемента a равным x.

i должен быть допустимым индексом. set не добавляет новые элементы в массив — см. функцию Dynarray.add_last для добавления элемента.

Вызывает Invalid_argument, если индекс недопустим.

val length : 'a t -> int

length a — это количество элементов в массиве.

val is_empty : 'a t -> bool

is_empty a возвращает true, если a пуст, то есть если 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 возвращает None, если a пуст, и 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 добавляет элемент x в конец массива a.

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

append_array a b добавляет все элементы массива b в конец a в том порядке, в котором они следуют в 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] добавит элементы 1, 2, а затем 3 в конец a. append_iter a Queue.iter q добавляет элементы из очереди q.

val blit : src:'a t ->       src_pos:int -> dst:'a t -> dst_pos:int -> len:int -> unit

blit ~src ~src_pos ~dst ~dst_pos ~len копирует len элементов из исходного динамического массива src, начиная с индекса src_pos, в целевой динамический массив dst, начиная с индекса dst_pos. Функция работает корректно, даже если src и dst — это один и тот же массив, а исходная и целевая области перекрываются.

В отличие от Array.blit, Dynarray.blit может расширять целевой массив новыми элементами: вызов blit допустим, даже если dst_pos + len больше, чем length dst. Единственное требование состоит в том, что dst_pos не должно превышать length dst (включительно), чтобы не было пробела между существующими элементами и областью копирования.

Начиная с 5.3
Вызывает Invalid_argument, если src_pos и len не определяют допустимый подмассив в src, либо если dst_pos строго меньше 0 или строго больше length dst.

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

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 вызывает f для каждого элемента a, от элемента с индексом 0 до элемента с индексом length a - 1.

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

rev_iter f a вызывает f для каждого элемента a, от элемента с индексом length a - 1 до элемента с индексом 0.

Начиная с 5.5

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

iteri f a вызывает f i x для каждого элемента x с индексом i в a, от индекса 0 до индекса length a - 1.

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

rev_iteri f a вызывает f i x для каждого элемента x с индексом i в a, от индекса length a - 1 по убыванию до индекса 0.

Начиная с 5.5

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 filter : ('a -> bool) -> 'a t -> 'a t

filter f a — это новый массив всех элементов a, удовлетворяющих условию f. Другими словами, это массив b, такой что для каждого элемента x в a по порядку, x добавляется в b, если f x равно true.

Например, filter (fun x -> x >= 0) a — это новый массив всех неотрицательных элементов a в исходном порядке.

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

filter_map f a — это новый массив элементов y, таких что f x равно Some y для элемента x из a. Другими словами, это массив b, такой что для каждого элемента x из a по порядку:

если f x = Some y, то y добавляется в b,
если f x = None, то в b элементы не добавляются.

Например, filter_map int_of_string_opt inputs возвращает новый массив целых чисел, считанных из строк в inputs, игнорируя строки, которые невозможно преобразовать в целые числа.

Сканирование динамического массива

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

exists f a возвращает true, если хотя бы один элемент a удовлетворяет условию f.

Например, если элементами 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 возвращает true, если все элементы a удовлетворяют условию f. Это включает случай, когда a пуст.

Например, если элементами a являются x0, x1, x2, то for_all f a возвращает f x0 && f x1 && f x2.

val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool

То же, что и Dynarray.exists, но для предиката с двумя аргументами.

Начиная с 5.4
Вызывает Invalid_argument, если два массива имеют разную длину.

val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool

То же, что и Dynarray.for_all, но для предиката с двумя аргументами.

Начиная с 5.4
Вызывает Invalid_argument, если два массива имеют разную длину.

val mem : 'a -> 'a t -> bool

mem a set возвращает true тогда и только тогда, когда a структурно равен элементу set (т. е. существует такой x в set, что compare a x = 0).

Начиная с 5.3

val memq : 'a -> 'a t -> bool

То же, что и Dynarray.mem, но использует физическое равенство вместо структурного для сравнения элементов массива.

Начиная с 5.3

val find_opt : ('a -> bool) -> 'a t -> 'a option

find_opt f a возвращает первый элемент массива a, удовлетворяющий предикату f, или None, если в массиве a нет значения, удовлетворяющего f.

Начиная с 5.3

val find_index : ('a -> bool) -> 'a t -> int option

find_index f a возвращает Some i, где i — индекс первого элемента массива a, удовлетворяющего f x, если такой элемент существует.

Возвращает None, если такого элемента нет.

Начиная с 5.3

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

find_map f a применяет f к элементам a по порядку и возвращает первый результат вида Some v или None, если таковых нет.

Начиная с 5.3

val find_mapi : (int -> 'a -> 'b option) -> 'a t -> 'b option

То же, что и find_map, но предикат применяется к индексу элемента в качестве первого аргумента (начиная с 0) и самому элементу в качестве второго аргумента.

Начиная с 5.3

Функции сравнения

Функции сравнения выполняют итерацию по своим аргументам; изменение их длины во время итерации является ошибкой программирования, см. раздел Итерация выше.

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

equal eq a b выполняется, когда a и b имеют одинаковую длину, и для всех индексов i выполняется eq (get a i) (get b i).

Начиная с 5.3

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

compare cmp a b сравнивает a и b в соответствии с порядком shortlex, то есть более короткие массивы меньше, а массивы одинакового размера сравниваются в лексикографическом порядке с использованием cmp для сравнения элементов.

Более подробную информацию о функциях сравнения см. в Array.sort.

Начиная с 5.3

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

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

Функции to_*, за исключением явно помеченных как «реентерабельные» (reentrant), итерируются по своему аргументу-динамическому массиву. В частности, изменение длины динамического массива во время их выполнения является ошибкой программирования, и функции преобразования вызывают 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-го элемента результирующей последовательности (который может произойти ноль, один или несколько раз) обратится к i-му элементу a на момент запроса. Последовательность завершается, если в этот момент 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 равно length a на момент вызова to_seq_rev.

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

to_seq_rev_reentrant a — это реентерабельный вариант функции Dynarray.to_seq_rev в том смысле, что доступ к её элементам остаётся возможным даже после изменения длины a.

Элементы, которые были удалены из массива к моменту их запроса в последовательности, пропускаются.

Дополнительные сведения о производительности

Базовый массив, вместимость

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

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

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

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

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

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 или выше.

val unsafe_to_iarray : capacity:int -> ('a t -> unit) -> 'a iarray

unsafe_to_iarray ~capacity f вызывает f на новом пустом динамическом массиве с заданной capacity, затем, когда это возможно, преобразует его в неизменяемый массив без копирования, а именно при выполнении двух условий:

элементы массива не являются числами с плавающей точкой (float), и
после возврата из f вместимость массива равна его длине.

Обратите внимание, что аргумент capacity является лишь подсказкой. Например, ничто не мешает вызвать Dynarray.fit_capacity в конце f.

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

Начиная с 5.4

Примеры кода

Мин-кучи для изменяемых очередей с приоритетом

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

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