Модуль 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.

Вызывает 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 -> (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 : int -> 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 : 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).

Начиная с 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

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

val sub : 'a array -> int -> 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 -> int -> int -> 'a -> unit

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

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

Вызывает 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 : ('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 : ('a -> 'a -> int) -> 'a array -> 'a array -> int

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

Начиная с 5.4

Итераторы

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 и обновляет их значения на месте.

Начиная с 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, но функция принимает индекс элемента в качестве первого аргумента и сам элемент в качестве второго аргумента.

Начиная с 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.

Начиная с 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.

Начиная с 4.03 (4.05 в ArrayLabels)
Вызывает 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)|].

Начиная с 4.03 (4.05 в ArrayLabels)
Вызывает Invalid_argument, если массивы имеют разный размер.

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

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

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

Начиная с 4.03

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

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

Начиная с 4.03

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

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

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

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

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

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

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

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

Начиная с 4.03

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

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

Начиная с 4.03

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

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

Начиная с 4.13

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

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

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

Начиная с 5.1

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

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

Начиная с 4.13

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

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

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

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

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

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

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 (не забудьте инициализировать генератор).

Начиная с 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 = 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).

Гонки данных

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

Гонка данных (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) при любой операции.