Модуль ArrayLabels

module ArrayLabels: sig .. end

Операции с массивами.

Версию этого модуля с метками можно использовать так, как описано в модуле StdLabels.

type 'a t = 'a array

Псевдоним для типа массивов.

val length : 'a array -> int

Возвращает длину (количество элементов) указанного массива.

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

get a n возвращает элемент под номером n массива a. Первый элемент имеет номер 0. Последний элемент имеет номер length a - 1. Вы также можете написать a.(n) вместо get a n.

Вызывает Invalid_argument, если n находится вне диапазона от 0 до (length a - 1).

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

set a n x модифицирует массив a на месте, заменяя элемент под номером n на x. Вы также можете написать a.(n) <- x вместо set a n x.

Вызывает Invalid_argument, если n находится вне диапазона от 0 до length a - 1.

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

make n x возвращает новый массив длины n, инициализированный значением x. Все элементы этого нового массива изначально физически равны x (в смысле предиката ==). Следовательно, если x изменяем, он разделяется между всеми элементами массива, и изменение x через один из элементов массива одновременно изменит все остальные элементы.

Вызывает Invalid_argument, если n < 0 или n > Sys.max_array_length. Если значением x является число с плавающей точкой, максимальный размер составляет только Sys.max_array_length / 2.

val create_float : int -> float array

create_float n возвращает новый массив чисел с плавающей точкой длины n с неинициализированными данными.

С версии 4.03

