Модуль StdLabels.Array

module Array: ArrayLabels

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 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 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 mapi : f:(int -> 'a -> 'b) -> 'a array -> 'b array

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

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

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

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

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

С момента 4.13.0

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

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.0
Возбуждает исключение 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.0
Возбуждает исключение 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.0

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

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

С момента 4.03.0

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

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

С момента 4.11.0
Возбуждает исключение Invalid_argument если массивы имеют разную длину.

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

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

С момента 4.11.0
Возбуждает исключение Invalid_argument если массивы имеют разную длину.

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

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

Since 4.03.0

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

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

Since 4.03.0

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

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

Since 4.13.0

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

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

Since 4.13.0

Массивы пар

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

split [|(a1,b1); ...; (an,bn)|] равно ([|a1; ...; an|], [|b1; ...; bn|]).

Since 4.13.0

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

combine [|a1; ...; an|] [|b1; ...; bn|] равно [|(a1,b1); ...; (an,bn)|]. Поднимайте Invalid_argument, если длины двух массивов отличаются.

Since 4.13.0

Сортировка

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

Сортирует массив в порядке возрастания согласно функции сравнения. Функция сравнения должна возвращать 0, если ее аргументы равны, положительное целое число, если первый больше, и отрицательное целое число, если первый меньше (см. полное описание ниже). Например, compare — подходящая функция сравнения. После вызова sort массив сортируется на месте в порядке возрастания. 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, но алгоритм сортировки является стабильным (т.е. элементы, сравниваемые как равные, сохраняют свой исходный порядок) и не гарантирует работу с постоянным объёмом памяти.

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

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

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

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

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

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

Since 4.07

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

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

Since 4.07

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

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

Since 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).

Конфликты данных

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

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

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

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

Массивы с плавающей точкой

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

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

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

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-битных архитектурах получение или установка элемента подразумевает два отдельных обращения к памяти. При наличии конфликтов данных пользователь может наблюдать разрывы при любой операции.