Программу, показанную на рис. 9.2, можно усовершенствовать, если реализовать операцию конкатенации более эффективно. Напомним, что конкатенация становится тривиальной операцией после применения разностного представления списков, введенного в гл. 8. Для того, чтобы использовать эту идею в нашей процедуре сортировки, нужно представить встречающиеся в ней списки в форме пар вида A-Z следующим образом:
УпорМеньш имеет вид A1-Z1
УпорБольш имеет вид A2-Z2
быстрсорт( [], [] ).
быстрсорт( [X | Хвост], УпорСпис) :-
разбиение( X, Хвост, Меньш, Больш),
быстрсорт( Меньш, УпорМеньш),
быстрсорт( Больш, УпорБольш),
конк( УпорМеньш, [X | УпорБольш], УпорСпис).
разбиение( X, [], [], [] ).
разбиение( X, [Y | Хвост], [Y | Меньш], Больш ) :-
больше( X, Y), !,
разбиение( X, Хвост, Меньш, Больш).
разбиение( X, [Y | Хвост], Меньш, [Y | Больш] ) :-
разбиение( X, Хвост, Меньш, Больш).
конк( [], L, L).
конк( [X | L1], L2, [X | L3] ) :-
конк( L1, L2, L3 ).
Рис. 9.2. Быстрая сортировка.
Тогда конкатенации списков
УпорМеньш и [ X | УпорБольш]
будет соответствовать конкатенация пар
A1-Z1 и [ X | A2]-Z2
В результате мы получим
А1-Z2, причем Z1 = [ X | А2]
Пустой список представляется парой Z-Z. Систематически вводя изменения в программу рис. 9.2, мы получим более эффективный способ реализации процедуры быстрсорт, показанный на рис. 9.3 под именем быстрсорт2. Здесь, как и раньше, процедура быстрсорт использует обычное представление списков, но в действительности сортировку выполняет более эффективная процедура быстрсорт2, использующая разностное представление. Эти две процедуры связаны между собой, соотношением
быстрсорт( L, S) :-
быстрсорт2( L, S-[] ).
быстрсорт( Спис, УпорСпис) :-
быстрсорт2( Спис, УпорСпис-[] ).
быстрсорт2( [], Z-Z).
быстрсорт2( [X | Хвост], A1-Z2) :-
разбиение( X, Хвост, Меньш, Больш),
быстрсорт2( Меньш, А1-[X | A2] ),
быстрсорт2( Больш, A2-Z2).
Рис. 9.3. Более эффективная реализация процедуры быстрсортс использованием разностного представления списков. Отношение разбиение( X, Спис, Меньш, Больш) определено, как на рис. 9.2.
Упражнения
9.5. Напишите процедуру слияния двух упорядоченных списков в один третий список. Например:
?- слить( [2, 5, 6, 6, 8], [1, 3, 5, 9], L).
L = [1, 2, 3, 5, 5, 6, 6, 8, 9]
9.6. Программы сортировки, показанные на рис. 9.2 и 9.3, отличаются друг от друга способом представления списков. Первая из них использует обычное представление, в то время как вторая — разностное представление. Преобразование из одного представления в другое очевидно и может быть автоматизировано. Введите в программу рис. 9.2 необходимые изменения, чтобы преобразовать ее в программу рис. 9.3.
9.7. Наша программа быстрсорт в случае, когда исходный список уже упорядочен или почти упорядочен, работает очень неэффективно. Проанализируйте причины этого явления.
9.8. Существует еще одна хорошая идея относительно механизма сортировки списков, позволяющая избавиться от недостатков программы быстрсорт, а именно: разбить список на два меньших списка, отсортировать их, а затем слить вместе. Итак, для того, чтобы отсортировать список L, необходимо
• разбить L на два списка L1 и L2 примерно одинаковой длины;
• произвести сортировку списков L1 и L2,получив списки S1 и S2;
• слить списки S1 и S2, завершив на этом сортировку списка L.
Реализуйте этот принцип сортировки и сравните его эффективность с эффективностью программы быстрсорт.
9.2. Представление множеств двоичными деревьями
Списки часто применяют для представления множеств. Такое использование списков имеет тот недостаток, что проверка принадлежности элемента множеству оказывается довольно неэффективной. Обычно предикат принадлежит( X, L) для проверки принадлежности X к L программируют так:
принадлежит X, [X | L] ).
принадлежит X, [ Y | L] ) :-
принадлежит( X, L).
Для того, чтобы найти X в списке L, эта процедура последовательно просматривает список элемент за элементом, пока ей не встретится либо элемент X, либо конец списка. Для длинных списков такой способ крайне неэффективен.
Для облегчения более эффективной реализация отношения принадлежности применяют различные древовидные структуры. В настоящем разделе мы рассмотрим двоичные деревья.
Двоичное дерево либо пусто, либо состоит из следующих трех частей:
• корень
• левое поддерево
правое поддерево
Корень может быть чем угодно, а поддеревья должны сами быть двоичными деревьями. На рис. 9.4 показано представление множества [а, b, с, d] двоичным деревом. Элементы множества хранятся в виде вершин дерева. Пустые поддеревья на рис. 9.4 не показаны. Например, вершина b имеет два поддерева, которые оба пусты.
Существует много способов представления двоичных деревьев на Прологе. Одна из простых возможностей — сделать корень главным функтором соответствующего терма, а поддеревья — его аргументами. Тогда дерево рис. 9.4 примет вид
а( b, с( d) )
Такое представление имеет среди прочих своих недостатков то слабое место, что для каждой вершины дерева нужен свой функтор. Это может привести к неприятностям, если вершины сами являются структурными объектами.
Рис. 9.4. Двоичное дерево.
Существует более эффективный и более привычный способ представления двоичных деревьев: нам нужен специальный символ для обозначения пустого дерева и функтор для построения непустого дерева из трех компонент (корня и двух поддеревьев). Относительно функтора и специального символа сделаем следующий выбор:
• Пусть атом nil представляет пустое дерево.
• В качестве функтора примем дер, так что дерево с корнем X, левым поддеревом L и правым поддеревом R будет иметь вид терма дер( L, X, R) (см. рис. 9.5).
В этом представлении дерево рис. 9.4 выглядит как
дер( дер( nil, b, nil), a,
дер( дер( nil, d, nil), с, nil) ).
Теперь рассмотрим отношение принадлежности, которое будем обозначать внутри. Цель
внутри( X, T)
истинна, если X есть вершина дерева T. Отношение внутри можно определить при помощи следующих правил:
X есть вершина дерева T, если
• корень дерева T совпадает с X, или
• X — это вершина из левого поддерева, или
• X — это вершина из правого поддерева.
Рис. 9.5. Представление двоичных деревьев.
Эти правила непосредственно транслируются на Пролог следующим образом:
внутри( X, дер( _, X, _) ).
внутри( X, дер( L, _, _) ) :-
внутри( X, L).
внутри( X, дер( _, _, R) ) :-
внутри( X, R).
Очевидно, что цель
внутри( X, nil)
терпит неудачу при любом X.
Посмотрим, как ведет себя наша процедура. Рассмотрим рис. 9.4. Цель
внутри( X, T)
используя механизм возвратов, находит все элементы данных, содержащиеся в множестве, причем обнаруживает их в следующем порядке:
X = а; X = b; X = с; X = d
Теперь рассмотрим вопрос об эффективности. Цель
внутри( а, T)
достигается сразу же после применения первого предложения процедуры внутри. С другой стороны, цель
внутри( d, T)
будет успешно достигнута только после нескольких рекурсивных обращений. Аналогично цель
внутри( e, T)
потерпит неудачу только после того, как будет просмотрено все дерево в результате рекурсивного применения процедуры внутри ко всем поддеревьям дерева T.
В этом последнем случае мы видим такую же неэффективность, как если бы мы представили множество просто списком. Положение можно улучшить, если между элементами множества существует отношение порядка. Тогда можно упорядочить данные в дереве слева направо в соответствии с этим отношением.
Рис. 9.6. Двоичный справочник. Элемент 6 найден после прохода по отмеченному пути 5→8→6.
Будем говорить, что непустое дерево дер( Лев, X, Прав) упорядочено слева направо, если
(1) все вершины левого поддерева Лев меньше X;
