Модуль StdLabels.Array

module Array: ArrayLabels

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

Since 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).

Since 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, и изменяет их значения на месте.

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

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

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

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

Конфликты данных

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

Конфликт данных возникает, когда две области обращаются к одному и тому же элементу массива без синхронизации, и по крайней мере одно из обращений является записью. В отсутствие конфликтов данных наблюдаемое поведение эквивалентно некоторому последовательному переплетению операций из различных областей.

По возможности, конфликты данных следует избегать, используя синхронизацию для управления доступом к элементам массива.

Действительно, в случае конфликтов данных программы не упадут, но наблюдаемое поведение может не соответствовать никакому последовательному переплетению операций из разных областей. Тем не менее, даже при наличии конфликтов данных операция чтения вернет значение некоторой предыдущей записи в это место (с несколькими исключениями для массивов с плавающей точкой).

Массивы с плавающей точкой

Массивы с плавающей точкой имеют два дополнительных нюанса в присутствии конфликтов данных.

Во-первых, операция копирования может копировать массив байт за байтом. Конфликты данных между такой операцией копирования и другой операцией могут привести к неожиданным значениям из-за разрыва (теaring): частичные записи, переплетённые с другими операциями, могут создавать значения с плавающей точкой, которые не существовали бы при последовательном выполнении.

Например, в конце

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