Модуль Float.ArrayLabels

module ArrayLabels: sig .. end

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

type t = floatarray

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

Since 4.08

val length : t -> int

Возвращает длину (количество элементов) заданного floatarray.

val get : t -> int -> float

get a n возвращает номер элемента n floatarray a.

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

val set : t -> int -> float -> unit

set a n x изменяет floatarray a на месте, заменяя элемент с номером n на x.

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

val make : int -> float -> t

make n x возвращает новый floatarray длиной n, инициализированный x.

Raises Invalid_argument если n < 0 или n > Sys.max_floatarray_length.

val create : int -> t

create n возвращает новый floatarray длиной n, с неинициализированными данными.

Raises Invalid_argument если n < 0 или n > Sys.max_floatarray_length.

val init : int -> f:(int -> float) -> t

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

Raises Invalid_argument если n < 0 или n > Sys.max_floatarray_length.

val make_matrix : dimx:int -> dimy:int -> float -> t array

make_matrix ~dimx ~dimy e возвращает двумерный массив (массив массивов) с первым измерением dimx и вторым измерением dimy, где все элементы инициализированы e.

Since 5.2
Raises Invalid_argument если dimx или dimy отрицательны или больше, чем Sys.max_floatarray_length.

val init_matrix : dimx:int -> dimy:int -> f:(int -> int -> float) -> t array

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

Since 5.2
Raises Invalid_argument если dimx или dimy отрицательны или больше, чем Sys.max_floatarray_length.

val append : t -> t -> t

append v1 v2 возвращает новый floatarray, содержащий конкатенацию floatarrays v1 и v2.

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

val concat : t list -> t

То же, что и Float.ArrayLabels.append, но конкатенирует список floatarrays.

val sub : t -> pos:int -> len:int -> t

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

Raises Invalid_argument если pos и len не обозначают допустимый подмассив a; то есть, если pos < 0, или len < 0, или pos + len > length a.

val copy : t -> t

copy a возвращает копию a, то есть новый floatarray, содержащий те же элементы, что и a.

val fill : t -> pos:int -> len:int -> float -> unit

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

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

val blit : src:t ->       src_pos:int -> dst:t -> dst_pos:int -> len:int -> unit

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

Raises Invalid_argument если src_pos и len не обозначают допустимый подмассив src, или если dst_pos и len не обозначают допустимый подмассив dst.

val to_list : t -> float list

to_list a возвращает список всех элементов a.

val of_list : float list -> t

of_list l возвращает новый floatarray, содержащий элементы l.

Raises Invalid_argument если длина l больше, чем Sys.max_floatarray_length.

Итераторы

val iter : f:(float -> unit) -> t -> unit

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

val iteri : f:(int -> float -> unit) -> t -> unit

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

val map : f:(float -> float) -> t -> t

map ~f a применяет функцию f ко всем элементам a, и создаёт floatarray с результатами, возвращёнными f.

val map_inplace : f:(float -> float) -> t -> unit

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

Since 5.1

val mapi : f:(int -> float -> float) -> t -> t

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

val mapi_inplace : f:(int -> float -> float) -> t -> unit

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

Since 5.1

val fold_left : f:('acc -> float -> 'acc) -> init:'acc -> t -> 'acc

fold_left ~f x ~init вычисляет f (... (f (f x init.(0)) init.(1)) ...) init.(n-1), где n — длина floatarray init.

val fold_right : f:(float -> 'acc -> 'acc) -> t -> init:'acc -> 'acc

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

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

val iter2 : f:(float -> float -> unit) ->       t -> t -> unit

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

Raises Invalid_argument если floatarrays не одного размера.

val map2 : f:(float -> float -> float) ->       t -> t -> t

map2 ~f a b применяет функцию f ко всем элементам a и b, и создаёт floatarray с результатами, возвращёнными f: [| f a.(0) b.(0); ...; f a.(length a - 1) b.(length b - 1)|].

Raises Invalid_argument если floatarrays не одного размера.

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

val for_all : f:(float -> bool) -> t -> bool

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

val exists : f:(float -> bool) -> t -> bool

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

