Программирование на Athanor – 14 (массивы и операции над ними)

Массивы: их создание и основные операции над ними

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

Массивы в языке Athanor – многомерные: они могут иметь до 16 измерений! Количество измерений в массиве называется его размерностью. Одномерные массивы удобны для представления линейных последовательностей значений (например, векторов). Двухмерные массивы удобны для реализации матриц, состоящих из строк и столбцов. Трёхмерные массивы – добавляют к плоским матрицам ещё одно измерение (глубину), т.к. состоят из строк, столбцов и слоёв (иногда называемых также "страницами"). Для четырёхмерных, пятимерных и ещё более многомерных массивов – устоявшихся специальных названий для измерений даже не придумано (но всё равно можно их создавать и с ними работать).

Разумеется, поскольку списки могут иметь неограниченную вложенность – с их помощью тоже нетрудно реализовать массив с произвольной размерностью. Однако (как уже сказано выше) массивы обычно лучше списков: они обеспечивают более быстрый доступ к своим элементам, и занимают заметно меньше памяти. К недостаткам массивов относится то, что при их создании – необходимо явно указать все его измерения (и, после его создания, их не так просто изменить).

Создание массива выполняется специальным встроенным функтором array – конструктором массива:

Список измерений для создаваемого массива должен быть непустым (если конструктору array передать пустой список – он просто возвращает ()). Все измерения должны быть целыми (допустим любой скаляр, но он неявно приводится к целому). Размерность создаваемого массива – равна количеству аргументов в конструкторе. Вызов array (Length) – создаёт одномерный массив (вектор) с длиной Length. Вызов array (Height, Width) – создаёт двухмерную матрицу с высотой (количеством строк) Height и шириной (количеством столбцов) Width. Вызов array (Depth, Height, Width) – создаёт трёхмерный массив с глубиной (количеством слоёв) Depth, высотой Height и шириной Width. Ну, и так далее. Если измерений больше одного, то самое первое измерение в списке всегда является самым внешним, а самое последнее – самым внутренним. Размер массива по любому измерению может быть произвольным (но до тех пор, пока хватает памяти). Он может быть равен 1, и даже 0 (хотя, если хотя бы одно измерение равно 0 – то массив не содержит элементов вообще). Для array есть альтернатива: a_create.

Все элементы созданного массива равны (), т.е. они пусты. Как и с любым контейнером данным – с массивом можно работать как целиком, так и поэлементно. Последнюю возможность обеспечивает встроенный функтор a_elem:

Эта операция является аксессором, так как обеспечивает прямой доступ (мутабельный) к произвольному элементу массива Array. Если массив имеет размерность N, то в списке индексов должно быть N элементов (если массив одномерный, то вместо списка требуется единственный скаляр). Не только число, но и порядок индексов в списке – соответствует порядку размеров массива в конструкторе array при его вызове (самый первый индекс в списке – является самым "внешним", а последний – самым "внутренним"). Как и для списков, отсчёт индексов (по всем измерениям) начинается с 0. Поэтому допустимыми значениями для индекса по измерению M – являются целые числа от 0 до (DimM - 1) включительно (где DimM – размер массива по данному измерению). Если какой-нибудь индекс выходит за пределы диапазона – такого элемента не существует, и операция a_elem молча возвращает (). А вот если попытаться изменить несуществующий элемент массива (например, присвоить ему любое значение) – интерпретатор всё-таки выдаст сообщение об ошибке (так как изменить несуществующее мутабельное нельзя).

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

Таким образом, вызов a_elem может вернуть значение () в двух случаях: или когда элемент массива не существует, или когда он существует, но ему ещё ничего не присвоено. Чтобы не путаться, желательно точно знать размер(ы) массива:

Все измерения массива возвращаются в виде списка (для одномерного массива – результатом будет просто скаляр) в том же порядке, в каком они были в конструкторе array. Как и там, самое первое измерение в списке – является самым внешним, самое последнее – самым внутренним, а общее число элементов списка равно размерности массива. Впрочем, для размерности есть и специальная операция:

Ещё одна операция возвращает общее число элементов в массиве:

