Модуль 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 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, но для предиката с двумя аргументами.

Since 4.11.0
Raises 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 если такого элемента нет, удовлетворяющего предикату f в массиве a.

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