Lecture
Это окончание невероятной информации про динамические структуры данных.
...
= nil then DelList: = nil {if m = 0, el-t is removed from the beginning of the list} else if m = 0 then DelList: = cdr (l) {- delete email at the place m-1 in the list without the 1st email; - insert the 1st el-t in the beginning of the received list} else DelList: = cons (car (l), DelList (cdr (l), m-1)); end; {Function DelList} {*** permutation in the list of l-places with the numbers m and m + 1} Function ExchngList (l: lpt; m: integer): lpt; begin {if the list is empty, it remains empty} if l = nil then ExchngList: = nil else if m = 0 then {if m = 0 and the next email is not, the list remains unchanged} if cdr (l) = nil then ExchngList: = l {if m = 0 (exchange of the 0th and 1st al-com): - a list is taken without two first emails - cdr (cdr (l)); - the 0th el is added to its beginning; - the 1st el-t is added to the beginning of the received list - car (cdr (l))} else ExchngList: = cons (car (cdr (l)), cons (car (l), cdr (cdr (l)))) else ExchngList: = cons (car (l), ExchngList (cdr (l), m-1)); end; {Function ExchngList} End.
To facilitate the reader to the task of self-study of the example, we will examine the first two functions in detail. Since the functions of this example widely use nested calls, including recursive ones, in the following analyzes the description of each next nested call is shifted to the right.
The Append function adds an x to the end of the list l. Consider its implementation on the example of the call: Append (4, (1,2,3)).
Since the list argument is not empty, the else branch is executed. It contains the operator:
Append: = cons (car (l), Append (x, cdr (l)));
It is important to accurately imagine the sequence of actions to perform this statement:
The ListRev function inverts the list — changing the order of its elements to the opposite. When a function is accessed, its second argument must be nil. Example: ListRev (1, (2,3), 4), nil).
The input list is not empty, so execution follows the else branch, where:
ListRev: = ListRev (cdr (l), cons (car (l), q));
Sequencing:
In program example 5.13, the use of branching lists is shown to solve a more applied problem. The program presented here is a calculator, it calculates the value of the entered arithmetic expression, whose components can be integers, signs of four arithmetic operations and parentheses. To simplify the example, we have introduced the following restrictions:
{==== Software Example 5.13 ====}
{Calculator. Calculating arithmetic expressions}
program Calc;
Uses ListWork;
type cptr = ^ char;
iptr = ^ integer;
const {numeric characters}
digits: set of char = ['0' .. '9'];
{high priority operation marks}
prty: set of char = ['*', '/'];
var s: string; {source line}
n: integer; {number of current character in ref. line}
{*** Representation of source line in list form}
Function Creat_Lst: lpt;
var lll: lpt; {pointer to the beginning of the current list}
s1: char; {current character of string}
st: string; {drive operand string}
{* Create an atom for an integer}
Procedure NewInt;
var ip: iptr; cc: integer;
begin
if Length (st)> 0 then begin
{if st is a digital representation of a number,
it is converted to integer type, an atom is created for it and
written to the end of the list}
New (ip); Val (st, ip ^, cc);
lll: = Append (NewAtom (ip, 'I'), lll);
st: = ''; {line drive is reset}
end; end; {Procedure NewInt}
Procedure NewChar; {Creating an atom for Char}
var cp: cptr;
begin {memory is allocated for 1 character, in it
the value of s1 is preserved, an atom is created for it,
written to the end of the list}
New (cp); cp ^: = s1;
lll: = Append (NewAtom (cp, 'C'), lll);
end; {Procedure NewChar}
begin {Function Creat_Lst}
{source list is empty, row drive is empty}
lll: = nil; st: = '';
while n <= length (s) do begin {loop to the end of the source string}
s1: = s [n]; n: = n + 1;
case s1 of
'(': {start of bracket subexpression: is created for it
new list - Creat_Lst, which is made up as a sub-list -
NewNode and added to the end of the current list — Append}
lll: = Append (NewNode (Creat_Lst), lll);
')': {the end of the bracket expression is the last number in
brackets are added to the end of the current list and the current list
formed - end of function}
begin
NewInt; Creat_Lst: = lll; Exit;
end;
else {begin} {number or sign of operation}
if s1 in digits then {numbers accumulate in st}
st: = st + s1
else begin {operation sign}
NewInt; {created atom for previously accumulated number}
NewChar; {created atom for sign}
end; {end;} end; {case} end; {while}
NewInt; {created atom for previously accumulated number}
Creat_Lst: = lll;
end; {Function Creat_Lst}
{*** Allocation of high-priority operations in sub-lists}
Function FormPrty (l: lpt): lpt;
var op1, op, op2: lpt; {1st operand, sign, 2nd operand}
l2, l3: lpt;
cp: ^ char;
begin
l2: = nil; {output list is empty}
{selection of 1st operand}
op1: = car (l); l: = cdr (l);
{if 1st operand - sublist - processing sublist}
if not atom (op1) then op1: = FormPrty (op1);
while l <> nil do begin {until the source list is empty}
{mark operation mark}
op: = car (l); l: = cdr (l);
{selection of 2nd operand}
op2: = car (l); l: = cdr (l);
{if the 2nd operand is a sublist - processing a sublist}
if not atom (op2) then op2: = FormPrty (op2);
if cptr (op ^ .down) ^ in prty then
{if the sign of the operation is priority, then a sublist is created:
1st operand, sign, 2nd operand, this sub-list is next 1st
operand}
op1: = cons (op1, cons (op, cons (op2, nil)))
else begin {if the sign is non-priority, 1st operand and sign
are written to the output list, the 2nd operand is then the 1st
operand}
l2: = Append (op, Append (op1, l2));
op1: = op2;
end; end;
FormPrty: = Append (op1, l2); {last operand added to
output list}
end; {Function FormPrty}
{*** expression evaluation}
Function Eval(l : lpt) : integer;
var op1, op, op2 : lpt;
begin
{ выделение 1-го операнда }
op1:=car(l); l:=cdr(l);
{ если 1-й операнд - подсписок - вычислить его выражение }
if not atom(op1) then iptr(op1^.down)^:=Eval(op1);
while l <> nil do begin
{ выделение знака операции }
op:=car(l); l:=cdr(l);
{ выделение 2-го операнда }
op2:=car(l); l:=cdr(l);
{ если 2-й операнд - подсписок - вычислить его выражение }
if not atom(op2) then iptr(op2^.down)^:=Eval(op2);
{ выполнение операции, результат - в op1 }
case cptr(op^.down)^ of
'+' : iptr(op1^.down)^:=iptr(op1^.down)^+iptr(op2^.down)^;
'-' : iptr(op1^.down)^:=iptr(op1^.down)^-iptr(op2^.down)^;
'*' : iptr(op1^.down)^:=iptr(op1^.down)^*iptr(op2^.down)^;
'/' : iptr(op1^.down)^:=iptr(op1^.down)^ div iptr(op2^.down)^;
end;
end;
Eval:=iptr(op1^.down)^; { возврат последнего результата }
end; { Function Eval }
{*** Главная программа }
var l : lpt;
begin
write('>'); readln(s); { ввод исходной строки }
{ формирование списка }
n:=1; l:=Creat_Lst;
{ выделение приоритетных операций }
l:=FormPrty(l);
{ вычисление и печать результата }
writeln(s,'=',Eval(l));
END.
Выполнение программы состоит во вводе строки, представляющей исходное выражение и последовательных обращений к трем функциям: Creat_Lst, FormPrty и Eval.
Функция Creat_Lst преобразует исходную строку в список. В функции поэлементно анализируются символы строки. Различаемые символы: левая круглая скобка, правая скобка, знаки операций и цифры. Цифровые символы накапливаются в промежуточной строке. Когда встречается символ-разделитель - правая скобка или знак операции накопленная строка преобразуется в число, для него создается атом с типом 'I' и включается в конец списка. Для знака операции создается атом с типом 'C' и тоже включается в конец списка. Левая скобка приводит к рекурсивному вызову Creat_Lst. Этот вызов формирует список для подвыражения в скобках, формирование списка заканчивается при появлении правой скобки. Для сформированного таким образом списка создается узел, и он включается в основной список как подсписок. Так, например, для исходной строки:
5+12/2-6*(11-7)+4
функцией Creat_Lst будет сформирован такой список:
(5,+,12,/,2,-,6,*,(11,-,7),+,4)
Следующая функция - FormPrty - выделяет в отдельные подсписки операции умножения и деления, имеющие более высокий приоритет, и их операнды. Функция просматривает список и выделяет в нем последовательные тройки элементов "операнд-знак-операнд". Если один из операндов является подсписком, то он обрабатывается функцией FormPrty. Если знак является одним из приоритетных знаков, то из тройки формируется подсписок, который становится первым операндом для следующей тройки. Если знак не приоритетный, то второй операнд тройки становится первым для следующей тройки. Список нашего примера после обработки его функцией FormPrty превратится в:
(5,+,(12,/,2),-,(6,*,(11,-,7)),+,4)
Наконец, функция Eval выполняет вычисления. Она во многом похожа на функцию FormPrty: в ней также выделяются тройки "операнд 1- 0знак-операнд". Если один или оба операнда являются подсписками, то сначала вычисляются эти подсписки и заменяются на атомы - результаты вычисления. Если оба операнда - атомы, то над ними выполняется арифметика, задаваемая знаком операции. Поскольку в первую очередь вычисляются подсписки, то подвыражения, обозначен- ные скобками в исходной строке, и операции умножения и деления выполняются в первую очередь. Для нашего примера порядок вычислений будет таков:
12 / 2 = 6; 5 + 6 = 11; 11 - 7 = 4; 6 * 4 = 24;
24 + 4 = 28; 11 - 28 = -17
LISP является наиболее развитым и распространенным языком обработки списков. "Идеология" и терминология этого языка в значительной степени повлияла на общепринятые подходы к обработке списков и использовалась и нами в предыдущем изложении. Все данные в LISP представляются в виде списков, структура элементсписка соответствует рис.5.15. LISP обеспечивает базовые функции обработки списков - car, cdr, cons, atom. Также многие вторичные функции реализованы в языке как базовые - для повышения их эффективности. Помимо чисто списковых операций в языке обеспечиваются операции для выполнения арифметических, логических операций, отношения, присваивания, ввода-вывода и т.д. Операция cond обеспечивает ветвление.
Сама LISP-программа представляется как список, записанный в скобочной форме. Элементами простого программного списка является имя операции/функции и ее параметры. Параметрами могут быть в свою очередь обращения к функциям, которые образуют подсписки. Как правило, вся программа на LISP представляет собой единственное обращение к функции с множеством вложенных обращений - рекурсивных или к другим функциям. Поэтому программирование на языке LISP часто называют "функциональным программированием". Функции, приведенные нами в примере 5.11 являются переложением на язык PASCAL их LISP-реализаций.
Системы программирования LISP строятся и как компиляторы, и как интерпретаторы. Однако, независимо от подхода к построению системы программирования, она обязательно включает в себя "сборку мусора" (см.раздел 5.7). Обратите внимание на то, что в примере 5.11, представляя PASCAL-реализацию операций языка LISP, мы в некоторых функциях выделяли память, но нигде ее не освобождали. Система программирования LISP автоматически следит за использованием памяти и обеспечивает ее освобождение.
Другие языки обработки списков, например IPL-V, COMMIT в большей мере ориентированы на решение прикладных задач, а не на обработку абстрактных списков, хотя использование списковых структур заложено в основы в их реализации.
Динамические структуры по определению характеризуется непостоянством и непредсказуемостью размера. Поэтому память под отдельные элементы таких структур выделяется в момент, когда они "начинают существовать" в процессе выполнения программы, а не вовремя трансляции. Когда в элементе структуры больше нет необходимости, занимаемая им память освобождается.
В современных вычислительных средах большая часть вопросов, связанных с управлением памятью решается операционными системами или системами программирования. Для программиста прикладных задач динамическое управление памятью либо вообще прозрачно, либо осуществляется через достаточно простой и удобный интерфейс стандартных процедур/функций. Однако, перед системным программистом вопросы управления памятью встают гораздо чаще. Во-первых, эти вопросы в полном объеме должны быть решены при проектировании операционных систем и систем программирования, во-вторых, некоторые сложные приложения могут сами распределять память в пределах выделенного им ресурса, наконец в-третьих, знание того, как в данной вычислительной среде распределяется память, позволит программисту построить более эффективное программное изделие даже при использовании интерфейса стандартных процедур.
В общем случае при распределении памяти должны быть решены следующие вопросы:
В распоряжении программы обычно имеется адресное пространство, которое может рассматриваться как последовательность ячеек памяти с адресами, линейно возрастающими от 0 до N. Какие-то части этого адресного пространства обычно заняты системными программами и данными, какие-то - кодами и статическими данными самой программы, оставшаяся часть доступна для динамического распределения. Обычно доступная для распределения память представляет собой непрерывный участок пространства с адресными границами от n1 до n2. В управлении памятью при каждом запросе на память необходимо решать, по каким адресам внутри доступного участка будет располагаться выделяемая память.
В некоторых системах программирования выделение памяти автоматизировано полностью: система не только сама определяет адрес выделяемой области памяти, но и определяет момент, когда память должна выделяться. Так, например, выделяется память под элементы списков в языке LISP, под символьные строки в языках SNOBOL и REXX. В других системах программирования - к ним относится большинство универсальных процедурных языков программирования - моменты выделения и освобождения памяти определяются программистом. Программист должен выдать запрос на выделение/освобождение памяти при помощи стандартной процедуры/функции - ALLOCATE/FREE в PL/1, malloc/free в C, New/Dispose в PASCAL и т.п. Система сама определяет размещение выделяемого блока и функция выделения памяти возвращает его адрес. Наконец, в уже названных выше задачах системного программирования программист зачастую должен определить также и адрес выделяемой области.
Память всегда выделяется блоками - т.е. обязательно непрерывными последовательностями смежных ячеек. Блоки могут быть фиксированной или переменной длины. Фиксированный размер блока гораздо удобнее для управления: в этом случае вся доступная для распределения память разбивается на "кадры", размер каждого из которых равен размеру блока, и любой свободный кадр годится для удовлетворения любого запроса. К сожалению, лишь ограниченный круг реальных задач может быть сведен к блокам фиксированной длины.
Одной из проблем, которые должны приниматься во внимание при управлении памятью является проблема фрагментации (дробления) памяти. Она заключается в возникновении "дыр" - участков памяти, которые не могут быть использованы. Различаются дыры внутренние и внешние. Внутренняя дыра - неиспользуемая часть выделенного блока, она возникает, если размер выделенного блока больше запрошенного. Внутренние дыры характерны для выделения памяти блоками фиксированной длины. Внешняя дыра - свободный блок, который в принципе мог бы быть выделен, но размер его слишком мал для удовлетворения запроса. Внешние дыры характерны для выделения блоками переменной длины. Управление памятью должно быть построено таким образом, чтобы минимизировать суммарный объем дыр.
Система управления памятью должна прежде всего "знать", какие ячейки имеющейся в ее распоряжении памяти свободны, а какие - заняты. Методы учета свободной памяти основываются либо на принципе битовой карты, либо на принципе списков свободных блоков.
В методах битовой карты создается "карта" памяти - массив бит, в котором каждый однобитовый элемент соответствует единице доступной памяти и отражает ее состояние: 0 - свободна, 1 - занята. Если считать единицей распределения единицу адресации - байт, то сама карта памяти будет занимать 1/8 часть всей памяти, что делает ее слишком дорогостоящей. Поэтому при применении методов битовой карты обычно единицу распределения делают более крупной, например, 16 байт. Карта, таким образом, отражает состояние каждого 16-байтного кадра. Карта может рассматриваться как строка бит, тогда поиск участка памяти для выделения выполняется как поиск в этой строке подстроки нулей требуемой длины.
В другой группе методов участки свободной памяти объединяются в связные списки. В системе имеется переменная, в которой хранится адрес первого свободного участка. В начале первого свободного участка записывается его размер и адрес следующего свободного участка. В простейшем случае список свободных блоков никак не упорядочивается. Поиск выполняется перебором списка.
Дисциплины выделения памяти решают вопрос: какой из свободных участков должен быть выделен по запросу. Выбор дисциплины распределения не зависит от способа учета свободной памяти. Две основные дисциплины сводятся к принципам "самый подходящий" и "первый подходящий". По дисциплине "самый подходящий" выделяется тот свободный участок, размер которого равен запрошенному или превышает его на минимальную величину. По дисциплине "первый подходящий" выделяется первый же найденный свободный участок, размер которого не меньше запрошенного. При применении любой дисциплины, если размер выбранного для выделения участка превышает запрос, выделяется запрошенный объем памяти, а остаток образует свободный блок меньшего размера. В некоторых системах вводится ограничение на минимальный размер свободного блока: если размер остатка меньше некоторого граничного значения, то весь свободный блок выделяется по запросу без остатка. Практически во всех случаях дисциплина "первый подходящий" эффективнее дисциплины "самый подходящий". Это объясняется во-первых, тем, что при поиске первого подходящего не требуется просмотр всего списка или карты до конца, во-вторых, тем, что при выборе всякий раз "самого подходящего" остается больше свободных блоков маленького размера - внешних дыр.
Когда в динамической структуре данных или в отдельном ее элементе нет больше необходимости, занимаемая ею память должна быть утилизована, т.е. освобождена и сделана доступной для нового распределения. В тех системах, где память запрашивается программистом явным образом, она и освобождена должна быть явным образом. Даже в некоторых системах, где память выделяется автоматически, она освобождается явным образом (например, операция DROP в языке REXX). В таких системах, конечно, задача утилизации решается просто. При представлении памяти на битовой карте достаточно просто сбросить в 0 биты, соответствующие освобожденным кадрам. При учете свободной памяти списками блоков освобожденный участок должен быть включен в список, но одного этого недостаточно. Следует еще позаботиться о том, чтобы при образовании в памяти двух смежных свободных блоков они слились в один свободный блок суммарного размера. Задача слияния смежных блоков значительно упрощается при упорядочении списка свободных блоков по адресам памяти - тогда смежные блоки обязательно будут соседними элементами этого списка.
Задача утилизации значительно усложняется в системах, где нет явного освобождения памяти: тогда на систему ложится задача определения того, какие динамические структуры или их элементы уже не нужны программисту. Один из методов решения этой задачи предполагает, что система не приступает к освобождению памяти до тех пор, пока свободной памяти совсем не останется. Затем все зарезервированные блоки проверяются и освобождаются те из них, которые больше не используются. Такой метод называется "сборкой мусора". Программа, сборки мусора вызывается тогда, когда нет возможности удовлетворить некоторый частный запрос на память, или когда размер доступной области памяти стал меньше некоторой заранее определенной границы. Алгоритм сборки мусора обычно бывает двухэтапным. На первом этапе осуществляется маркировка (пометка) всех блоков, на которые указывает хотя бы один указатель. На втором этапе все неотмеченные блоки возвращаются в свободный список, а метки стираются. Важно, чтобы в момент включения сборщика мусора все указатели были установлены на те блоки, на которые они должны указывать. Если необходимо в некоторых алгоритмах применять методы с временным рассогласованием указателей, необходимо временно отключить сборщик мусора - пока имеется такое рассогласование. Один из самых серьезных недостатков метода сборки мусора состоит в том, что расходы на него увеличиваются по мере уменьшения размеров свободной области памяти.
Другой метод - освобождать любой блок, как только он перестает использоваться. Он обычно реализуется посредством счетчиков ссылок - счетчиков, в которых записывается, сколько указателей на данный блок имеется в данный момент времени. Когда значение счетчика становится равным 0, соответствующий блок оказывается недоступным и, следовательно, не используемым. Блок возвращается в свободный список. Такой метод предотвращает накопление мусора, не требует большого числа оперативных проверок во время обработки данных. Однако и у этого метода есть определенные недостатки. Вопервых, если зарезервированные блоки образуют циклическую структуру, то счетчик ссылок каждого из них не равен 0, когда все связи, идущие извне блоков в циклическую структуру, будут уничтожены. Это приводит к появлению мусора. Существуют различные возможности устранить этот недостаток: запретить циклические и рекурсивные структуры; отмечать циклические структуры флажками, и обрабатывать их особым образом; потребовать, чтобы любая циклическая структура всегда имела головной блок, счетчик циклов которого учитывал бы только ссылки от элементов, расположенных вне цикла, и чтобы доступ ко всем блокам этой структуры осуществлялся только через него. Во-вторых, требуются лишние затраты времен и памяти на ведение счетчиков ссылок.
В некоторых случаях может быть полезен метод восстановления ранее зарезервированной памяти, называемый уплотнением. Уплотнение осуществляется путем физического передвижения блоков данных с целью сбора всех свободных блоков в один большой блок. Преимущество этого метода в том, что после его применения выделение памяти по запросам упрощается. Единственная серьезная проблема, возникающая при использовании метода - переопределение указателей. Механизм уплотнения использует несколько просмотров памяти. Сначала определяются новые адреса всех используемых блоков, которые были отмечены в предыдущем проходе, а затем во время следующего просмотра памяти все указатели, связанные с отмеченными блоками, переопределяются. После этого отмеченные блоки переставляются. Механизма освобождения памяти в методе восстановления совсем нет. Вместо него используется механизм маркировки, который отмечает блоки, используемые в данный момент. Затем, вместо того, чтобы освобождать каждый не отмеченный блок путем введения в действие механизма освобождения памяти, помещающего этот блок в свободный список, используется уплотнитель, который собирает неотмеченные блоки в один большой блок в одном конце области памяти. Недостаток метода в том, что из-за трех просмотров памяти велики затраты времени. Однако повышенная скорость резервирования в определенных условиях может компенсировать этот недостаток.
In the case of the blocks
Часть 1 5. DYNAMIC STRUCTURES OF DATA. RELATED LISTS
Часть 2 5.5. Язык программирования LISP - 5. DYNAMIC STRUCTURES OF DATA.
Comments
To leave a comment
Structures and data processing algorithms.
Terms: Structures and data processing algorithms.