156
Глава 2. Построение абстракций с помощ ью данных
Один из вопросов, которые должны нас заботить при разработке реализации — эф-
фективность. Рассмотрим число шагов, которые требуют наши операции над множе-
ствами. Поскольку все они используют element-of-set?, скорость этой операции
оказывает большое влияние на скорость реализации в целом. Теперь заметим, что для
того, чтобы проверить, является ли объект элементом множества, процедуре element-
of-set? может потре боваться просмотреть весь список. (В худшем случае оказывается,
что объекта в списке не т.) Следовательно , если в множестве n элементов, element-of-
set? может затратить до n шагов. Таким образом, ч исло требуемых шагов растет как
Θ(n). Число шагов, требуемых adjoin-set, которая эту операцию использует, также
растет как Θ(n). Для intersection-set, которая проделывает element-of-set?
для каждого элемента set1, число требуемых шагов растет как произведение размеров
исходных множеств, или Θ(n
2
) для двух множеств размера 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)