ФЭНДОМ


Определение Править

Массив - тип данных, имеющий сигнатуру $ 'a\ array $, являющийся контейнером и содержащий так называемые mutable-значения, то есть его содержимое можно редактировать "на месте" ("in-place"), не создавая новый экземпляр, как это происходит со списками. Создаются массивы при помощи функции $ [Array.make\colon int \to\ 'a \to\ 'a\ array] $ или её синонима $ [Array.create] $, где первым аргументом является длина массива, а вторым - инициализирующий элемент, которому будут равны все элементы массива после его создания. Доступ к элементу массива осуществляется либо при помощи функции $ [Array.get\colon 'a\ array \to\ int \to\ 'a] $, либо с помощью синтаксиса a.(i), где a - название массива, i - индекс (номер) требуемого элемента. Для записи в массив существует функция $ [Array.set\colon 'a\ array \to\ int \to\ 'a \to\ unit] $, либо синтаксис a.(i) <- x, где x - новое значение для ячейки i массива a.

Главное отличие массивов от списков состоит в том, что списки легко изменяют свой размер, но с трудом индексируются; с массивами же всё наоборот. Для списка операция добавления элемента ( :: ) является базовой и работает за $ O(1) $, но доступ к элементу под номером n происходит за $ O(n) $; в массиве же доступ к элементу является базовой операцией и работает за $ O(1) $, а изменение размера - по крайней мере за $ O(n) $, где n - это новый размер.

Классические массивы - это просто кусок памяти, длина которого - это произведение размера одного элемента массива и количества элементов в нём. В OCaml'е на них ещё навешен счётчик, их длина, с тем чтобы функция $ [Array.length] $ работала за константное время. Есть ещё другая религия, пришедшая из Си, где конец массива помечается специальным маркером, и функция вычисления длины просто шагает вперёд по массиву в его поисках. Как нетрудно заметить, ошибка "Array index out of bounds" там гораздо более непредсказуемая, чем в OCaml'е :)

Дополнительные функцииПравить

Для удобства в модуле Array есть некоторые дополнительные функции для работы с массивами. В первую очередь стоит упомянуть функцию $ [Array.length\colon 'a\ array \to\ int] $, возвращающую длину данного массива. Кроме того, следует отметить функцию $ [Array.init\colon int \to\ (int \to\ 'a) \to\ 'a\ array] $, создающую массив по функции от индекса; например, с её помощью очень легко создать массив-вектор:

 let vect = Array.init 10 (fun i -> i)

Кроме того, есть стандартные функции $ [Array.map\colon ('a \to\ 'b) \to\ 'a\ array \to\ 'b\ array] $ и $ [Array.iter\colon ('a \to\ unit) \to\ 'a\ array \to\ unit] $, обладающие той же функциональностью, что и их аналоги из модуля List. Однако также имеются их продвинутые аналоги: $ [Array.mapi\colon (int \to\ 'a \to\ 'b) \to\ 'a\ array \to\ 'b\ array] $ и $ [Array.iteri\colon (int \to\ 'a \to\ unit) \to\ 'a\ array \to\ unit] $, отличающиеся от своих собратьев тем, что функция, которую они берут в качестве первого параметра, должна быть от двух аргументов: от индекса элемента в массиве и от самого элемента.

Цикл forПравить

При работе с массивами очень удобно использовать циклы. В конце концов, и то, и другое было придумано императивщиками :) Итак, встречайте цикл for:

 for var = low to high do (* code here *) done

Здесь $ var $ - счётчик цикла, $ low $ - начальное значение, $ high $ - конечное. Поясню. Код внутри цикла выполнится $ high - low + 1 $ раз, если $ high \geq low $ и $ 0 $ в противном случае. На каждой итерации для кода внутри цикла будет доступно текущее значение счётчика, равное $ low + i $, где $ i $ - количество уже совершённых итераций. Пример:

 let print_array a =
  for i = 0 to pred (Array.length a) do
   print_endline a.(i)
  done

Итак, количество итераций цикла for всегда должно быть известно в момент его начала. Так бывает часто, но не всегда. И вот как раз для случаев "не всегда" был придуман цикл while.

Цикл whileПравить

 while cond do (* code here *) done

Здесь $ cond $ - это некоторое значение типа bool, которое вычисляется перед каждой итерацией цикла и определяет, будет ли выполнена эта итерация. Пример:

 while true do () done

Эта программа умеет очень классно виснуть :)

Наивный поискПравить

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

 let find x a =
  let len = Array.length a in
  let rec find_aux i =
   if i = len then None else
   if a.(i) = x then Some i else
   find_aux (succ i) in
  find_aux 0

Очевидно, что сей гениальный алгоритм обладает несомненным достоинством - он работает правильно на любом массиве. Впрочем, время его работы сводит на на это потрясающее достоинство: он работает прямо пропорционально длине массива, то есть $ O(n) $. Очевидно, что это не есть хорошо. Нужен был прорыв... и прорыв произошёл.

Двоичный поискПравить

Пусть дан отсортированный массив, причём на его элементах определена операция сравнения. Рассмотрим середину массива и сравним её с искомым элементом. Очевидно, что если она больше, то искомый элемент находится левее её, если меньше - то правее, если они совпали - задача решена, если указатели столкнулись, а элемента нету - ну что ж, жаль. Повторить рекурсивно...

 let qfind x a =
  let rec qfind_aux l r =
   let i = (l + r) / 2 in
   if a.(i) = x then Some i else
   if i = l then None else
   if a.(i) > x then qfind_aux l i else qfind_aux i r in
  qfind_aux 0 (Array.length a)

Понятно, что на каждой итерации алгоритма область поиска сужается вдвое, следовательно, количество операций, которые алгоритму необходимо выполнить - это не более чем то, сколько раз массив можно ещё делить пополам, то есть двоичный логарифм от его длины, поэтому сложность алгоритма - $ O(logn) $.

Кстати, следует заметить, что массив - это функция int -> int, потому что...

Обратная функцияПравить

Двоичный поиск имеет ещё одно, неожиданное, применение: вычисление значения функции, обратной к монотонной. Рассмотрим случай монотонно возрастающей функции; случай монотонно убывающей очевидно вытекает из него. Алгоритм используется почти тот же самый, только поиск производится не по массиву, а по типу float.

 let inverse f x =
  let rec estimate l r =
   let i = (l +. r) /. 2. in
   let fi = f i in
   if (r -. l <= 0.000001) || (fi = x) then i else
   if fi < x then estimate i r else estimate l i in
  estimate 0. x

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