На этом шаге мы рассмотрим создание и использование массивов.
По технологическим причинам архитектура большинства вычислительных машин строится так, что программные переменные располагают в линейном ("одномерном") порядке. Это имеет далеко идущие последствия, касающиеся распространенных программистских "привычек" [1, с.242-243].
Если Вам понадобилось большое количество переменных для объектов одного и того же типа, то рекомендуется использовать массив, т.е. конечную последовательность индексированных переменных.
В качестве индексов фигурируют, как правило, целые числа. В этом случае для задания диапазона индексов достаточно указать нижнюю и верхнюю границы. Массив может иметь размерность 1,2,... Одномерные массивы, или векторы, образуют важный специальный класс массивов.
Пример 1. Библиотека для работы с массивами. Представление массивов с помощью списков языка LISP.
(DEFUN NTH (LAMBDA (N LST) ; Функция возвращает N-й элемент списка LST ; (COND ( (EQ N 1) (CAR LST) ) ( T (NTH (- N 1) (CDR LST) ) ) ) )) ; --------------------------- ; (DEFUN INSERT (LAMBDA (X N LST) ; Функция вставляет элемент X на N-ю позицию ; ; в список LST ; (COND ( (NULL LST) (CONS X LST) ) ( (EQ N 1) (CONS X LST) ) ( T (CONS (CAR LST) (INSERT X (- N 1) (CDR LST))) ) ) )) ; ------------------------- ; (DEFUN DELETE (LAMBDA (N LST) ; Функция удаляет N-й элемент из списка LST ; (COND ( (EQ N 1) (CDR LST) ) ( T (CONS (CAR LST) (DELETE (- N 1) (CDR LST))) ) ) )) ;Приведем пример использования функций библиотеки: (DEFUN SWAP (LAMBDA (N M LST) ; Обмен значениями N-го и M-го элементов списка LST ; (INSERT (NTH N LST) M (DELETE M (INSERT (NTH M LST) N (DELETE N LST)))) ))
Для тестирования этой библиотеки можно осуществить обмен значениями N-го и M-го элементов списка LST:
$ (SWAP 2 3 '(1 2 3 4 5))
1 3 2 4 5
Пример 2. Реализуем на языке LISP функцию языка программирования APL, называемую перестройка (обозначается @), действие которой разберем на примерах:
1) Команда : 2 3 @ 4 7 8 2 4 6
Результат выполнения:
4 7 8
2 4 6
2) Команда : 4 2 @ 7 8 4
Результат выполнения:
7 8
4 7
8 4
7 8
3) Команда : 3 4 @ 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Результат выполнения:
1 2 3 4
5 6 7 8
9 10 11 12
Числа, стоящие слева от знака операции, определяют структуру результирующей матрицы: число строк и число столбцов. Числа, стоящие справа от знака операции, используются для построения массива, они упорядочиваются по строкам.
Здесь уместно сделать два замечания.
Во-первых, если у Вас недостаточно элементов для того, чтобы построить массив, APL возвращается к началу "кучи" данных, находящихся в правой части, и начинает вновь выбирать из нее элемент за элементом.
Во-вторых, если у нас, напротив, слишком много элементов, то выбирается ровно столько, сколько нужно, остальные игнорируются.
(DEFUN R (LAMBDA (N C LST)
(COND ( (<; (LENGTH LST) (* N C))
(R N C (APPEND LST LST)) )
( T (COND ( (ZEROP N) NIL )
( T (CONS (CARN C LST)
(R (- N 1)
C
(CDRN C LST))))
)
)
)
))
; ----------------------- ;
(DEFUN CARN (LAMBDA (N LST)
(COND ( (ZEROP N) NIL )
( T (CONS (CAR LST)
(CARN (- N 1) (CDR LST))) )
)
))
; ----------------------- ;
(DEFUN CDRN (LAMBDA (N LST)
(COND ( (ZEROP N) LST )
( T (CDRN (- N 1) (CDR LST)) )
)
))
Тестовый пример:
$ (R 2 3 '(4 7 8 2 4 6))
((4 7 8) (2 4 6))
Замечание. Кроме привычных нам массивов с числовыми индексами можно также работать с хэш-массивами.
Хэш-массивы родственны обычному одномерному массиву и ассоциативному списку. Если с помощью обычного массива можно связать объекты языка LISP с целыми числами (индексами), а с помощью ассоциативного списка - с символами, являющимися ключами, то хэш-массив позволяет связать два произвольных объекта языка LISP (атомы, списки, строки и т.д.).
Работа с хэш-массивом напоминает работу с обычным (одномерным) массивом с тем лишь отличием, что в качестве индекса используется указатель на объект языка LISP.
Преимуществом хэш-массивов является быстрота вычислений. Поиск данных, соответствующих ключу, например, в ассоциативном списке, предполагает последовательный просмотр ключей до тех пор, пока искомый ключ не найден. Вместо этого в хэш-массиве место хранения, соответствующее ключу, вычисляется непосредственно по виду ключа с помощью специальной хэш-функции. Однако, если ассоциативные списки малы (содержат для разных версий языка LISP от 4 (!) до 100 элементов), то они могут быть более эффуктивными, чем хэш-массивы, которые требуют значительного времени на инициализацию (Have A Large Initial Overhead).
Таким образом, если Вы используете ассоциативные списки в программе, то замена их на хэш-массивы (Hash Tables) может ускорить выполнение.
О хэш-массивах в языке программирования Perl можно прочитать в 10 шаге.
На следующем шаге мы рассмотрим работу со строками.
