yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->Операторы АТД, основанные на множествах

Алгоритмы структуры данных

Операторы АТД, основанные на множествах

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

1-3. Первые три процедуры UNION(A, В, С), INTERSECTION^, Б, С) и DIFFERENCE^, В, С) имеют "входными" аргументами множества А и В, а в качестве результата — "выходное" множество С, равное соответственно А  В, AВ и А\ В.

4.    Иногда мы будем использовать оператор, который называется слияние (merge), или объединение непересекающихся множеств. Этот оператор (обозначается MERGE) не отличается от оператора объединения двух множеств, но здесь предполагается, что множества-операнды не пересекаются (т.е. не имеют общих элементов). Процедура MERGE(A, В, С) присваивает множеству С значение А  В, но результат будет не определен, если А  В = 0, т.е. в случае, когда множества А к В имеют общие элементы.

5.    Функция MEMBER(x, А) имеет аргументами множество А и объект ж того зке типа, что и элементы множества А, и возвращает булево значение true (истина), если x  А, и значение false (ложь), если х  А.

6.    Процедура MAKENULL(A) присваивает множеству А значение пустого множества.

7.    Процедура INSERTCr, А), где объект х имеет тот же тип данных, что и элементы множества А, делает х элементом множества А. Другими словами, новым значением множества А будет А  {х}. Отметим, что в случае, когда элемент х уже присутствует в множестве А, это множество не изменяется в результате выполнения данной процедуры.

8.    Процедура DELETE(x, А) удаляет элемент х из множества А, т.е. заменяет множество А множеством А \ {х}. Если элемента х нет в множестве А, то это множество не изменяется. ;

9.    Процедура ASSIGN(A, В) присваивает множеству А в качестве значения множество В.

10. Функция MIN(A) возвращает наименьший элемент множества А. Для применения этой функции необходимо, чтобы множество А было параметризировано и его элементы были линейно упорядочены. Например, МШ({2, 3, 1}) = 1 и MIN({'а', 'Ь', 'с'}) = 'а'. Подобным образом определяется функция МАХ.

11. Функция EQUAL(A, В) возвращает значение true тогда и только тогда, когда множества А и В состоят из одних и тех же элементов.

12. Функция FIND(x) оперирует в среде, где есть набор непересекающихся множеств. Она возвращает имя (единственное) множества, в котором есть элемент х.

4.2. АТД с операторами множеств

Мы начнем с определения АТД для математической модели "множество" с определенными тремя основными теоретико-множественными операторами объединения, пересечения и разности. Сначала приведем пример такого АТД и покажем, как его можно использовать, а затем обсудим некоторые простые реализации этого АТД.

Пример 4.1. Напишем программу, выполняющую простой "анализ потока данных" по блок-схемам представленных процедур. Программа будет использовать переменные абстрактного типа данных SET (Множество), для этого АТД операторы UNION, INTERSECTION, DIFFERENCE, EQUAL, ASSIGN и MAKENULL определены в предыдущем разделе.

В блок-схеме на рис. 4.1 блоки-прямоугольники помечены B1, ..., В8, а операторы определения данных (операторы объявления данных и операторы присваивания) пронумерованы от 1 до 9. Эта блок-схема соответствует алгоритму Евклида (вычисление наибольшего общего делителя двух чисел), но в данном примере детали этого алгоритма нас не интересуют.

В общем случае анализ потока данных относится к той части компилятора, которая проверяет блоковую структуру исходной программы (подобную рис. 4.1) и собирает информацию о выполнении операторов каждого прямоугольника блок-схемы. Влеки (прямоугольники) блок-схемы представляют совокупность операторов, через которые последовательно "проходит" поток данных. Информация, полученная в результате анализа потока данных, помогает повысить качество генерируемого компилятором кода программы. Бели, например, в процессе анализа потока данных обнаружено, что при каждом прохождении блока В переменная х принимает значение 27, то можно подставить 27 для всех вхождений х в блоке В вместо выполнения оператора присваивания этой переменной. Если доступ к константам осуществляется быстрее, чем к значениям переменных, то описанная замена приводит к более эффективному коду программы, полученному в процессе компиляции.

В нашем примере мы хотим определить, где переменная последний раз принимала новое значение. Другими словами, мы хотим для каждого блока В, вычислить множество DEFIN[i] определений d таких, которые сделаны в блоках от В1, до Bi, но в последующих блоках нет других определений для той же переменной, которая определялась в определении d.