Это число всегда равно произведению всех размеров массива (для одномерного массива – просто равно его длине).

С помощью a_elem можно присвоить всем элементам массива произвольные значения. Однако, довольно часто (особенно, при инициализации массива) требуется присвоить всем элементам какое-то одно значение. Это удобнее делать следующим образом:

Это – быстрый способ присвоить всем элементам массива какое-то одно (чаще всего, скалярное) значение. Например, a_fill (Array, 0) – присваивает всем элементам Array ноль (целочисленный), а a_fill (Array, "") – присваивает им всем пустую строку.

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

Также как и для a_fill, здесь происходит заполнение массива значениями. Однако, они (обычно) уже не одинаковые, так как вычисляются динамически, и независимо для кажого из элементов. Для каждого элемента массива – вызывается функциональная ссылка FuncRef, которой передаётся список индексов для данного элемента (только один индекс, если массив одномерный). Результат, который возвращает вызов FuncRef, и становится значением элемента. Порядок индексов в вызове – тот же, что и в a_elem. Всё это проще продемонстрировать на примерах:

• MulTab = array (10, 10); a_init_all (MulTab, !(I J) = ((I+1) * (J+1)));

Квадратная матрица MulTab инициализируется как таблица умножения: так как нам не интересны нулевые элементы, на пересечении строки I и столбца J мы ставим (I+1) * (J+1).

• Ident = array (N, N); a_init_all (Ident, !(I J) = (I == J));

Делает квадратную матрицу Ident "единичной": присваивает 1 всем элементам на её главной диагонали, и 0 – всем прочим элементам (это именно то значение, которое возвращает (I == J)).

• Factorials = array (M); a_init_all (Factorials, !(n) = (factorial (n)));

Присваивает всем элементам одномерного вектора Factorials последовательные значения факториалов, от 0! до (M-1)!

(Саму реализацию функции factorial мы здесь не приводим – но в статье 8 уже было несколько готовых решений, берите любое.)

Разумеется, и:

• a_fill (Array, Value);

тоже можно заменить на:

• a_init_all (Array, ! () = Value);

– но первый вариант и проще, и быстрее.

Как и для (практически) любой структуры данных в языке, для массивов определён собственный итератор:

Итератор a_loop работает так же, как и все прочие итераторы языка: выполняет свой последний аргумент (Loop) многократно, предварительно присваивая ссылку на каждый элемент переменной (в общем случае – любому мутабельному выражению) Var. (Таким образом, итератор выполняется ровно a_total (Array) раз.) Порядок элементов определяется вложенными циклами по каждому измерению: самый внутренний цикл выполняется по самому внутреннему измерению, а самый внешний – по самому внешнему. Например, для одномерного вектора особых вариантов нет: выполняется единственный цикл, от первого элемента до последнего. Для двухмерной матрицы – выполняется два вложенных цикла: внутренний по столбцам матрицы, и внешний по строкам. Для трёхмерного массива – выполняется три вложенных цикла: внутренний по столбцам матрицы, средний по её строкам, и внешний по её слоям (или страницам). Думаю, идея понятна и для более высоких размерностей. Как и прочие итераторы, a_loop также возвращает значение: это результат выполнения Loop для самого последнего элемента массива Array. Обычно, это значение игнорируется, но и его можно использовать в вычислениях.

Для массивов также определёна возможность их вывода в поток. Если вывести массив в любой выходной поток – туда последовательно выводятся все его элементы (порядок вывода тот же, что и в итераторе a_loop). Другими словами, выполнение:

• out_stream <: Array

всегда эквивалентно выполнению:

• a_loop (Array, Element, out_stream <: Element)

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

Список элементов должен быть строго линейным (т.е. структура массива Array на нём никак не отражается!), элементов в нём обычно a_total (Array), и упорядочиваются они точно так же, как и в a_loop. Впрочем, элементов в списке может быть и меньше: тогда те (последние по порядку) элементы, которым не хватило значений, просто останутся не присвоенными. Разумеется, предусмотрена и обратная операция:

