Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 64
Текст из файла (страница 64)
Сечение ЧЕСТОК(2: 10: 2), например, является пятиэлементным массивом, состоящим из второго, четвертого. шестого, восьмого и лесятого элементов матрицы ЧЕСТСЕ. Сечения могут также содержать нерегулярные расположения элементов существующего массива. Например, сечение ЧЕСТОВ ( (/3, 2, 1, 8/) ) является массивом, содержащим третий. второй, первыЯ и восьмой элементы массива ЧЕСТОВ. В языке Аба возможны только крайне ограниченные сечения, состоящие из последовательных элементов одномерного массива.
Например, если ЕТЯТ вЂ” массив с диапазоном значений (1 .. 100) . то 11ЯТ (5 .. 10) является сечением массива Ь|ЯТ, состоящим из шести элементов, имеющих индексы от 5 до 10. Как указывалось в разделе 5.3.2, сечение переменной типа ЯТК1ИЯ называется ссылкой на подстроку. 5.5.
Массивы мат(г 3,13( МАТ (!.3. 2) СОВЕ (1.3, 1.3. 2 31 СОВЕ (2, 1.'3. 1Л( Рис. 5 4. Прииеры сечений в языке ГОНТАМ 90 5.5.8. Оценка Массивы есть практически во всех языках программирования. Они просты и хорошо разработаны. Единственными сушественными усовершенствованиями, сделанными со времени их появления в языке РОКТКАМ (, было включение всех порядковых типов в число возможных типов инлексов и, разумеется, введение динамических массивов.
Несмотря на необходимость и фундаментальность массивов, их структура все же вызывает некоторые разногласия. Иногда бывает удобно разрешать программисту задавать отдельные подструктуры многомерных массивов, но платой за это удобство может оказаться повышенная сложность реализации и ухулшение читабельности. 5.5.9. Реализация тинов массивов Реализация массивов требует больших затрат во время компиляции, чем реализация таких простых типов, как типы целых чисел.
Команды. позволяюшие доступ к элементам массива, должны формироваться во время комп(ьзяции. Во время выполнения программы эти команды должны вычислять адреса элементов массива. Если команды доступа разработаны плохо, то поступ к элементам массива, особенно в массивах с несколькими индексами, становится неэффективным. Это справедливо независимо от того, каким именно обра- Глава 5. (нпы данных 236 юи массив связывается с памятью: статически или динамически. Нельзя предварительно вычислить адрес, доступ к которому осушествляется с помошью обращения список[)г) Одномерный массив представляет собой список последовательных ячеек памяти.
))редположим. что нижняя граница диапазона индексов массива 1 ' вс равна 1. Ф) нкция пестуна лля массива 11як часто имеет висл адрес (список [й) ) = адрес (список '1) ) - ! х-1) размер злеь:ента : ) оследнее упрошается до виза адрес(список[)г]) = (адрес(список,[ )'; — размер элемента', (К * размео зпемеига)' плесь первый операнд операции сложения является постоянной частью функции доступа. в горой — переменной. Если тип элемента связывается статически. а массив. в свою очередь. статически свя.,вается с памятью. то значение постоянной части можно вычислить до начала выпол.
няя программы. Во время выполнения останется произвести операции сложения и ум- жения. Если базовый, или начальный. алрес массива не известен до начала выполне, я программы, то при размешении массива в памяти должна выполняться еше и -ерация вычитания.
Обобшением этой функции доступа на случай произвольной нижней границы будет . езуюшая функция: -.прес(список[)г)) = адрес(список'нижняя гранина,') (й -нижняя гоани. а! * размер зпемеиса Динамический дескриптор одномерного массива всегда можно -;зставить в виде, показанном на рис. 5.5. Дескриптор содержит - эормацию, необходимую для создания функции доступа. Если во .:чя выполнения программы проверка выхода индекса за пределы пазона не проводится и все атрибуты являются статическими, то время выполнения сам дескриптор не нужен, требуется только чкция доступа.
При проверке выхода индекса за прелелы лиапаг з во время выполнения программы может потребоваться хранить зчяти эти диапазоны значений индексов в динамическом дескгоре. Если диапазоны значений индексов отлельного типа мас-з являются статическими. то диапазоны могут включаться в ко- выполняюшие проверку, что устраняет потребность в динами- Рис. 5.5.Дяяаикчес.-1м дескрипторе. Если какая-либо из позиций лескриптора «ийдесярнллгпрод.
мвается динамически, то эти части деслриптора должны сохра- номерных.насснвов ;я во время выполнения программы. х)иогомерные массивы реализовать значительно труднее, чем одномерные. хотя рас-.ние на большее число измерений выполняется достаточно просто. Аппаратная па- лпнейна — обычно это последовательности байтов.
Таким образом. значения типов :мх. имеющих несколько измерений. дояжны отображаться в одномерную память. .:ствует два способа отображения многомерных массивов в одно измерение; запись . -рокам и запись по столбцам. При записи по строкам (гоп гпазог огдег) вначале за- чэются элементы массива. имеюшие в качестве первого индекса значение нижней Массивы 237 границы этого индекса, за ними следуют элементы второго значения первого индекса и так далее. Если массив является матрицей, он запоминается построчно.
Например, пусть матрица имеет значения: 3 4 7 б 2 5 138 Тогда при использовании записи по строкам она будет храниться в памяти следуюшим образом: 3, 4, 7, б, 2, 5, 1, 3, 8 При записи по столбцам (со!цшп та]ог огг(ег) вначале запоминаются элементы массива, имеюшие в качестве последнего индекса значение нижней границы этого индекса, за ними еле)пзот элементы второго значения последнего индекса и так далее. Если массив является двумерной матрицеЯ, то он запоминается по столбцам. Если привеленную выше матрицу записать по столбцам, то в память оиа будет занесена в виде следуюшей строки: 3, б, 1, 4, 2, 3, 7, 5, 8 Запись по столбцам используется в языке ЕОКТКА)4, а в остальных языках используется запись по строкам. Иногда следует знать порядок запоминания многомерных массивов; например, когда такие массивы обрабатываются с помощью указателей в программах на языке С, или когда массивы в программах на языке РОКТКАХ ставятся в соответствие массивам другого вида оператором е()()1чдье)(се.
Вообще такая информация важна во всех языках. разработчики которых серьезно заинтересованы в скорости выполнения программ, и в компьютерах, использующих виртуальную память (практически все машины, не являюшиеся персональными компьютерами, используют виртуальную память). Последовательный доступ к элементам матриц будет осушествляться быстрее, если производить его в том порядке, в котором хранятся эти элементы, поскольку такой доступ минимизирует замешение страниц. (Замещение страниц — процесс перемещения блоков информации между диском и оперативной памятью.) Функция доступа к элементам многомерного массива представляет собой отображение его базового адреса и множества значениЯ индексов в адреса элементов, заданных значениями индексов.
Ниже приводится изображение функции лоступа лля двумерного массива, записанного в память по строкам. Вообще, адрес элемента — это базовый адрес структуры плюс размер элемента, умноженный на число элементов структуры, предшествуюших данному. Для матрицы, записанной в память по строкам, число предшествуюших элементов равно количеству строк, находяшихся выше, умноженному на размер строки в элементах, плюс число элементов, находяшихся слева от данного.
Сказанное иллюстрирует рис. 5.6, в котором лля простоты все нижние границы считались равными 1. Для того чтобы получить фактическое значение адреса, число элементов массива, предшествуюших данному, следует умножить на размер элемента. Теперь функцию доступа можно записать так: адрес(а(1, 3] ) = адрес(а(1, 1] ) ((((число строк, находящихся над (-той строкой) * (размер строки)) + (число элементов, находящихся слева от /-того столбца)) * размер элемента) 236 Глава б. Типы данных Рис.
5.б. Расположение элечента (1, Я в матрице Поскольку число строк. находящихся над 1-той строкой, равно (1-1] и число элемен- тов слева от З-того столбца равно ( З -1 ), то получаем: адрес(а[1, З] ) = адрес(а[1, 1] ) ( ( ( (1 - 1) * и) + (З - 1) ) * размер элемента) Злесь и — число элементов в строке. Последнее выражение можно преобразовать в вид: адрес(а[1, 7] ) = адрес (а [1, 1] ) ((и + 1) * размер элемента) (1 * и + З) * размер элемента) Здесь первые два члена — постоянная часть, а последний — переменная. Обобщим функцию доступа на случай произвольных нижних ~рапид: адрес (а[1, З]) = адрес (а[гр стр, гр стлб]] + ((((1 — гр стр) * и) (3 — гр стлб)) * размер элемента] Здесь гр стр — нижняя граница строк, гр стлб — нижняя граница столбцов. По- следнее выражение можно преобразовать так: адрес(а [1, 7] ] = адрес (а[гр стр, гр стлб] ) (((гр стр + й) + гр стлб) * размер элемента)+ (((1 " и + З) * размер элемента) Злесь первые два члена — постоянная часть, а последний — переменная.
Последнее выражение относительно просто обобщается на произвольное число измерений. Для каждого измерения массива функции доступа требуется выполнить одну команду умножения и одну сложения. Следовательно, обращения к элементам массива, имеющего несколько индексов, являются неэффективными. Вид статического дескриптора многомерного массива показан на рис. 5.7. 239 5.5.
Массивы Рнс. 5.7. Стилгический дескриптор ниого- териого ииссиеи Еше одни уровень сложности функции отображения памяти создается сечениями. Для того чтобы пояснить это, рассмотрим программу, в которой есть матрица и массив, причем столбец матрицы присваивается массиву: 1НТЕЕЕК МАТ (1:10, 1:5], ЫЯТ (1:10) Е1ЯТ = МАТ (1 З, З) Функция отображения памяти для матрицы МАТ выглядит следуюшим образом ( предполагается использование записи в память по строкам и единичный размер элемента) адрес (МАТ(', 3]) .= адрес (МАТ[1, 1)) ((1 — 1) * 5 л (3 -1)) * 1 — (адрес (МАТ(1, 1]) — 6)] ((5 * 1) е 3) Функция отображения памяти для обрашения к сечению МАТ[ 1: 3, 3) выглядит следуюшим образом: адрес (МАТ[1, 3]) - адрес (МАТ[1, 1]) + ((1 — 1) " 5 е (3 -1)) * 1 (адрес (МАТ[1, 1]) — 3) +(5 * 1) О|метим. что это отображение имеет в точности ту же форму, что и любая другая функция доступа к одномернолгу массиву, хозя форма постоянной части несколько отличается из-за того, что массив, составляюший основу сечения, является двумерным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
