Для понимания идеологии советую прочитать "Свойство замыкания на примере list"
*-Нравится статья? Кликни по рекламе! :)
Множество есть просто набор различных объектов. Чтобы дать ему более точное определение, можно использовать метод абстракции данных. А именно, мы определяем «множество», указывая операции, которые можно производить над множествами. Это операции union-set (объединение), intersection-set (пересечение), element_of_set (проверка на принадлежность) и adjoin-set (добавление элемента). Adjoin_set принимает как аргументы объект и множество, и возвращает множество, которое содержит все элементы исходного множества плюс добавленный элемент. Intersection_set вычисляет пересечение двух множеств, то есть множество, которое содержит только те элементы, которые присутствуют в обоих аргументах.
Можно представить множество как список, в котором ни один элемент не содержится более одного раза. Пустое множество представляется пустым списком.
Итак, первая функция - проверка на наличие элемента в множестве:
def element_of_set(x, set):
if set is None:
return False
elif x==car(set): return True
return element_of_set(x, cdr(set))
Используя эту процедуру, мы можем написать adjoin_set. Если объект, который требуется добавить, уже принадлежит множеству, мы просто возвращаем исходное множество. В противном случае мы добавим объект к списку.представляющему множество:def adjoin_set(x, set):
if element_of_set(x, set)==True:
return set
return (set, (x, None))
Для intersection_set можно использовать рекурсивную стратегию. Если мы знаем, как получить пересечение set2 и cdr от set1, нам нужно только понять, надо ли добавить к нему car от set1. Это зависит от того, принадлежит ли (car set1) еще и set2. Получается такая процедура:def intersection_set(set1, set2):
if set1==() or set2==():
return ()
if set1 is None:
return None
print set1
if element_of_set(car(set1), set2)==True:
return (car(set1), intersection_set(cdr(set1), set2))
return intersection_set(cdr(set1), set2)
Один из вопросов, которые должны нас заботить при разработке реализации — эффективность. Рассмотрим число шагов, которые требуют наши операции над множествами. Поскольку все они используют element_of_set, скорость этой операции оказывает большое влияние на скорость реализации в целом. Теперь заметим, что для того, чтобы проверить, является ли объект элементом множества, процедуре element_of_set может потребоваться просмотреть весь список. (В худшем случае оказывается, что объекта в списке нет.) Следовательно, если в множестве n элементов, element_of_set может затратить до n шагов. Таким образом, число требуемых шагов растет как O(n). Число шагов, требуемых adjoin_set, которая эту операцию использует, такжерастет как O(n). Для intersection_set, которая проделывает element_of_set для каждого элемента set1, число требуемых шагов растет как произведение размеров исходных множеств, или O(n2) для двух множеств размера n.
Множества как упорядоченные списки
Один из способов ускорить операции над множествами состоит в том, чтобы изменить
представление таким образом, чтобы элементы множества перечислялись в порядке возрастания. Для этого нам потребуется способ сравнения объектов, так, чтобы можно было
сказать, какой из них больше. Например, символы мы могли бы сравнивать лексикографически, или же мы могли бы найти какой-нибудь способ ставить каждому объекту в соответствие некоторое уникальное число и затем сравнивать объекты путем сравнения соответствующих чисел. Чтобы упростить обсуждение, мы рассмотрим только случай, когда элементами множества являются числа, так что мы сможем сравнивать элементы при помощи > и <. Мы будем представлять множество чисел как список его элементов в возрастающем порядке.
Одно из преимуществ упорядочения проявляется в element_of_set: проверяя наличие элемента, нам больше незачем просматривать все множество. Если мы достигли элемента, который больше того объекта, который мы ищем, мы можем уже сказать, что искомого в списке нет:
def element_of_set(x, set):
if set is None:
return False
elif x==car(set): return True
elif x<car(set): return False
return element_of_set(x, cdr(set))
Сколько шагов мы на этом выигрываем? В худшем случае, объект, который мы ищем, может быть наибольшим в множестве, так что число шагов то же, что и для неупорядоченного представления. С другой стороны, если мы ищем элементы разных размеров, можно
ожидать, что иногда мы сможем останавливаться близко к началу списка, а иногда нам
все же потребуется просмотреть большую его часть. В среднем мы можем ожидать, что
потребуется просмотреть около половины элементов множества. Таким образом, среднее
число требуемых шагов будет примерно n/2. Это все еще рост порядка O(n), но это
экономит нам в среднем половину числа шагов по сравнению с предыдущей реализацией.
Более впечатляющее ускорение мы получаем в intersection_set. При неупорядоченном представлении эта операция требовала O(n2) шагов, поскольку мы производили полный поиск в set2 для каждого элемента set1. Однако при упорядоченном представлении мы можем воспользоваться более разумным методом. Начнем со сравнения
первых элементов двух множеств, x1 и x2. Если x1 равно x2, мы получаем один элемент пересечения, а остальные элементы пересечения мы можем получить, пересекая
оставшиеся элементы списков-множеств. Допустим, однако, что x1 меньше, чем x2. Поскольку x2 — наименьший элемент set2, мы можем немедленно заключить, что x1
больше нигде в set2 не может встретиться и, следовательно, не принадлежит пересечению. Следовательно пересечение двух множеств равно пересечению set2 с cdr от
set1. Подобным образом, если x2 меньше, чем x1, то пересечение множеств получается
путем пересечения set1 с cdr от set2. Вот процедура:
def intersection_set(set1, set2):
if set1==() or set2==():
return ()
if set1 is None or set2 is None:
return None
x1=car(set1)
x2=car(set2)
if x1==x2:
return(x1, intersection_set(cdr(set1), cdr(set2)))
if x1<x2:
return intersection_set(cdr(set1), set2)
return intersection_set(set1, cdr(set2))
Чтобы оценить число шагов, необходимое для этого процесса, заметим, что на каждом шагу мы сводим задачу нахождения пересечения к вычислению пересечения меньших множеств — убирая первый элемент либо из set1, либо из set2, либо из обоих. Таким образом, число требуемых шагов не больше суммы размеров set1 и set2, а не их произведения, как при неупорядоченном представлении. Это рост O(n), а не O(n2) — заметное ускорение, даже для множеств небольшого размера.Множества как бинарные деревья
Можно добиться еще лучших результатов, чем при представлении в виде упорядоченных списков, если расположить элементы множества в виде дерева. Каждая вершина дерева содержит один элемент множества, называемый «входом» этой вершины, и указатели (возможно, пустые) на две другие вершины. «Левый» указатель указывает на элементы, меньшие, чем тот, который содержится в вершине, а «правый» на элементы, большие, чем тот, который содержится в вершине. На рисунке ниже показано несколько вариантов представления множества {1, 3, 5, 7, 9, 11} в виде дерева. Одно и то же множество может быть представлено в виде дерева несколькими различными способами. Единственное, чего мы требуем от правильного представления — это чтобы все элементы левого поддерева были меньше, чем вход вершины, а элементы правого поддеревабольше.
проверить, содержится ли в множестве число x. Начнем с того, что сравним x со входом
начальной вершины. Если x меньше его, то мы уже знаем, что достаточно просмотреть
только левое поддерево; если x больше, достаточно просмотреть правое поддерево. Если
дерево «сбалансировано», то каждое из поддеревьев будет по размеру примерно вполовину меньше. Таким образом, за один шаг мы свели задачу поиска в дереве размера n к задаче поиска в дереве размера n/2. Поскольку размер дерева уменьшается вдвое на каждом шаге, следует ожидать, что число шагов, требуемых для поиска в дереве размера n, растет как O(log n). Для больших множеств это будет заметным ускорением по сравнению с предыдущими реализациями.
Деревья мы можем представлять при помощи списков. Каждая вершина будет списком из трех элементов: вход вершины, левое поддерево и правое поддерево. None список на месте левого или правого поддерева будет означать, что в этом месте никакое поддерево не присоединяется.
Пример l=(7, (3,(1, None, None),(5, None, None)), (9,(None, None, None),(11, None, None)))
Можно написать процедуру element_of_set с использованием вышеописанной стратегии:
def element_of_set(x, set):
if set is None:
return False
elif x==car(set):
return True
elif x<car(set):
return element_of_set(x, cdr(set))
return element_of_set(x, cddr(set))
Где функция car возвращает текущий элемент, cdr - левую ветвь, а cddr - правую.Добавление элемента к множеству реализуется похожим образом и также требует O(log n) шагов. Чтобы добавить объект x, мы сравниваем его с входом вершины и определяем, должны ли мы добавить x к левой или правой ветви, а добавив x к соответствующей ветви, мы соединяем результат с изначальным входом и второй ветвью.
Если x равен входу, мы просто возвращаем вершину. Если нам требуется добавить x к пустому дереву, мы порождаем дерево, которое содержит x на входе и пустые левое и правое поддеревья. Вот процедура:
def adjoin_set(x, set):
if set is None:
return(x, None, None)
elif x==car(set):
return set
elif x<car(set):
return (car(set), adjoin_set(x, cdr(set)), cddr(set))
return (car(set), cdr(set), adjoin_set(x, cddr(set)))
Утверждение, что поиск в дереве можно осуществить за логарифмическое число шагов, основывается на предположении, что дерево «сбалансировано», то есть что левое и правое его поддеревья содержат приблизительно одинаковое число элементов, так что каждое поддерево содержит приблизительно половину элементов своего родителя. Но как нам добиться того, чтобы те деревья, которые мы строим, были сбалансированы?
множестве, мы имеем право ожидать, что если мы будем добавлять элементы «случайным образом», в среднем дерево будет получаться сбалансированным. Однако такой гарантии у нас нет. Например, если мы начнем с пустого множества и будем добавлять по очереди числа от 1 до 7, то получится весьма несбалансированное дерево, показанное на рисунке 2.17. В этом дереве все левые поддеревья пусты, так что нет никакого преимущества по сравнению с
простым упорядоченным списком. Одним из способов решения этой проблемы было бы
определение операции, которая переводит произвольное дерево в сбалансированное с теми же элементами. Тогда мы сможем проводить преобразование через каждые несколько операций adjoin_set, чтобы поддерживать множество в сбалансированном виде. Есть и другие способы решения этой задачи. Большая часть из них связана с разработкой новых структур данных, для которых и поиск, и вставка могут производиться за O(log n) шагов.
Множества и поиск информации
Мы рассмотрели способы представления множеств при помощи списков и увидели, как выбор представления для объектов данных может сильно влиять на производительность программ, использующих эти данные. Еще одной причиной нашего внимания к множествам было то, что описанные здесь методы снова и снова возникают в приложениях, связанных с поиском данных.
Рассмотрим базу данных, содержащую большое количество записей, например, сведения о кадрах какой-нибудь компании или о транзакциях в торговой системе. Как правило, системы управления данными много времени проводят, занимаясь поиском и модификацией данных в записях; следовательно, им нужны эффективные методы доступа к записям. Для этого часть каждой записи выделяется как идентифицирующий ключ (key). Ключом может служить что угодно, что однозначно определяет запись. В случае записей о кадрах это может быть номер карточки сотрудника. Для торговой системы это может быть номер транзакции. Каков бы ни был ключ, когда мы определяем запись в виде структуры данных, нам нужно указать процедуру выборки ключа, котораявозвращает ключ, связанный с данной записью.
Конечно, существуют лучшие способы представить большие множества, чем в виде неупорядоченных списков. Системы доступа к информации, в которых необходим «произвольный доступ» к записям, как правило, реализуются с помощью методов, основанных
на деревьях, вроде вышеописанной системы с бинарными деревьями. При разработке таких систем методология абстракции данных оказывается весьма полезной. Проектировщик может создать исходную реализацию с помощью простого, прямолинейного представления вроде неупорядоченных списков. Для окончательной версии это не подходит, но такой вариант можно использовать как «поспешную и небрежную» реализацию базы данных, на которой тестируется остальная часть системы. Позже представление данных можно изменить и сделать более изощренным. Если доступ к базе данных происходит в терминах абстрактных селекторов и конструкторов, такое изменение представления данных не потребует никаких модификаций в остальной системе.
Используемая литература:
Комментариев нет:
Отправить комментарий