Неизвестно - Prolog

Программу, показанную на рис. 9.2, можно усовершенствовать, если реализовать операцию конкатенации более эффективно. Напомним, что конкатенация

быстрсорт( [ ], [ ] ).

быстрсорт( [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. Быстрая сортировка.

становится тривиальной операцией после применения разностного представления списков, введенного в гл. 8. Для того, чтобы использовать эту идею в нашей процедуре сортировки, нужно представить встречающиеся в ней списки в форме пар вида A-Zследующим образом:

УпорМеньшимеет вид A1-Z1

УпорБольшимеет вид A2-Z2

Тогда конкатенации списков

УпорМеньши [ Х | УпорБольш]

будет соответствовать конкатенация пар

A1-Z1 и [ Х | A2]-Z2

В результате мы получим

А1-Z2, причем Z1 = [ Х | А2]

Пустой список представляется парой Z-Z. Систематически вводя изменения в программу рис. 9.2, мы получим более эффективный способ реализации процедуры быстрсорт, показанный на рис. 9.3 под именем

быстрсорт( Спис, УпорСпис) :-

быстрсорт2( Спис, УпорСпис-[ ] ).

быстрсорт2( [ ], Z-Z).

быстрсорт2( [X | Хвост], A1-Z2) :-

разбиение( X, Хвост, Меньш, Больш),

быстрсорт2( Меньш, А1-[Х | A2] ),

быстрсорт2( Больш, A2-Z2).

Рис. 9. 3. Более эффективная реализация процедуры быстрсорт

с использованием разностного представления списков. Отношение

разбиение( Х, Спис, Меньш, Больш)определено, как на рис. 9.2.

быстрсорт2. Здесь, как и раньше, процедура быстрсортиспользует обычное представление списков, но в действительности сортировку выполняет более эффективная процедура быстрсорт2, использующая разностное представление. Эти две процедуры связаны между собой, соотношением

быстрсорт( L, S) :-

быстрсорт2( L, S-[ ] ).

Упражнения

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)для проверки принадлежности Х к L программируют так:

принадлежит X, [X | L] ).

принадлежит X, [ Y | L] ) :-

принадлежит( X, L).

Для того, чтобы найти Х в списке L, эта процедура последовательно просматривает список элемент за элементом, пока ей не встретится либо элемент X, либо конец списка. Для длинных списков такой способ крайне неэффективен.