Как и для a_load, список-результат не имеет никакой вложенности (элементы выгружаются последовательно), порядок выгрузки – точно соответствует порядку a_load и a_loop, и в списке (как правило) a_total (Array) элементов. Впрочем, их может быть и меньше: по соглашению, самые последние (и только последние!) элементы, равные (), в этот список не включаются. Поэтому, если массив совершенно пуст (все его элементы равны ()) – то и результатом a_save также будет ()!

Правда, a_save не сохраняет никакой информации о структуре массива, но зато это делает a_dims. То есть, если нужно сделать NewArray точной копией OldArray, этого можно добиться так:

• NewArray = array (a_dims (OldArray));
  a_load (NewArray, a_save (OldArray));

Созданный так NewArray совпадает с OldArray полностью: как по размерам, так и по содержимому. (Результатом OldArray [==] NewArray – будет 1. Да, сравнения на идентичность/неидентичность – для массивов тоже работают.)

Вот другой пример: создадим трёхмерную матрицу поворота. Эта матрица – описывает преобразование декартовых координат через три эйлеровых угла: угол прецессии (alpha), угол нутации (beta) и угол вращения (gamma). Естественно, все три угла должны быть в радианах – и в этом случае:

		Rotation = a_create (3, 3);

		a_load (Rotation,
			` -- первая строка: `
			cos(alpha) * cos(gamma) - sin(alpha) * cos(beta) * sin(gamma),
			- cos(alpha) * sin(gamma) - sin(alpha) * cos(beta) * cos(gamma),
			sin(alpha) * sin(beta),

			` -- вторая строка: `
			sin(alpha) * cos(gamma) + cos(alpha) * cos(beta) * sin(gamma),
			- sin(alpha) * sin(gamma) + cos(alpha) * cos(beta) * cos(gamma),
			- cos(alpha) * sin(beta),

			` -- третья строка: `
			sin(beta) * sin(gamma),
			sin(beta) * cos(gamma),
			cos(beta)
			);

(В более реальном примере лучше сперва вычислить все синусы и косинусы: так будет быстрее.)

Массивы принципиально не смешиваются с другими данными – например, скалярными. Если в списковых операциях обычно допустимо использование скалярных операндов (т.к. они неявно векторизуются), то операндом в операциях над массивом – всегда должен быть массив! Обычно, если вместо массива передаётся что-то другое – то эти операции выдают ошибку (и ничего больше не делают). Но в языке есть предикат, позволяющий проверить результат любого выражения на "массивность":

Для любых других данных, отличных от массивов – вызов is_array возвращает 0.

Перейдём от теоретической части к практической: покажем, как используя массивы реализовать немного вполне полезной матричной алгебры. Для начала, определим простые средства для создания матриц:

` Создать матрицу [Rows * Cols] и заполнить её списком Elements `
! MatCreate (Rows Cols Elements) : [Matrix] = 
	if (Rows * Cols == #Elements):: {
		Matrix = array (Rows, Cols);

		a_load (Matrix, Elements);

		Matrix } ::
		(<: "Неправильное число элементов!");

Вызов MatCreate совмещает в себе создание матрицы (array), и её инициализацию списокм элементов (a_load). Кроме того, в отличие от встроенного a_load – здесь также проверяется длина списка элементов.

` Вывести (в стандартный вывод) матрицу Matrix: `
! MatPrint (Matrix) : [i j M N] = {
	[M N] = a_dims (Matrix);

	<: ("[", M, " * ", N, "] = \n");

	for_inc (i, M, {
		<: "[\t";
		for_inc (j, N,
			<: (Matrix {i,j}, "\t")
			);
		<: "]\n";
		});

	<: "\n";
	};	` -- MatPrint `

Вызов MatPrint выводит матрицу-операнд аккуратно, и в намного более наглядном виде, чем по умолчанию. Например:

:( TestA = MatCreate (2, 2, [21 49 15 72]) );
:( TestB = MatCreate (3, 3, [11 66 99 22 55 77 44 88 33]) );

MatPrint (TestA);
MatPrint (TestB);

выводит:

