Быстрая сортировка - это более сложный метод сортировки, предложенный Хоором и применимый для сортировки больших списков. Для реализации быстрой сортировки на Прологе мы должны сначала разделить список, состоящий из головы Н и хвоста Т, на два списка L и М такие, что:
• все элементы L меньше или равны Н;
• все элементы М больше чем Н;
• порядок следования элементов в L и М такой же как в [Н |Т].
После того, как мы разделили список, применяем быструю сортировку к каждому из полученных списков (это рекурсивная часть), и присоединяем М к L Цель разбить(H,T,L,M) разделяет список [Н |Т] на списки L и М, как сказано выше:
paзбить(H,[A|X],[A|Y],Z):- А=‹ Н, разбить(Н,Х,Y,Z).
разбить(Н,[А|Х],Y,[А|Z]):- А › Н, разбить(Н,Х,Y,Z).
разбить(_,[], [],[]).
Тогда программа быстрой сортировки примет вид:
бысорт([],[]).
бысорт([H|T],S):-разбить(Н,Т,А,В),бысорт(А,А1),бысорт(В,В1), присоединить(А1, [H|B1],S).
Предикат присоединить можно встроить внутрь программы сортировки. Тогда получается другой предикат
бысорт2 ([H|T], S,X):-разбить(Н,T,А,В), бысорт2(А,S,[Н|Y]), бысорт2(B,Y,X).
бысорт2([],Х,Х).
В этом случае третий аргумент используется как временная рабочая область, и при обращениях к бысорт2 этот аргумент должен заполняться пустым списком.
Более подробные сведения о методах сортировки можно найти в книге D. Knuth, The Art of Computer Programming, v. 3 (Sort and Searching), Addison-Wesley, 1973 (Имеется перевод: Кнут Д. Искусство программирования для ЭВМ, т. 3 (Сортировка и поиск). М.: Мир, 1978.- Перев.) Метод быстрой сортировки Хоора описан в его статье в Computer Journal n. 5 (1962), стр. 10-15.
Упражнение 7.5. Проверьте, что предикат перестановка (L1, L2) строит все перестановки заданного списка L1 (причем каждую по одному разу) и выдает их как альтернативные значения списка L2. В каком порядке строятся эти решения?
Упражнение 7.6. Быстрая сортировка лучше всего работает ка больших списках, поскольку там она обеспечивает более быструю сходимость к решению. В то же время объем работы, выполняемой на каждом уровне рекурсии быстрой сортировки, превышает то, что делается в других методах, из-за использования разбить. Поэтому, при сортировке небольших списков рекурсивные вызовы бысорт, видимо, можно заменить обращениями к другим методам сортировки, например, к сортировке включением. Разработайте «гибридную» программу, которая использует быструю сортировку для обработки больших подсписков (списков, полученных с помощью предиката разбить), но переключается на другой метод (сортировка включением) при значительном уменьшении длины подсписка. Подсказка: поскольку разбить должен просмотреть все элементы списка, то он может заодно подсчитать и длину списка.
7.8. Использование базы данных: random, генатом, найтивсе
Во всех программах, которые рассматривались до сих пор, база данных использовалась лишь для хранения фактов и правил, с помощью которых определяются предикаты. Можно использовать базу данных и для хранения обычных структур, т. е. таких, которые порождаются при выполнении программы. До сих пор для передачи таких структур от одного предиката к другому мы применяли механизм аргументов. Однако существуют доводы в пользу хранения этой информации в базе данных. Иногда некоторый элемент информации может потребоваться во многих частях программы. Передача его через механизм аргументов может привести к появлению одного – двух дополнительных аргументов у большинства предикатов. Другим доводом является возможность сохранения информации при возвратном ходе. В этом разделе мы рассмотрим три предиката, которые позволяют хранить в базе данных структуры, время жизни которых превышает то, что может быть обеспечено с помощью переменных. Вот эти три предиката: random, вырабатывающий при каждом вызове псевдослучайное целое, найтивсе, порождающий список всех структур, обеспечивающих истинность данного предиката, и генатом, порождающий атомы с различающимися именами.
Генератор случайных чисел (random)
Цель random(R, N) конкретизирует N целым числом, случайно выбранным в диапазоне от 1 до R. Метод выбора случайного числа основан на конгруэнтном методе с использованием начального числа («затравки») инициализируемого произвольным целым числом. Каждый раз, когда требуется случайное число, ответ вычисляется на основе существующего начального значения, и при этом порождается новое начальное число, которое сохраняется до тех пор, пока вновь не потребуется вычислить случайное число. Для хранения начального числа между вызовами random мы используем базу данных. После того как начальное число использовано, мы убираем (с помощью retract) из базы данных старую информацию о начальном числе, вычисляем его новое значение, и засылаем в базу данных новую информацию (с помощью asserta). Исходное начальное значение – это просто факт в базе данных, с функтором seed имеющим одну компоненту – целое значение начального числа.
seed(13).
random (R,N):-seed(S),N is (S mod R) + 1,retract(seed(S)),NewSeed is (125 * S + 1) mod 4096,asserta(seed(NewSeed)),!.
Используя семантику retract можно упростить определение random следующим образом:
random(R,N):-retract(seed(S)),N is (S mod R)+1,NewSeed is (125 * S +1) mod 4096,asserta(seed(NewSeed)),!.
Для того, чтобы напечатать последовательность случайных чисел, расположенных в диапазоне между 1 и 10, которая обры-вается после того, как будет порождено значение 5, нужно задать следующий вопрос:
?- repeat, random(10,X), write(X), nl, X=5.
Генератор имен (генатом)
Предикат генатом позволяет порождать новые атомы Пролога. Если у нас есть программа, которая воспринимает информацию об окружающем мире (например, путем анализа описывающих его предложений на английском языке), то в случае появления в этом мире нового объекта возникают трудности с его обозначением. Естественно представлять объект атомом Пролога. Если объект ранее не встречался, мы должны убедиться в том, что тот атом, который мы ему сопоставляем, случайно не совпал с другим атомом, уже представляющим какой-то другой объект. Иными словами, нам необходимо иметь возможность формировать новые атомы. Мы можем также потребовать, чтобы созданный атом имел также некоторое мнемоническое значение: это облегчит понимание информации выводимой нашей программой. Если бы атомы представляли, скажем, студентов, то целесообразно было бы назвать первого студента – студент1, второго – студент2, третьего – студентЗ и т. д. Если к тому же нам нужно было бы работать с объектами представляющими еще и преподавателей, то можно было бы выбрать для их представления атомы преподаватель1, преподаватель2, преподавательЗ и т. д.
Функция программы генатом состоит в том, чтобы порождать новые атомы от заданных корней (таких как студент и преподаватель). Для каждого корня программа запоминает, какой номер был использован в последний раз. Поэтому, когда в следующий раз от нее требуется породить атом с данным корнем можно гарантировать, что он будет отличаться от тех, что были порождены ранее. Так, когда вопрос
?- генатом(студент,X).
задан впервые, ответом будет
X = студент1
В следующий же раз ответом будет
X = студент2
и т. д.
Заметим, что эти различающиеся решения при возвратном ходе не порождаются (генатом(Х, Y) нельзя согласовать вновь), они порождаются последующими целями, включающими этот предикат.
В определении генатом используется вспомогательный предикат тек_номер. Контроль за тем, какой номер использовать следующим для данного корня, осуществляется программой генатом путем записи в базу данных фактов вида тек_номер и удаления фактов, которые стали ненужными. Факт тек_номер (Корень, Номер) означает, что последний номер, использованный с корнем Корень, был Номер. Иными словами, последний атом, порожденный для этого корня, состоял из литер, взятых из Корень, за которыми был приформирован номер, взятый из Номер. Когда Пролог пытается доказать согласованность цели генатом, обычно делается следующее: последний факт тек_номер для заданного корня удаляется из базы данных, к его номеру прибавляется 1, и новый факт тек_номер запоминается в базе данных, заменяя исключенный факт. С этого момента новый номер может быть использован как основа для порождения нового атома. Хранить информацию о текущем номере в базе данных очень удобно. В противном случае каждый предикат, прямо или косвенно участвующий в выполнении генатом, должен был бы пересылать информацию о текущих номерах через дополнительные аргументы.