Чтобы проиллюстрировать необходимость такой информации, рассмотрим блок-схему на рис. 4.1. Первый блок В1 являясь "холостым" блоком, содержит три определения, присваивающих переменным t, p и q "неопределенные" значения. Если, например, множество DEFIN[7] включает в себя опр萵деление 3, которое присваивает переменной q "неопределенное" значение, значит, программа содержит ошибку, поскольку будет предпринята печать этой переменной без присваивания ей "настоящего" значения. К счастью, в данной блок-схеме нетрудно проверить, что невозможно достигнуть блока В7, минуя операторы присвоения значений этой переменной, поэтому множество DEFIN[7] не будет содержать определение 3.

При вычислении множества DEFIN[i] будем придерживаться нескольких правил. Сначала для каждого блока Вi предварительно вычислим два множества GEN[i] и KILL[i]. GEN[i] — это множество определений, сделанных в блоке Вi. Если в этом блоке есть несколько определений одной переменной, то только последнее из них заносится в множество GEN[i]. Другими словами, GEN[i] является множеством определений, "генерируемых" блоком Вi.

Множество KILL[i] содержит определения (из всех блоков, кроме Д) тех же переменных, которые определены в блоке Д. Например, на рис. 4.1 GEN[4] = {6}, поскольку в блоке В4 содержится определение 6 (переменной t). В свою очередь KILL[4] = {1, 9}, так как существуют определения 1 и 9 той же переменной t и которые не входят в блок В4.

Кроме множеств DEFIN[i], для каждого блока В, также будем вычислять множества DEFOUT[i]. Так же, как DEFIN[i] является множеством определений, действие которых достигает блока Вi, так и DEFOUT[i] — это множество определений, действие которых распространяется за блок Вi. Существует простая формула, связывающая множества DEFIN[i] и DEFOUT[i]:

DEFOUT[i] = (DEFIN[i]-KILL[i])GEN[i] (4.1)

Таким образом, определение d распространяет свое действие за блок Вi только в двух случаях: если его действие начато до блока Вi и не "убито" в этом блоке или если оно генерировано в блоке Вi. Вторая формула, связывающая множества DEFIN[i] и DEFOUT[i], показывает, что DEFIN[i] можно вычислить как объединение тех множеств DEFOUT[p], для которых определяющие их блоки Вp, предшествуют блоку Вi.

(4.2)

Из формулы (4.2) следует очевидный вывод, что определения данных регистрируются в блоке Д тогда и только тогда, когда их действие начинается в одном из предшествующих блоков. В особых случаях, когда Д не имеет предшественников (как блок B1 на рис. 4.1), множество DEFIN[i] считается равным пустому множеству. Хотя в этом примере введено много новых понятий, мы не будем обобщать этот материал для написания общих алгоритмов вычисления областей действия определений в произвольных блок-схемах. Вместо этого мы напишем часть программы вычисления множеств DEFIN[i] и DEFOUT[i] (i = 1, .... 8) для блок-схемы рис. 4.1, предполагая, что множества GEN[i] и KILL[i] определены заранее. Отметим, что предлагаемый фрагмент программы предполагает существование АТД SET (Множество) с операторами UNION, INTERSECTION, DIFFERENCE, EQUAL, ASSIGN и MAKENULL, позднее мы покажем, как реализовать этот АТД.

В создаваемом программном фрагменте (листинг 4.1) процедура propagate(GEN, KILL, DEFIN, DEFOUT) использует формулу (4.1) для вычисления множества DEFOUT указанного блока. Если программа свободна от циклов и повторяющихся структур, то в этом случае множества DEFOUT можно вычислить непосредственно. При наличии в программе циклов или повторяющихся структур для вычисления DEFOUT применяются итерационные процедуры. Сначала для всех і положим DEFIN[i] = 0 и DEFOUT[i] = GEN[i], затем последовательно применим формулы (4.1) и (4.2) несколько раз, пока не "стабилизируются" (не перестанут изменяться) множества DEFIN и DEFOUT. Поскольку каждое новое значение множеств DEFIN[i] и DEFOUT[i] содержит свои предыдущие значения, а количество всех определений в программе ограничено, то процесс должен сходиться к решению уравнений (4.1) и (4.2).

Последовательные значения множеств DEFIN[i] после каждой итерации цикла показаны в табл. 4.1. Заметим, что операторы 1, 2 и 3 присваивания переменным "неопределенных" значений не распространяются на блоки, где эти переменные используются. Отметим также, что в листинге 4.2 сначала выполняются вычисления по формуле (4.2), а затем по формуле (4.1); в общем случае это обеспечивает сходимость процесса вычисления DEFIN[i] всего за несколько итераций.

 

43