val mem : float -> set:t -> bool

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

val mem_ieee : float -> set:t -> bool

То же, что и Float.ArrayLabels.mem, но использует IEEE равенство вместо структурного равенства.

Поиск в массивах

val find_opt : f:(float -> bool) -> t -> float option

val find_index : f:(float -> bool) -> t -> int option

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

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

Since 5.1

val find_map : f:(float -> 'a option) -> t -> 'a option

val find_mapi : f:(int -> float -> 'a option) -> t -> 'a option

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

Since 5.1

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

val sort : cmp:(float -> float -> int) -> t -> unit

Сортирует floatarray в порядке возрастания согласно функции сравнения. Функция сравнения должна возвращать 0, если аргументы равны, положительное целое число, если первый больше, и отрицательное целое число, если первый меньше (см. полную спецификацию ниже). Например, compare — подходящая функция сравнения. После вызова sort, массив сортируется на месте в порядке возрастания. sort гарантированно выполняется в постоянном объёме памяти и (в худшем случае) логарифмическом объёме стека.

В текущей реализации используется сортировка кучей. Она выполняется в постоянном объёме стека.

Спецификация функции сравнения: пусть a — floatarray, а 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:(float -> float -> int) -> t -> unit

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

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

val fast_sort : cmp:(float -> float -> int) -> t -> unit

Аналогично Float.ArrayLabels.sort или Float.ArrayLabels.stable_sort, выбирая наиболее быстрый алгоритм для типичных входных данных.

val shuffle : rand:(int -> int) -> t -> unit

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

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

Since 5.2

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

val to_seq : t -> float Seq.t

Итерируется по floatarray в порядке возрастания. Изменения floatarray во время итерации будут отражены в последовательности.

val to_seqi : t -> (int * float) Seq.t

Итерируется по floatarray в порядке возрастания, возвращая индексы и элементы. Изменения floatarray во время итерации будут отражены в последовательности.

val of_seq : float Seq.t -> t

Создаёт массив из генератора.

val map_to_array : f:(float -> 'a) -> t -> 'a array

map_to_array ~f a применяет функцию f ко всем элементам a и строит массив с результатами, возвращёнными f: [| f a.(0); f a.(1); ...; f a.(length a - 1) |].

val map_from_array : f:('a -> float) -> 'a array -> t

map_from_array ~f a применяет функцию f ко всем элементам a и строит floatarray с результатами, возвращёнными f.

Массивы и безопасность при одновременном доступе

При одновременном доступе к float массивам из нескольких областей следует соблюдать осторожность: доступ к массиву никогда не приведёт к аварийному завершению программы, но несинхронизированные обращения могут привести к неожиданным (непоследовательным) результатам.

Атомарность

Каждая операция с float массивом, которая обращается более чем к одному элементу массива, не является атомарной. Сюда относятся итерации, сканирование, сортировка, разделение и объединение массивов.

Например, рассмотрим следующую программу:

let size = 100_000_000
  let a = Float.ArrayLabels.make size 1.
  let update a f () =
     Float.ArrayLabels.iteri ~f:(fun i x -> Float.Array.set a i (f x)) a
  let d1 = Domain.spawn (update a (fun x -> x +. 1.))
  let d2 = Domain.spawn (update a (fun x ->  2. *. x +. 1.))
  let () = Domain.join d1; Domain.join d2

После выполнения этого кода каждый элемент float массива a будет либо 2., либо 3., либо 4., либо 5.. Если требуется атомарность, пользователь должен реализовать собственную синхронизацию (например, используя Mutex.t).

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

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

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

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

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

Разрывы

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

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

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

let zeros = Float.Array.make size 0.
  let max_floats = Float.Array.make size Float.max_float
  let res = Float.Array.copy zeros
  let d1 = Domain.spawn (fun () -> Float.Array.blit zeros 0 res 0 size)
  let d2 = Domain.spawn (fun () -> Float.Array.blit max_floats 0 res 0 size)
  let () = Domain.join d1; Domain.join d2

массив res float может содержать значения, которые не являются ни 0., ни max_float.

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