Модуль Array

module Array: 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.

Raises 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.

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

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

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

Raises 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, с неинициализированными данными.

Since 4.03

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

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

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

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

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

Raises 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.

Raises Invalid_argument если length v1 + length v2 > Sys.max_array_length.

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

То же, что и Array.append, но конкатенирует список массивов.

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

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

Raises 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 -> int -> int -> 'a -> unit

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

Raises Invalid_argument если pos и len не обозначают допустимый подмассив a.

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

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

Raises 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.

Raises Invalid_argument если длина l больше Sys.max_array_length.

Итераторы

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

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

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

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

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

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

val fold_left : ('a -> 'b -> 'a) -> '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 : ('a -> 'b -> 'a * 'c) -> 'a -> 'b array -> 'a * 'c array

fold_left_map — комбинация Array.fold_left и Array.map, которая передаёт аккумулирующее значение через вызовы f.

Since 4.13.0

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

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

Итераторы по двум массивам

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

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

Since 4.03.0 (4.05.0 в ArrayLabels)
Raises Invalid_argument если массивы имеют разную длину.

val map2 : ('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)|].

Since 4.03.0 (4.05.0 в ArrayLabels)
Raises Invalid_argument если массивы имеют разную длину.

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

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

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

Since 4.03.0

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

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

Since 4.03.0

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

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

Since 4.11.0
Raises Invalid_argument если два массива имеют разную длину.

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

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

Since 4.11.0
Raises Invalid_argument если у двух массивов разная длина.

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

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

Since 4.03.0

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

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

Since 4.03.0

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

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

Since 4.13.0

val find_map : ('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 : ('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 : ('a -> 'a -> int) -> 'a array -> unit

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

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

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

Аналогично Array.sort или Array.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 = Array.make size 1
let d1 = Domain.spawn (fun () ->
   Array.iteri (fun i x -> a.(i) <- x + 1) a
)
let d2 = Domain.spawn (fun () ->
  Array.iteri (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-битных архитектурах получение или установка поля включает в себя два отдельных обращения к памяти. В случае гонок данных пользователь может наблюдать разрывы в любой операции.