1.6. Представление массивов,
записей и множеств
Смысл использования абстракций в программировании – в том, чтобы обеспе%
чить возможность спроектировать, понять и верифицировать программу, исходя только из свойств абстракций, то есть не зная о том, как абстракции реализованы и представлены на конкретной машине. Тем не менее профессиональному программисту нужно понимать широко применяемые способы представления фундаментальных структур данных. Это может помочь принять разумные реше%
Представление массивов, записей и множеств
Фундаментальные структуры данных
32
ния о построении программы и данных в свете не только абстрактных свойств структур, но и их реализации на конкретной машине с учетом ее специфических особенностей и ограничений.
Проблема представления данных заключается в том, как отобразить абстракт%
ную структуру на память компьютера. Память компьютера – это, грубо говоря,
массив отдельных ячеек, которые называются
байтами. Они интерпретируются как группы из 8 бит каждая. Индексы байтов называются
адресами.
VAR store: ARRAY StoreSize OF BYTE
Примитивные типы представляются небольшим числом байтов, обычно 1, 2, 4
или 8. Компьютеры проектируются так, чтобы пересылать небольшие группы смежных байтов одновременно, или, как говорят, параллельно. Единицу одновре%
менной пересылки называют
словом.
1.6.1. Представление массивовПредставление массива – это отображение (абстрактного) массива, компоненты ко%
торого имеют тип
T
, на память компьютера, которая сама есть массив компонент типа
BYTE
. Массив должен быть отображен на память таким образом, чтобы вычисление адресов его компонент было как можно более простым (и поэтому эффективным).
Адрес i
для j
%й компоненты массива вычисляется с помощью линейной функции i = i
0
+ j*s,
где i
0
– адрес первой компоненты, а s
– количество слов, которые занимает одна компонента. Принимая, что слово является наименьшей единицей пересылки содержимого памяти, весьма желательно, чтобы s
было целым числом, в простей%
шем случае s = 1
. Если s
не является целым (а это довольно обычная ситуация), то s
обычно округляется вверх до ближайшего большего целого
S
. Тогда каждая ком%
понента массива занимает
S
слов, тогда как
S–s слов остаются неиспользованными
(см. рис. 1.4 и 1.5). Округление необходимого числа слов вверх до ближайшего це%
лого называется
выравниванием (padding). Эффективность использования памя%
ти u
определяется как отношение минимального объема памяти, нужного для
Рис. 1.4. Отображение массива на память компьютера
33
представления структуры, к реально использованному объему:
u = s /
(
s
, округленное вверх до ближайшего целого).
Поскольку проектировщик компилятора должен стремиться к тому, чтобы эффективность использования памяти была как можно ближе к 1, но при этом доступ к частям слова громоздок и относительно неэффективен, приходится идти на компромисс. При этом учитываются следующие соображения:
1. Выравнивание уменьшает эффективность использования памяти.
2. Отказ от выравнивания может повлечь необходимость выполнять неэф%
фективный доступ к частям слова.
3. Доступ к частям слова может вызвать разбухание скомпилированного кода и тем самым уменьшить выигрыш, полученный из%за отказа от выравнивания.
На самом деле соображения 2 и 3 обычно настолько существенны, что компи%
ляторы автоматически используют выравнивание. Заметим, что эффективность использования памяти всегда u > 0.5
, если s > 0.5
. Если же s
≤
0.5
, то эффек%
тивность использования памяти можно сильно увеличить, размещая более одной компоненты массива в каждом слове. Это называется упаковкой (packing). Если в одном слове упакованы n
компонент, то эффективность использования памяти равна (см. рис. 1.6)
u = n*s /
(
n*s
, округленное вверх до ближайшего целого).
Рис. 1.5. Представление записи с выравниванием
Рис. 1.6. Упаковка шести компонент в одном слове
Доступ к i
%й компоненте упакованного массива подразумевает вычисление ад%
реса слова j
, в котором находится нужная компонента, а также позиции k
%ой ком%
поненты внутри слова:
j = i DIV n k = i MOD n
В большинстве языков программирования программист не имеет возможно%
сти управлять представлением структур данных. Однако должна быть возмож%
ность указывать желательность упаковки хотя бы в тех случаях, когда в одно сло%
во помещается больше одной компоненты, то есть когда может быть достигнут
Представление массивов, записей и множеств
Фундаментальные структуры данных
34
выигрыш в экономии памяти в два раза и более. Можно предложить указывать желательность упаковки с помощью символа
PACKED
, который ставится перед символом
ARRAY
(или
RECORD
) в соответствующем объявлении.
1.6.2. Представление записей
Записи отображаются на память компьютера простым расположением подряд их компонент. Адрес компоненты (поля) r
i относительно адреса начала записи r
на%
зывается смещением (offset) поля k
i
. Оно вычисляется следующим образом:
k i
= s
1
+ s
2
+ ... + s i–1
k
0
= 0
где s j
– размер (в словах) j
%й компоненты. Здесь видно, что равенство типов всех компонент массива имеет приятным следствием, что k
i
= i
×
s
. К несчастью, общ%
ность записевой структуры не позволяет использовать простую линейную функ%
цию для вычисления смещения компоненты; именно поэтому требуют, чтобы компоненты записи выбирались с помощью фиксированных идентификаторов.
У этого ограничения есть то преимущество, что смещения полей определяются во время компиляции. В результате доступ к полям записи более эффективен.
Упаковка может привести к выигрышу, если несколько компонент записи мо%
гут поместиться в одном слове памяти (см. рис. 1.7). Поскольку смещения могут быть вычислены компилятором, смещение поля, упакованного внутри слова, то%
же может быть определено компилятором. Это означает, что на многих вычисли%
тельных установках упаковка записей в гораздо меньшей степени снижает эффек%
тивность доступа к полям, чем упаковка массивов.
Рис. 1.7. Представление упакованной записи
1.6.3. Представление множеств
Множество s
удобно представлять в памяти компьютера его характеристической функцией
C(s)
. Это массив логических значений, чья i
%я компонента означает, что i
присутствует в s
. Например, множество небольших чисел s = {2, 3, 5, 7, 11, 13}
представляется последовательностью или цепочкой битов:
35
C(s) = (… 0010100010101100)
Представление множеств характеристическими функциями имеет то преиму%
щество, что операции вычисления, объединения, пересечения и разности двух множеств могут быть реализованы как элементарные логические операции. Сле%
дующие тождества, выполняющиеся для всех элементов i
множеств x
и y
, связыва%
ют логические операции с операциями на множествах:
i IN (x+y) = (i IN x) OR (i IN y)
i IN (x*y) = (i IN x) & (i IN y)
i IN (x–y) = (i IN x) & (i IN y)
Такие логические операции имеются во всех цифровых компьютерах, и, более того, они выполняются одновременно для всех элементов (битов) слова. Поэтому для эффективной реализации базовых операций множества их следует пред%
ставлять небольшим фиксированным количеством слов, для которых можно вы%
полнить не только базовые логические операции, но и операции сдвига. Тогда проверка на принадлежность реализуется единственным сдвигом c последующей проверкой знака. В результате проверка вида x IN {c
1
, c
2
, ... , c n
}
может быть реализована гораздо эффективнее, чем эквивалентное булевское выражение
(x = c
1
) OR (x = c
2
) OR ... OR (x = c n
)
Как следствие множества должны использоваться только c небольшими чис%
лами в качестве элементов, из которых наибольшее равно длине слова компьюте%
ра (минус 1).
1.7. Файлы или последовательностиЕще один элементарный способ структурирования –
последовательность. Обыч%
но это однородная структура, подобная массиву. Это означает, что все ее элемен%
ты имеют одинаковый тип –
базовый тип последовательности. Будем обозначать последовательность s
из n
элементов следующим образом:
s =
0
, s
1
, s
2
, ... , s n–1
>
Число n
называется длиной последовательности.
Эта структура выглядит в точности как массив. Но существенная разница в том, что у массива число элементов зафиксировано в его определении, а у после%
довательности – нет. То есть оно может меняться во время выполнения програм%
мы. Хотя каждая последовательность в любой момент времени имеет конкретную конечную длину, мы должны считать мощность последовательностного типа бес%
конечной, так как нет никаких ограничений на потенциальную длину последова%
тельностей.
Прямое следствие переменной длины последовательностей – невозможность отвести фиксированный объем памяти под переменные%последовательности. По%
этому память нужно выделять во время выполнения программы, в частности ког%
да последовательность растет. Соответственно, когда последовательность сокра%
Файлы или последовательности
Фундаментальные структуры данных
36
щается, освобождающуюся память можно утилизовать. В любом случае нужна некая динамическая схема выделения памяти. Подобными свойствами обладают все структуры переменного размера, и это обстоятельство столь важно, что мы характеризуем их как «сложные» (advanced) структуры, в отличие от фундамен%
тальных, обсуждавшихся до сих пор.
Тогда почему мы обсуждаем последовательности в главе, посвященной фунда%
ментальным структурам? Главная причина – в том, что стратегия управления памятью для последовательностей оказывается достаточно простой (в отличие от других «сложных» структур), если потребовать определенной дисциплины исполь%
зования последовательностей. И тогда можно обеспечить довольно эффективный механизм управления памятью. Вторая причина – в том, что едва ли не в каждой задаче, решаемой с помощью компьютеров, используются последовательности.
Например, последовательности обычно используют в тех случаях, когда данные пересылаются с одного устройства хранения на другое, например с диска или лен%
ты в оперативную память или обратно.
Упомянутая дисциплина состоит в том, чтобы ограничиться только последова%
тельным доступом. Это подразумевает, что доступ к элементам последовательности осуществляется строго в порядке их следования, а порождается последователь%
ность присоединением новых элементов к ее концу. Немедленное следствие –
невозможность
прямого доступа к элементам, за исключением того элемента, ко%
торый доступен для просмотра в данный момент. Именно такая дисциплина дос%
тупа составляет главное отличие последовательностей от массивов. Как мы уви%
дим в главе 2, дисциплина доступа оказывает глубокое влияние на программы.
Преимущество последовательного доступа, который все%таки является серьез%
ным ограничением, – в относительной простоте необходимого здесь способа управ%
ления памятью. Но еще важнее возможность использовать эффективные методы
буферизации (buffering) при пересылке данных между оперативной памятью и внешними устройствами. Последовательный доступ позволяет «прокачивать»
потоки данных с помощью «каналов» (pipes) между разными устройствами хране%
ния. Буферизация подразумевает накопление данных из потока в
буфере и последу%
ющую пересылку целиком содержимого всего буфера, как только он заполнится.
Это приводит к весьма существенному повышению эффективности использова%
ния внешней памяти. Если
ограничиться только последовательным доступом, то механизм буферизации довольно прост для любых последовательностей и любых внешних устройств. Поэтому его можно заранее предусмотреть в вычислитель%
ной системе и предоставить для общего пользования, освободив программиста от необходимости включать его в свою программу. Обычно здесь речь идет о
файловойсистеме, где для постоянного хранения данных используют устройства последова%
тельного доступа большого объема, в которых данные сохраняются даже после вык%
лючения компьютера. Единицу хранения данных в таких устройствах обычно на%
зывают (
последовательным)
файлом. Мы будем использовать термин
файл (file)
как синоним для термина
последовательность (sequence).
Существуют устройства хранения данных, в которых последовательный дос%
туп является единственно возможным. Очевидно, сюда относятся все виды лент.
Но даже на магнитных дисках каждая дорожка представляет собой хранилище,
37
допускающее только последовательный доступ. Строго последовательный доступ характерен для любых устройств с механически движущимися частями, а также для некоторых других.
Отсюда следует, что полезно проводить различие между
стуктурой данных, то есть последовательностью, с одной стороны, и
механизмом доступа к ее элемен там – с другой. Первая объявляется как структура данных, а механизм доступа обычно реализуется посредством некоторой записи, с которой ассоциированы не%
которые операторы, – или, используя современную терминологию, посредством объекта доступа или «бегунка» (rider object). Различать объявление данных и ме%
ханизм доступа полезно еще и потому, что для одной последовательности могут одновременно существовать несколько точек доступа, в которых осуществляется последовательный доступ к разным частям последовательности.
Суммируем главное из предшествующего обсуждения следующим образом:
1. Массивы и записи – структуры, допускающие произвольный доступ к сво%
им элементам. Их используют, размещая в оперативной памяти.
2. Последовательности используются для работы с данными на внешних устройствах хранения, допускающих последовательный доступ, таких как диски или ленты.
3. Мы проводим различие между последовательностью как структурой дан%
ных и механизмом доступа, подразумевающим определенную позицию в ней.
1.7.1. Элементарные операции с файламиДисциплину последовательного
доступа можно обеспечить, предоставляя набор специальных операций, помимо которых доступ к файлам невозможен. Поэтому хотя в общих рассуждениях можно использовать обозначение s
i для i
%го элемента последовательности s
, в программе это невозможно.
Последовательности, то есть файлы, – это обычно большие, динамические структуры данных, сохраняемые на внешних запоминающих устройствах. Такое устройство сохраняет данные, даже если программа заканчивается или отключа%
ется компьютер. Поэтому введение файловой переменной – сложная операция,
подразумевающая подсоединение данных на внешнем устройстве к файловой пе%
ременной в программе. Поэтому объявим тип
File в отдельном модуле, опреде%
ление которого описывает тип вместе с соответствующими операциями. Назовем этот модуль
Files и условимся, что последовательностная или файловая перемен%
ная должна быть явно инициализирована («открыта») посредством вызова соответствующей операции или функции:
VAR f: File f := Open(name)
где name идентифицирует файл на внешнем устройстве хранения данных. В не%
которых системах различается открытие существующего и нового файлов:
f := Old(name)
f := New(name)
Файлы или последовательности
Фундаментальные структуры данных
38
Нужно еще потребовать, чтобы связь между внешней памятью и файловой пе%
ременной разрывалась, например посредством вызова
Close(f)
Очевидно, набор операций должен содержать операцию для порождения (за%
писи) последовательности и еще одну – для ее просмотра (чтения). Потребуем,
чтобы эти операции применялись не напрямую к файлу, а к некоторому объекту%
бегунку, который сам подсоединен к файлу (последовательности) и который реа%
лизует некоторый механизм доступа. Дисциплина последовательного доступа обеспечивается ограничением набора операций доступа (процедур).
Последовательность создается присоединением элементов к ее концу после подсоединения бегунка к файлу. Если есть объявление
VAR r: Rider то бегунок r
подсоединяется к файлу f
оператором
Set(r, f, pos)
где pos = 0
обозначает начало файла (последовательности). Вот типичная схема порождения последовательности:
WHILE
DO x; Write(r, x) END
Чтобы прочитать последовательность, сначала к ней подсоединяется бегунок,
как показано выше, и затем производится чтение одного элемента за другим. Вот типичная схема чтения последовательности:
Read(r, x);
WHILE r.eof DO
x; Read(r, x) END
Очевидно, с каждым бегунком всегда связана некоторая позиция. Обозначим ее как r.pos
. Далее примем, что бегунок содержит предикат (флажок) r.eof
,
указывающий, был ли достигнут конец последовательности в предыдущей опера%
ции чтения
(eof – сокращение от англ. «end of file», то есть «конец файла» – прим.
перев.). Теперь мы можем постулировать и неформально описать следующий на%
бор примитивных операций:
1a.
New(f, name)
определяет f
как пустую последовательность.
1b.
Old(f, name)
определяет f
как последовательность, хранящуюся на внеш%
нем носителе с указанным именем.
2.
Set(r, f, pos)
связывает бегунок r
с последовательностью f
и устанавлива%
ет его в позицию pos
3.
Write(r, x)
записывает элемент со значением x
в последовательность,
с которой связан бегунок r
, и продвигает его вперед.
4.
Read(r, x)
присваивает переменной x
значение элемента, на который указывает бегунок r
, и продвигает его вперед.
5.
Close(f)
регистрирует записанный файл f
на внешнем носителе (с не%
медленной записью содержимого буферов на диск).
Замечание. Запись элемента в последовательность – это часто достаточно сложная операция. С другой стороны, файлы обычно создаются присоединением новых элементов в конце.
39
Замечание переводчика. В примерах программ в книге используются еще две операции:
6.
WriteInt(r, n)
записывает целое число n
в последовательность, с которой связан бегунок r
, и продвигает его вперед.
7. ReadInt(r, n)
присваивает переменной n
целое число, на которое указывает бегунок r
, и продвигает его вперед.
Чтобы дать более точное представление об операциях последовательного дос%
тупа, ниже приводится пример реализации. В нем показано, как можно выразить операции, если последовательности представлены массивами. Этот пример наме%
ренно использует только понятия, введенные и обсужденные ранее, и в нем нет ни буферизации, ни последовательных устройств хранения данных, которые, как указывалось выше, делают понятие последовательности по%настоящему нужным и полезным. Тем не менее этот пример показывает все существенные свойства простейших операций последовательного доступа независимо от того, как после%
довательности представляются в памяти.
Операции реализуются как обычные процедуры. Такой набор объявлений ти%
пов, переменных и заголовков процедур (сигнатур) называется
определением(definition). Будем предполагать, что элементами последовательностей являются литеры, то
есть что речь идет о текстовых файлах, чьи элементы имеют тип
CHAR
Объявления типов
File и
Rider являются хорошими примерами применения запи%
сей, так как в дополнение к полю, обозначающему массив, представляющий дан%
ные, нужны и другие поля для обозначения текущей длины файла и позиции, то есть состояния бегунка:
DEFINITION Files;
(* ADruS171_Files *)
TYPE File; (* *)
Rider = RECORD eof: BOOLEAN END;
PROCEDURE New(VAR name: ARRAY OF CHAR): File;
PROCEDURE Old(VAR name: ARRAY OF CHAR): File;
PROCEDURE Close(VAR f: File);
PROCEDURE Set(VAR r: Rider; VAR f: File; pos: INTEGER);
PROCEDURE Write(VAR r: Rider; ch: CHAR);
PROCEDURE Read(VAR r: Rider; VAR ch: CHAR);
PROCEDURE WriteInt(VAR r: Rider; n: INTEGER);
PROCEDURE ReadInt(VAR r: Rider; VAR n: INTEGER);
END Files.
Определение представляет собой некоторую абстракцию. Здесь нам даны два типа данных,
File и
Rider
, вместе с соответствующими операциями, но без каких%
либо дальнейших деталей, раскрывающих их реальное представление в памяти.
Что касается операций, объявленных как процедуры, то мы видим только их заго%
ловки. Детали реализации не показаны здесь намеренно, и называется это
упря тыванием информации (information hiding). О бегунках мы узнаем только то, что
Файлы или последовательности
Фундаментальные структуры данных
40
у них есть свойство с именем eof
. Этот флажок получает значение
TRUE
, когда опе%
рация чтения достигает конца файла. Позиция бегунка скрыта, и поэтому его ин%
вариант не может быть разрушен прямым обращением к его полям. Инвариант выражает тот факт, что позиция бегунка всегда находится в пределах, соответ%
ствующих данной последовательности. Истинность инварианта первоначально устанавливается процедурой
Set
, а в дальнейшем требуется и поддерживается процедурами
Read и
Write
(а также
ReadInt и
WriteInt
– прим. перев.).
Операторы, реализующие описанные процедуры, а также все детали реализа%
ции типов данных содержатся в так называемом модуле (module). Представить данные и реализовать процедуры можно многими способами. В качестве про%
стого примера приведем следующий модуль (с фиксированной максимальной длиной файла):
MODULE Files;
(* ADruS171_Files *)
CONST MaxLength = 4096;
TYPE
File
File
File
File
File = POINTER TO RECORD
len: INTEGER;
a: ARRAY MaxLength OF CHAR
END;
Rider
Rider
Rider
Rider
Rider = RECORD (* 0 <= pos <= f.len <= Max Length *)
f: File; pos: INTEGER; eof: BOOLEAN
END;
PROCEDURE New
New
New
New
New (name: ARRAY OF CHAR): File;
VAR f: File;
BEGIN
NEW(f); f.len := 0; f.eof := FALSE;
(* ! *)
RETURN f
END New;
PROCEDURE Old
Old
Old
Old
Old (name: ARRAY OF CHAR): File;
VAR f: File;
BEGIN
NEW(f); f.eof := FALSE; (* *)
RETURN f
END Old;
PROCEDURE Close
Close
Close
Close
Close (VAR f: File);
BEGIN
END Close;
PROCEDURE Set
Set
Set
Set
Set (VAR r: Rider; f: File; pos: INTEGER);
BEGIN (* # f # NIL*)
r.f := f; r.eof := FALSE;
IF pos >= 0 THEN
IF pos <= f.len THEN r.pos := pos ELSE r.pos := f.len END
ELSE
41
r.pos := 0
END
END Set;
PROCEDURE Write
Write
Write
Write
Write (VAR r: Rider; ch: CHAR);
BEGIN
IF (r.pos <= r.s.len) & (r.pos < MaxLength) THEN
r.f.a[r.pos] := ch; INC(r.pos);
IF r.pos > r.f.len THEN INC(r.f.len) END
ELSE
r.eof := TRUE
END
END Write;
PROCEDURE Read
Read
Read
Read
Read (VAR r: Rider; VAR ch: CHAR);
BEGIN
IF r.pos < r.f.len THEN
ch := r.f.a[r.pos]; INC(r.pos)
ELSE
r.eof := TRUE
END
END Read;
PROCEDURE WriteInt
WriteInt
WriteInt
WriteInt
WriteInt (VAR r: Rider; n: INTEGER);
BEGIN (* ! *)
END WriteInt;
PROCEDURE ReadInt
ReadInt
ReadInt
ReadInt
ReadInt (VAR r: Rider; VAR n: INTEGER);
BEGIN (* ! *)
END ReadInt;
END Files.
В этом примере максимальная длина, которую могут иметь файлы, задается произвольно выбранной константой. Если какая%то программа попытается со%
здать более длинную последовательность, то это
будет не ошибкой программы,
а недостатком данной реализации. С другой стороны, попытка чтения за текущим концом файла будет означать ошибку программы. Здесь флаг r.eof также исполь%
зуется операцией записи, чтобы сообщить, что выполнить ее не удалось. Поэтому условие
r.eof является предусловием как для
Read
, так и для
Write
(предусло%
вие – это логическое выражение, которое должно быть истинным для корректно%
го выполнения некоторой операции
– прим. перев.).
Скачать 2.67 Mb.