Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 36
Текст из файла (страница 36)
Построение абстракций с помощью данныхОдин из вопросов, которые должны нас заботить при разработке реализации — эффективность. Рассмотрим число шагов, которые требуют наши операции над множествами. Поскольку все они используют element-of-set?, скорость этой операцииоказывает большое влияние на скорость реализации в целом. Теперь заметим, что длятого, чтобы проверить, является ли объект элементом множества, процедуре elementof-set? может потребоваться просмотреть весь список. (В худшем случае оказывается,что объекта в списке нет.) Следовательно, если в множестве n элементов, element-ofset? может затратить до n шагов. Таким образом, число требуемых шагов растет какΘ(n).
Число шагов, требуемых adjoin-set, которая эту операцию использует, такжерастет как Θ(n). Для intersection-set, которая проделывает element-of-set?для каждого элемента set1, число требуемых шагов растет как произведение размеровисходных множеств, или Θ(n2 ) для двух множеств размера n. То же будет верно и дляunion-set.Упражнение 2.59.Реализуйте операцию union-set для представления множеств в виде неупорядоченных списков.Упражнение 2.60.Мы указали, что множество представляется как список без повторяющихся элементов. Допустим теперь, что мы разрешаем повторяющиеся элементы. Например, множество {1, 2, 3} могло быбыть представлено как список (2 3 2 1 3 2 2).
Разработайте процедуры element-of-set?,adjoin-set, union-set и intersection-set, которые бы работали с таким представлением.Как соотносится эффективность этих операций с эффективностью соответствующих процедур дляпредставления без повторений? Существуют ли приложения, в которых Вы бы использовали скорееэто представление, чем представление без повторений?Множества как упорядоченные спискиОдин из способов ускорить операции над множествами состоит в том, чтобы изменитьпредставление таким образом, чтобы элементы множества перечислялись в порядке возрастания.
Для этого нам потребуется способ сравнения объектов, так, чтобы можно былосказать, какой из них больше. Например, символы мы могли бы сравнивать лексикографически, или же мы могли бы найти какой-нибудь способ ставить каждому объекту всоответствие некоторое уникальное число и затем сравнивать объекты путем сравнениясоответствующих чисел.
Чтобы упростить обсуждение, мы рассмотрим только случай,когда элементами множества являются числа, так что мы сможем сравнивать элементыпри помощи > и <. Мы будем представлять множество чисел как список его элементов в возрастающем порядке. В то время как первая наша реализация позволяла нампредставлять множество {1, 3, 6, 10} путем перечисления его элементов в произвольномпорядке, в новом представлении разрешен только список (1 3 6 10).Одно из преимуществ упорядочения проявляется в element-of-set?: проверяяналичие элемента, нам больше незачем просматривать все множество.
Если мы достиглиэлемента, который больше того объекта, который мы ищем, мы можем уже сказать, чтоискомого в списке нет:(define (element-of-set? x set)(cond ((null? set) false)2.3. Символьные данные157((= x (car set)) true)((< x (car set)) false)(else (element-of-set? x (cdr set)))))Сколько шагов мы на этом выигрываем? В худшем случае, объект, который мы ищем, может быть наибольшим в множестве, так что число шагов то же, что и для неупорядоченного представления. С другой стороны, если мы ищем элементы разных размеров, можноожидать, что иногда мы сможем останавливаться близко к началу списка, а иногда намвсе же потребуется просмотреть большую его часть.
В среднем мы можем ожидать, чтопотребуется просмотреть около половины элементов множества. Таким образом, среднеечисло требуемых шагов будет примерно n/2. Это все еще рост порядка Θ(n), но это экономит нам в среднем половину числа шагов по сравнению с предыдущей реализацией.Более впечатляющее ускорение мы получаем в intersection-set.
При неупорядоченном представлении эта операция требовала Θ(n2 ) шагов, поскольку мы производилиполный поиск в set2 для каждого элемента set1. Однако при упорядоченном представлении мы можем воспользоваться более разумным методом. Начнем со сравненияпервых элементов двух множеств, x1 и x2. Если x1 равно x2, мы получаем один элемент пересечения, а остальные элементы пересечения мы можем получить, пересекаяоставшиеся элементы списков-множеств.
Допустим, однако, что x1 меньше, чем x2. Поскольку x2 — наименьший элемент set2, мы можем немедленно заключить, что x1больше нигде в set2 не может встретиться и, следовательно, не принадлежит пересечению. Следовательно пересечение двух множеств равно пересечению set2 с cdr отset1. Подобным образом, если x2 меньше, чем x1, то пересечение множеств получаетсяпутем пересечения set1 с cdr от set2. Вот процедура:(define (intersection-set set1 set2)(if (or (null? set1) (null? set2))’()(let ((x1 (car set1)) (x2 (car set2)))(cond ((= x1 x2)(cons x1(intersection-set (cdr set1)(cdr set2))))((< x1 x2)(intersection-set (cdr set1) set2))((< x2 x1)(intersection-set set1 (cdr set2)))))))Чтобы оценить число шагов, необходимое для этого процесса, заметим, что на каждомшагу мы сводим задачу нахождения пересечения к вычислению пересечения меньшихмножеств — убирая первый элемент либо из set1, либо из set2, либо из обоих.
Такимобразом, число требуемых шагов не больше суммы размеров set1 и set2, а не ихпроизведения, как при неупорядоченном представлении. Это рост Θ(n), а не Θ(n2 ) —заметное ускорение, даже для множеств небольшого размера.Упражнение 2.61.Напишите реализацию adjoin-set для упорядоченного представления. По аналогии с elementof-set? покажите, как использовать упорядочение, чтобы получить процедуру, которая в среднемтребует только половину числа шагов, которое требуется при неупорядоченном представлении.Глава 2. Построение абстракций с помощью данных158731195531137519971111Рис.
2.16. Различные бинарные деревья, представляющие множество {1, 3, 5, 7, 9, 11}.Упражнение 2.62.Дайте представление порядка Θ(n) для операции union-set с представлением в виде упорядоченных списков.Множества как бинарные деревьяМожно добиться еще лучших результатов, чем при представлении в виде упорядоченных списков, если расположить элементы множества в виде дерева. Каждая вершинадерева содержит один элемент множества, называемый «входом» этой вершины, и указатели (возможно, пустые) на две другие вершины. «Левый» указатель указывает наэлементы, меньшие, чем тот, который содержится в вершине, а «правый» на элементы,большие, чем тот, который содержится в вершине.
На рисунке 2.16 показано нескольковариантов представления множества {1, 3, 5, 7, 9, 11} в виде дерева. Одно и то же множество может быть представлено в виде дерева несколькими различными способами.Единственное, чего мы требуем от правильного представления — это чтобы все элементы левого поддерева были меньше, чем вход вершины, а элементы правого поддеревабольше.Преимущество древовидного представления следующее.
Предположим, мы хотимпроверить, содержится ли в множестве число x. Начнем с того, что сравним x со входомначальной вершины. Если x меньше его, то мы уже знаем, что достаточно просмотретьтолько левое поддерево; если x больше, достаточно просмотреть правое поддерево. Еслидерево «сбалансировано», то каждое из поддеревьев будет по размеру примерно вполовину меньше. Таким образом, за один шаг мы свели задачу поиска в дереве размера nк задаче поиска в дереве размера n/2.
Поскольку размер дерева уменьшается вдвое накаждом шаге, следует ожидать, что число шагов, требуемых для поиска в дереве размера n, растет как Θ(log n)38 . Для больших множеств это будет заметным ускорением по38 Уменьшение размера задачи вдвое на каждом шагу является определяющей характеристикой логарифмического роста, как мы видели на примере алгоритма быстрого возведения в степень в разделе 1.2.4 и методаполовинного деления в разделе 1.3.3.2.3.
Символьные данные159сравнению с предыдущими реализациями.Деревья мы можем представлять при помощи списков. Каждая вершина будет списком из трех элементов: вход вершины, левое поддерево и правое поддерево. Пустойсписок на месте левого или правого поддерева будет означать, что в этом месте никакое поддерево не присоединяется. Мы можем описать это представление при помощиследующих процедур39 :(define (entry tree) (car tree))(define (left-branch tree) (cadr tree))(define (right-branch tree) (caddr tree))(define (make-tree entry left right)(list entry left right))Теперь можно написать процедуру element-of-set? с использованием вышеописанной стратегии:(define (element-of-set? x set)(cond ((null? set) false)((= x (entry set)) true)((< x (entry set))(element-of-set? x (left-branch set)))((> x (entry set))(element-of-set? x (right-branch set)))))Добавление элемента к множеству реализуется похожим образом и также требует Θ(log n) шагов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
