Модуль 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 init_matrix : dimx:int -> dimy:int -> f:(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

Аналогично 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 map_inplace : f:('a -> 'a) -> 'a array -> unit

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

С 5.1

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

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

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

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

С 5.1

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

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

С 4.13

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

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
Возбуждает 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)|].

Since 4.05
Raises Invalid_argument если массивы имеют разный размер.

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

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

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

Since 4.03

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

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

Since 4.03

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

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

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

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

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

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

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

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

Since 4.03

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

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

Since 4.03

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

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

Since 4.13

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

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

Возвращает None в противном случае.

Since 5.1

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

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

Since 4.13

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