[2 * 2] = 
[	21	49	]
[	15	72	]

[3 * 3] = 
[	11	66	99	]
[	22	55	77	]
[	44	88	33	]

Функтор MatTranspose транспонирует матрицу-операнд, возвращая результат:

` Транспонирует матрицу Mat (возвращает результат): `
! MatTranspose (Mat) : [TMat M N i j] = {
	[M N] = a_dims (Mat);

	TMat = array (N, M);

	for_inc (i, M,
		for_inc (j, N,
			TMat {j,i} = Mat {i,j})
			);

	TMat };		` -- MatTranspose `

Вычисление произведения двух матриц тоже вполне тривиально:

` Возвращается матричное произведение (MatA * MatB): `
! MatProduct (MatA MatB) : [MatC i j k L L1 M N sum] = {
	[M L] = a_dims (MatA);
	[L1 N] = a_dims (MatB);

	if (L == L1):: {
		MatC = array (M, N);

		for_inc (i, M,
			for_inc (j, N, {
				sum = 0;

				for_inc (k, L,
					sum =+: MatA {i,k} * MatB {k,j});

				MatC {i,j} = sum;
				})
			);
		} :: (<: "Размеры матриц не совпадают!");

	MatC };		` -- MatProduct `

В завершение, реализуем самую нетривиальную операцию из всех – вычисление определителя матрицы:

` Возвращается определитель Matrix: `
! MatDeterm (Matrix) : [M N Row_Filter] = {
	[M N] = a_dims (Matrix);

	if (M == N):: {
	Row_Filter = array (N);
	a_fill (Row_Filter, 1);

	! calc_minor (Column) : [Value Row Sign] =
	(Column <> N) ? {
		Sign = 1;
		Value = 0;

		for_inc (Row, N,
			if (Row_Filter {Row}):: {
				-- Row_Filter {Row};
				Value =+: Sign * Matrix {Row,Column} * calc_minor (Column + 1);
				++ Row_Filter {Row};
				Sign =*: -1;
				});

			Value }
		: 1;

	` result is: `
	calc_minor (0) }
	:: { <: "Матрица не квадратная!"; () }
	};	` -- MatDeterm `

Наверное, здесь уже нужны комментарии. Первым делом, мы проверяем, является ли матрица строго квадратной (если число её строк и столбцов не совпадает, мы сообщаем об ошибке). Сами вычисления выполняются рекурсивно: практически всю реальную вычислительную работу выполняет внутренний функтор calc_minor, который рекурсивно вызывает сам себя для всех миноров меньше размером. Сам определитель вычисляется как знакопеременная сумма этих миноров. В каждом миноре матрицы столбцы идут подряд (от Column до N), но вот строки "разрежены", и мы отслеживаем их состояние с помощью внутреннего вектора Row_Filter, каждый элемент которого соответствует строке матрицы (если он равен 1, то строка включается в минор, а если 0, то пропускается). Нетрудно убедиться, что на каждом уровне рекурсии число строк в миноре будет равно числу столбцов, как и должно быть. Сам код в MatDeterm практически тривиален: мы устанавливаем весь Row_Filter в 1, и сразу вызываем calc_minor для столбца 0 (т.е., для всей матрицы в целом). Его результат и будет результатом всего вызова (т.е. самим определителем).

Заметим также, что здесь мы впервые имеем дело с вложенными определениями функторов. Определение calc_minor является внутренним для MatDeterm (но имеет возможность работать с локальным контекстом последнего, таким, как переменные Matrix или Row_Filter).

Можно убедиться, что этот функтор работает правильно:

:( TestC = MatCreate (4, 4, (-5, 1, -4, 1, 1, 4, -1, 5, -4, 1, -8, -1, 3, 2, 6, 2)) );

MatPrint (TestC);

<: ("Determ (TestC) = ", MatDeterm (TestC), "\n");

И, в результате, получим правильный ответ:

[4 * 4] = 
[	-5	1	-4	1	]
[	1	4	-1	5	]
[	-4	1	-8	-1	]
[	3	2	6	2	]

Determ (TestC) = -264

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