val init : int -> f:(int -> 'a) -> 'a array

init n ~f возвращает новый массив длины n, где элемент под номером i инициализирован результатом f i. Иными словами, init n ~f табулирует результаты последовательного применения f к целым числам от 0 до n-1.

Вызывает Invalid_argument, если n < 0 или n > Sys.max_array_length. Если возвращаемым типом f является float, максимальный размер составляет только Sys.max_array_length / 2.

val make_matrix : dimx:int -> dimy:int -> 'a -> 'a array array

make_matrix ~dimx ~dimy e возвращает двумерный массив (массив массивов) с первой размерностью dimx и второй размерностью dimy. Все элементы этой новой матрицы изначально физически равны e. Доступ к элементу (x,y) матрицы m осуществляется с помощью нотации m.(x).(y).

Вызывает Invalid_argument, если dimx или dimy отрицательны или превышают Sys.max_array_length. Если значением e является число с плавающей точкой, максимальный размер составляет только Sys.max_array_length / 2.

val init_matrix : dimx:int -> dimy:int -> f:(int -> int -> 'a) -> 'a array array

init_matrix ~dimx ~dimy ~f возвращает двумерный массив (массив массивов) с первой размерностью dimx и второй размерностью dimy, где элемент по индексу (x,y) инициализирован значением f x y. Доступ к элементу (x,y) матрицы m осуществляется с помощью нотации m.(x).(y).

С версии 5.2
Вызывает Invalid_argument, если dimx или dimy отрицательны или превышают Sys.max_array_length. Если возвращаемым типом f является float, максимальный размер составляет только Sys.max_array_length / 2.

val append : 'a array -> 'a array -> 'a array

append v1 v2 возвращает новый массив, содержащий конкатенацию массивов v1 и v2.

Вызывает Invalid_argument, если length v1 + length v2 > Sys.max_array_length.

val concat : 'a array list -> 'a array

То же, что и ArrayLabels.append, но объединяет список массивов.

val sub : 'a array -> pos:int -> len:int -> 'a array

sub a ~pos ~len возвращает новый массив длины len, содержащий элементы с номерами от pos до pos + len - 1 массива a.

Вызывает Invalid_argument, если pos и len не определяют допустимый подмассив массива a; то есть если pos < 0, или len < 0, или pos + len > length a.

val copy : 'a array -> 'a array

copy a возвращает копию a, то есть новый массив, содержащий те же элементы, что и a.

val fill : 'a array -> pos:int -> len:int -> 'a -> unit

fill a ~pos ~len x модифицирует массив a на месте, сохраняя x в элементах с номерами от pos до pos + len - 1.

Вызывает Invalid_argument, если pos и len не определяют допустимый подмассив массива a.

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

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

Вызывает Invalid_argument, если src_pos и len не определяют допустимый подмассив массива src или если dst_pos и len не определяют допустимый подмассив массива dst.

val to_list : 'a array -> 'a list

to_list a возвращает список всех элементов массива a.

val of_list : 'a list -> 'a array

of_list l возвращает новый массив, содержащий элементы списка l.

Вызывает Invalid_argument, если длина списка l превышает Sys.max_array_length.

Сравнение

val equal : eq:('a -> 'a -> bool) -> 'a array -> 'a array -> bool

equal eq a b равно true тогда и только тогда, когда a и b имеют одинаковую длину n и для всех i в [0;n-1], eq a.(i) b.(i) равно true.

С версии 5.4

val compare : cmp:('a -> 'a -> int) -> 'a array -> 'a array -> int

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

С версии 5.4

Итераторы

val iter : f:('a -> unit) -> 'a array -> unit

iter ~f a поочередно применяет функцию f ко всем элементам массива a. Это эквивалентно f a.(0); f a.(1); ...; f a.(length a - 1); ().

val iteri : f:(int -> 'a -> unit) -> 'a array -> unit

То же, что и ArrayLabels.iter, но функция применяется к индексу элемента в качестве первого аргумента и к самому элементу в качестве второго аргумента.

val map : f:('a -> 'b) -> 'a array -> 'b array

map ~f a применяет функцию f ко всем элементам массива a и создает массив из результатов, возвращенных функцией f: [| f a.(0); f a.(1); ...; f a.(length a - 1) |].

val map_inplace : f:('a -> 'a) -> 'a array -> unit

map_inplace ~f a применяет функцию f ко всем элементам массива a и обновляет их значения на месте.

С версии 5.1

val mapi : f:(int -> 'a -> 'b) -> 'a array -> 'b array

То же, что и ArrayLabels.map, но функция применяется к индексу элемента в качестве первого аргумента и к самому элементу в качестве второго аргумента.

val mapi_inplace : f:(int -> 'a -> 'a) -> 'a array -> unit

То же, что и ArrayLabels.map_inplace, но функция применяется к индексу элемента в качестве первого аргумента и к самому элементу в качестве второго аргумента.

С версии 5.1

val fold_left : f:('acc -> 'a -> 'acc) -> init:'acc -> 'a array -> 'acc

fold_left ~f ~init a вычисляет f (... (f (f init a.(0)) a.(1)) ...) a.(n-1), где n — длина массива a.

val fold_left_map : f:('acc -> 'a -> 'acc * 'b) -> init:'acc -> 'a array -> 'acc * 'b array

fold_left_map представляет собой комбинацию ArrayLabels.fold_left и ArrayLabels.map, которая передает аккумулятор через вызовы функции f.

С версии 4.13

val fold_right : f:('a -> 'acc -> 'acc) -> 'a array -> init:'acc -> 'acc

fold_right ~f a ~init вычисляет f a.(0) (f a.(1) ( ... (f a.(n-1) init) ...)), где n — длина массива a.

Итераторы для двух массивов

val iter2 : f:('a -> 'b -> unit) -> 'a array -> 'b array -> unit

iter2 ~f a b применяет функцию f ко всем элементам массивов a и b.

С версии 4.05
Вызывает Invalid_argument, если массивы имеют разный размер.

val map2 : f:('a -> 'b -> 'c) -> 'a array -> 'b array -> 'c array

map2 ~f a b применяет функцию f ко всем элементам массивов a и b и создает массив из результатов, возвращенных функцией f: [| f a.(0) b.(0); ...; f a.(length a - 1) b.(length b - 1)|].

С версии 4.05
Вызывает Invalid_argument, если массивы имеют разный размер.

Сканирование массивов

val for_all : f:('a -> bool) -> 'a array -> bool

for_all ~f [|a1; ...; an|] проверяет, удовлетворяют ли все элементы массива предикату f. То есть возвращает (f a1) && (f a2) && ... && (f an).

С версии 4.03

val exists : f:('a -> bool) -> 'a array -> bool

exists ~f [|a1; ...; an|] проверяет, удовлетворяет ли хотя бы один элемент массива предикату f. То есть возвращает (f a1) || (f a2) || ... || (f an).

С версии 4.03

val for_all2 : f:('a -> 'b -> bool) -> 'a array -> 'b array -> bool

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

С версии 4.11
Вызывает Invalid_argument, если два массива имеют разную длину.

val exists2 : f:('a -> 'b -> bool) -> 'a array -> 'b array -> bool

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

С версии 4.11
Вызывает Invalid_argument, если два массива имеют разную длину.

val mem : 'a -> set:'a array -> bool

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

С версии 4.03

val memq : 'a -> set:'a array -> bool

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

С версии 4.03

val find_opt : f:('a -> bool) -> 'a array -> 'a option

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

С версии 4.13

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

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

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

С версии 5.1

val find_map : f:('a -> 'b option) -> 'a array -> 'b option

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

С версии 4.13

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

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

С версии 5.1

Массивы пар

val split : ('a * 'b) array -> 'a array * 'b array

split [|(a1,b1); ...; (an,bn)|] эквивалентно ([|a1; ...; an|], [|b1; ...; bn|]).

С версии 4.13

val combine : 'a array -> 'b array -> ('a * 'b) array

combine [|a1; ...; an|] [|b1; ...; bn|] эквивалентно [|(a1,b1); ...; (an,bn)|]. Вызывает Invalid_argument, если два массива имеют разную длину.

С версии 4.13

Сортировка и перемешивание

val sort : cmp:('a -> 'a -> int) -> 'a array -> unit

Сортирует массив по возрастанию в соответствии с функцией сравнения. Функция сравнения должна возвращать 0, если ее аргументы равны, положительное целое число, если первый больше, и отрицательное целое число, если первый меньше (полную спецификацию см. ниже). Например, подходящей функцией сравнения является compare. После вызова sort массив сортируется на месте по возрастанию. Гарантируется, что sort выполняется с постоянным использованием памяти в куче и (максимум) логарифмическим использованием памяти в стеке.

Текущая реализация использует пирамидальную сортировку (Heap Sort). Она работает с постоянным использованием пространства стека.

Спецификация функции сравнения: Пусть a — массив, а cmp — функция сравнения. Для всех x, y, z из a должно выполняться следующее:

cmp x y > 0 тогда и только тогда, когда cmp y x < 0
если cmp x y >= 0 и cmp y z >= 0, то cmp x z >= 0

Когда sort завершает работу, a содержит те же элементы, что и раньше, упорядоченные таким образом, что для всех допустимых индексов i и j массива a выполняется:

cmp a.(i) a.(j) >= 0, если i >= j

val stable_sort : cmp:('a -> 'a -> int) -> 'a array -> unit

То же, что и ArrayLabels.sort, но алгоритм сортировки является стабильным (т. е. элементы, сравниваемые как равные, сохраняют свой исходный порядок), и не гарантируется его выполнение с постоянным объемом памяти в куче.

Текущая реализация использует сортировку слиянием (Merge Sort). Она использует временный массив длины n/2, где n — длина массива. Обычно она работает быстрее, чем текущая реализация ArrayLabels.sort.

val stable_sort_sub : cmp:('a -> 'a -> int) -> 'a array -> pos:int -> len:int -> unit

stable_sort_sub ~cmp a ~pos ~len сортирует подмассив массива a, ограниченный начальной позицией pos и длиной len. Данные в этом подмассиве сортируются по возрастанию в соответствии с функцией сравнения cmp. Данные за пределами этого подмассива остаются без изменений. Алгоритм сортировки стабилен; он совпадает с алгоритмом в ArrayLabels.stable_sort.

С версии 5.5
Вызывает Invalid_argument, если pos и len не определяют допустимый подмассив массива a; то есть если pos < 0, или len < 0, или pos + len > length a.

val fast_sort : cmp:('a -> 'a -> int) -> 'a array -> unit

То же, что и ArrayLabels.sort или ArrayLabels.stable_sort, в зависимости от того, что быстрее на типичных входных данных.

val shuffle : rand:(int -> int) -> 'a array -> unit

shuffle ~rand a случайным образом переставляет элементы массива a, используя rand для получения случайных чисел. Распределение перестановок является равномерным.

Функция rand должна быть такой, чтобы вызов rand n возвращал равномерно распределенное случайное число в диапазоне [0;n-1]. Для этого можно использовать Random.int (не забудьте инициализировать генератор).

С версии 5.2

Массивы и последовательности

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

Итерация по массиву в порядке возрастания индексов. Изменения массива во время итерации будут отражаться в последовательности.

С версии 4.07

val to_seqi : 'a array -> (int * 'a) Seq.t

Итерация по массиву в порядке возрастания индексов с возвратом индексов вместе с элементами. Изменения массива во время итерации будут отражаться в последовательности.

С версии 4.07

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

Создает массив из генератора

С версии 4.07

Массивы и безопасность параллелизма

Следует соблюдать осторожность при одновременном доступе к массивам из нескольких доменов: доступ к массиву никогда не приведет к сбою программы, однако несинхронизированные обращения могут привести к неожиданным результатам (нарушающим последовательную согласованность).

Атомарность

Любая операция с массивом, которая обращается более чем к одному элементу массива, не является атомарной. Сюда входят итерация, сканирование, сортировка, разделение и объединение массивов.

Например, рассмотрим следующую программу:

let size = 100_000_000
let a = ArrayLabels.make size 1
let d1 = Domain.spawn (fun () ->
   ArrayLabels.iteri ~f:(fun i x -> a.(i) <- x + 1) a
)
let d2 = Domain.spawn (fun () ->
  ArrayLabels.iteri ~f:(fun i x -> a.(i) <- 2 * x + 1) a
)
let () = Domain.join d1; Domain.join d2

После выполнения этого кода каждое поле массива a будет равно либо 2, либо 3, либо 4, либо 5. Если требуется атомарность, пользователь должен реализовать собственную синхронизацию (например, используя Mutex.t).

Гонки данных

Если два домена обращаются только к непересекающимся частям массива, наблюдаемое поведение эквивалентно некоторому последовательному чередованию операций этих двух доменов.

Считается, что возникает гонка данных (data race), когда два домена обращаются к одному и тому же элементу массива без синхронизации, и хотя бы одно из этих обращений является записью. При отсутствии гонок данных наблюдаемое поведение эквивалентно некоторому последовательному чередованию операций из разных доменов.

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

Действительно, при наличии гонок данных программы не будут аварийно завершать работу, но наблюдаемое поведение может не быть эквивалентным какому-либо последовательному чередованию операций из разных доменов. Тем не менее, даже при наличии гонок данных операция чтения вернет значение некоторой предыдущей записи в эту ячейку (за несколькими исключениями для массивов float).

Массивы float

Массивы чисел с плавающей точкой имеют две дополнительные особенности при наличии гонок данных.

Во-первых, операция blit может копировать массив побайтово. Гонки данных между такой операцией blit и другой операцией могут приводить к неожиданным значениям из-за разрыва данных (tearing): частичные операции записи, чередующиеся с другими операциями, могут создавать значения float, которые не появились бы при последовательном выполнении.

Например, в конце

let zeros = Array.make size 0.
let max_floats = Array.make size Float.max_float
let res = Array.copy zeros
let d1 = Domain.spawn (fun () -> Array.blit zeros 0 res 0 size)
let d2 = Domain.spawn (fun () -> Array.blit max_floats 0 res 0 size)
let () = Domain.join d1; Domain.join d2

массив res может содержать значения, которые не равны ни 0., ни max_float.

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