Модуль 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 init_matrix : int -> int -> (int -> int -> 'a) -> 'a array array

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

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

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 map_inplace : ('a -> 'a) -> 'a array -> unit

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

Since 5.1

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

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

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

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

Since 5.1

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

fold_left_map - это комбинация Array.fold_left и Array.map, которая передает накопитель через вызовы f.

Since 4.13

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

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 (4.05 в 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 (4.05 в 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

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

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

Since 4.03

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

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

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

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

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

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

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

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

Since 4.03

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

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

Since 4.03

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

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

Since 4.13

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

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

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

Since 5.1

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

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

Since 4.13

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

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

Since 5.1

Массивы пар

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

split [|(a1,b1); ...; (an,bn)|] это ([|a1; ...; an|], [|b1; ...; bn|]).

Since 4.13

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

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

Since 4.13

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

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

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

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

Since 5.2

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

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