ближайшего большего целого числа дая компонента массива занимает

s]. В этом случае каж. s] слов, причем часть

слова величиной [s] - s остается неиспользованной (см,

память

- абстрактный массив -

Рис. 1.5. Отображение массива в память.

рис. 1.5 и 1.6). Округление числа занимаемых слов до ближайшего целого называется выравниванием. Отношение размера памяти, которая отводится для описания структуры

5 = 2.3

i fsi=3

неиспользуемая память

Рис. 1.6. Представление записи с выравниванием.

данных, к размеру действительно занятой памяти называется коэффициентом использования памяти:

(1.33)

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

1. Выравнивание понижает коэффициент использования памяти.

2. Отказ от выравнивания может привести к неэффективному обращению к частям слова.

выравнивание

Рис. 1.7. Упаковка шести компонент в одно слово.

коэффициент можно значительно увеличить, помещая в каждое слово более одной компоненты массива. Этот прием называется упаковкой. Если в слово упаковано п компонент, то коэффициент использования памяти равен (см. рис. 1.7)

-J- (1-34)

Доступ к i-й компоненте упакованного массива требует вычисления / - адреса слова, в котором расположена эта компонента, а также k - относительного адреса расположения компоненты внутри слова:

/ = i div п

== I mod п = I - / * п

Большинство языков программирования не дает програм-тсту возможности управлять реализацией абстрактных структур данных. Однако полезно иметь возможность указывать желательность упаковки хотя бы в тех случаях, когда в одно слово можно поместить более одной компог ненты, поскольку при этом достигается экономия памяти в 2 и более раз. Мы вводим соглашение, что желательность упаковки будет обозначаться словом packed перед словом array (или record).

Пример:

type al\a = packed array[l. ./г] of char

Эта особенность наиболее Ценна для вычислительных машин с Длинными словами и сравнительно удобным доступом к отдельным частям слов. Важное свойство этого префикса состоит в том, что он не изменяет значение и правильность программы. Это означает, что можно выбирать любое из Альтернативных представлений с уверенностью, что это не повлияет на смысл программы.

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

о действительности положения 2 и 3 обычно более важны, л трансляторы всегда автоматически применяют выравнивание. Заметим, что при s > 0.5 коэффициент использования памяти всегда будет и > 0.5. Однако, если s 0.5, этот

48 1. Фундаментальные структуры аанных

- --

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

и:аггау[а. .d]of Г

р: packed array[fc.. с] of Г

где а b с d - одного и того же скалярного типа. Тогда

-pack {и, i, р) (а -СЬСЬ--М) (1.-36)

эквивалентно

Pli]-ulj + i-b], i=-b..c

а

unpack{р, и, i) (aib - c + d) (1.37)

эквивалентно

u[j + {-b]:==plJ], j = b..c

1.10.2. Представление записей

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

i = S, + S2+ ... +S£ (1.38)

где Sj - размер в словах /-й компоненты. Поскольку у массива все компоненты одного типа, то

= S2 = ... = s

и, следовательно,

/= S,-f S2 + + Sj-i = (t - 1) - S.

Универсальность записи не позволяет вычислять относительные адреса ее компонент с помощью такой же простой линейной функции, поэтому очень полезно ограничить доступ к ее компонентам и пользоваться лишь фиксированными идентификаторами. Это ограничение позволяет узнать относительные адреса во время трансляции, что намного увеличивает эффективность доступа к полям записи.