Модуль Float.ArrayLabels

module ArrayLabels: sig .. end

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

type t = floatarray

Тип «плоских» массивов чисел с плавающей точкой.

floatarray — это структура данных массива, содержащая фиксированное количество элементов типа float. Гарантируется, что элементы floatarray хранятся в памяти непрерывно, без какого-либо боксинга (упаковки).

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

Литералы массивов типа floatarray могут быть записаны с использованием того же синтаксиса, что и литералы типа float array, если в окружении достаточно информации о типах, чтобы компилятор мог устранить неоднозначность между этими двумя случаями. Дополнительные сведения см. в разделе 12.25 «Type-directed disambiguation of array literals» руководства.

Начиная с 4.08

val length : t -> int

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

val get : t -> int -> float

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

Вызывает Invalid_argument, если n выходит за пределы диапазона от 0 до (length a - 1).

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

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

Вызывает Invalid_argument, если n выходит за пределы диапазона от 0 до (length a - 1).

val make : int -> float -> t

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

Вызывает Invalid_argument, если n < 0 или n > Sys.max_floatarray_length.

val create : int -> t

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

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

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

Начиная с 5.2
Вызывает 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.

Начиная с 5.2
Вызывает Invalid_argument, если dimx или dimy отрицательно либо больше Sys.max_floatarray_length.

val append : t -> t -> t

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

Вызывает Invalid_argument, если length v1 + length v2 > Sys.max_floatarray_length.

val concat : t list -> t

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

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

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

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

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

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

Вызывает Invalid_argument, если длина l больше, чем Sys.max_floatarray_length.

Сравнение

val equal : eq:(float -> float -> bool) ->       t -> t -> bool

equal ~eq a b возвращает true тогда и только тогда, когда a и b имеют одинаковую длину n и для всех i в [0;n-1] значение eq a.(i) b.(i) равно true.

Начиная с 5.4

val compare : cmp:(float -> float -> int) ->       t -> t -> int

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

Начиная с 5.4

Итераторы

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

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

Начиная с 5.1

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

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

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

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

Вызывает Invalid_argument, если массивы floatarray имеют разный размер.

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

Вызывает Invalid_argument, если массивы floatarray имеют разный размер.

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

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 возвращает true тогда и только тогда, когда в 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, если такого элемента нет.

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

Начиная с 5.1

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

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

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

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

Текущая реализация использует сортировку слиянием (Merge 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 (не забудьте инициализировать генератор).

Начиная с 5.2

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

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.

Массивы и потокобезопасность

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

Атомарность

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

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

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

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

Гонки данных

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

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

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

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

Расщепление (tearing)

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

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

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

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