Сортировка фактов

domains

ИмяЗаписи = string

НомерЗаписи, ЗначениеЗаписи = integer

МояЗапись=моя_запись(НомерЗаписи, ИмяЗаписи, ЗначениеЗаписи); пусто

database - мои_записи

мз(МояЗапись)

predicates

показать_мои_записи

значение_записи(МояЗапись,ЗначениеЗаписи)

запись_выбрать(МояЗапись З1, МояЗапись З2,

МояЗапись Вставить, МояЗапись Наверх)

запись_вставить(МояЗапись)

сортировка(МояЗапись Вниз, МояЗапись Вверх) - (i,o)

сортировка

откат

clauses

откат:-fail.

% взять значение записи

значение_записи(моя_запись(_,_,Значение),Значение):-!.

% выбрать какую запись добавить, а какую передать наверх

запись_выбрать(Запись1,пусто,пусто,Запись1):-!.

запись_выбрать(Запись1,Запись2,Запись1,Запись2):-

               значение_записи(Запись1,Значение1),

               значение_записи(Запись2,Значение2),

               Значение1>Значение2,

               !.

запись_выбрать(Запись1,Запись2,Запись2,Запись1):-

               !.

% вставить факт обратно в базу знаний

запись_вставить(пусто):-!.

запись_вставить(Запись):-

               asserta(мз(Запись)),

               !.

% сама сортировка

сортировка(ЗаписьВниз,ЗаписьНаверх):-

% выбрать запись из базы знаний

               retract(мз(Запись1)),

% определить какую из записей передать вниз,

% а какую возможно вставить в этом предикате

               запись_выбрать(ЗаписьВниз,Запись1,ЗаписьВниз1,ЗаписьВставить1),

% рекурсия сортировки вниз

               сортировка(ЗаписьВниз1,Запись2),

% определить какую запись вставить обратно в знания

% а какую передать наверх

               запись_выбрать(ЗаписьВставить1,Запись2,ЗаписьВставить,ЗаписьНаверх),

% выбранную запись на вставление - вставляем

               запись_вставить(ЗаписьВставить),

               !.

% конец фактов - запомним последний

сортировка(Запись,пусто):-

               запись_вставить(Запись),

               !.

показать_мои_записи:-

               мз(Запись),

               nl,write(Запись),

               откат.

показать_мои_записи:-!.

сортировка:-

               сортировка(пусто,Запись),

               запись_вставить(Запись),

               показать_мои_записи,

               !.

В базе знаний “проба.txt” содержатся факты в следующем виде и порядке:

мз(моя_запись(1,"я",23)).

мз(моя_запись(2,"ты",3)).

мз(моя_запись(3,"он",2)).

мз(моя_запись(4,"она",123)).

мз(моя_запись(5,"они",223)).

мз(моя_запись(6,"вы",213)).

мз(моя_запись(7,"кто",23)).

мз(моя_запись(8,"что",20)).

мз(моя_запись(9,"где",13)).

мз(моя_запись(10,"когда",12)).

мз(моя_запись(1,"я",5)).

мз(моя_запись(2,"ты",55)).

мз(моя_запись(3,"он",24)).

мз(моя_запись(4,"она",1)).

мз(моя_запись(5,"они",223)).

мз(моя_запись(6,"вы",33)).

мз(моя_запись(7,"кто",44)).

мз(моя_запись(8,"что",20)).

мз(моя_запись(9,"где",113)).

мз(моя_запись(10,"когда",4)).

Сначала нужно загрузить факты в память с помощью команды:

Goal consult("проба.txt",мои_записи).

После этого можно запускать сортировку фактов:

Goal сортировка. % отсортировать один раз

Надо заметить что сортировка за один раз не расставляет все факты полностью по возрастанию Значения факта: здесь предикат “сортировка” - это лишь одна итерация сортировки. Однако за одну итерацию сразу несколько фактов перемещаются на довольно длинное расстояние в списке фактов. После нескольких выполнений предиката “сортировка” факты будут полностью отсортированы. Дело в том, что чтобы оценить окончание сортировки нужно сделать дополнительный предикат, который бы перезапускал сортировку в случае не полной сортировки фактов.

Вот результаты сортировки входных фактов из файла “проба”:

Итерация 1.

моя_запись(4,"она",1)

моя_запись(2,"ты",3)

моя_запись(3,"он",2)

моя_запись(1,"я",23)

моя_запись(4,"она",123)

моя_запись(6,"вы",213)

моя_запись(7,"кто",23)

моя_запись(8,"что",20)

моя_запись(9,"где",13)

моя_запись(10,"когда",12)

моя_запись(1,"я",5)

моя_запись(2,"ты",55)

моя_запись(3,"он",24)

моя_запись(10,"когда",4)

моя_запись(5,"они",223)

моя_запись(6,"вы",33)

моя_запись(7,"кто",44)

моя_запись(8,"что",20)

моя_запись(9,"где",113)

моя_запись(5,"они",223)

Итерация 2.

моя_запись(4,"она",1)

моя_запись(3,"он",2)

моя_запись(2,"ты",3)

моя_запись(10,"когда",4)

моя_запись(1,"я",23)

моя_запись(4,"она",123)

моя_запись(7,"кто",23)

моя_запись(8,"что",20)

моя_запись(9,"где",13)

моя_запись(10,"когда",12)

моя_запись(1,"я",5)

моя_запись(2,"ты",55)

моя_запись(3,"он",24)

моя_запись(8,"что",20)

моя_запись(6,"вы",213)

моя_запись(6,"вы",33)

моя_запись(7,"кто",44)

моя_запись(9,"где",113)

моя_запись(5,"они",223)

моя_запись(5,"они",223)

Итерация 3

моя_запись(4,"она",1)

моя_запись(3,"он",2)

моя_запись(2,"ты",3)

моя_запись(10,"когда",4)

моя_запись(1,"я",5)

моя_запись(1,"я",23)

моя_запись(7,"кто",23)

моя_запись(8,"что",20)

моя_запись(9,"где",13)

моя_запись(10,"когда",12)

моя_запись(8,"что",20)

моя_запись(2,"ты",55)

моя_запись(3,"он",24)

моя_запись(6,"вы",33)

моя_запись(4,"она",123)

моя_запись(7,"кто",44)

моя_запись(9,"где",113)

моя_запись(6,"вы",213)

моя_запись(5,"они",223)

моя_запись(5,"они",223)

Итерация 4

моя_запись(4,"она",1)

моя_запись(3,"он",2)

моя_запись(2,"ты",3)

моя_запись(10,"когда",4)

моя_запись(1,"я",5)

моя_запись(10,"когда",12)

моя_запись(1,"я",23)

моя_запись(8,"что",20)

моя_запись(9,"где",13)

моя_запись(8,"что",20)

моя_запись(7,"кто",23)

моя_запись(3,"он",24)

моя_запись(6,"вы",33)

моя_запись(7,"кто",44)

моя_запись(2,"ты",55)

моя_запись(9,"где",113)

моя_запись(4,"она",123)

моя_запись(6,"вы",213)

моя_запись(5,"они",223)

моя_запись(5,"они",223)

Итерация 5

моя_запись(4,"она",1)

моя_запись(3,"он",2)

моя_запись(2,"ты",3)

моя_запись(10,"когда",4)

моя_запись(1,"я",5)

моя_запись(10,"когда",12)

моя_запись(9,"где",13)

моя_запись(8,"что",20)

моя_запись(8,"что",20)

моя_запись(1,"я",23)

моя_запись(7,"кто",23)

моя_запись(3,"он",24)

моя_запись(6,"вы",33)

моя_запись(7,"кто",44)

моя_запись(2,"ты",55)

моя_запись(9,"где",113)

моя_запись(4,"она",123)

моя_запись(6,"вы",213)

моя_запись(5,"они",223)

моя_запись(5,"они",223)

Как видно, на пятой итерации все факты полностью отсортированы. Об этом говорит сайт https://intellect.icu . Хотя можно было бы уже остановиться и на третьей итерации, ведь лучшие факты уже находились в начале базы знаний, а точность их сортировки не так и важна в данной задаче. Недостаток алгоритма в том, что если в фактах есть много записей с одинаковыми значениями, то сортировка каждый раз будет сдвигать такие факты на одно место вверх.

А вот более сложный алгоритм. Здесь устранен недостаток, описанный выше. И теперь одинаковые записи сортируются как одна запись: если две записи равны, то они собираются в список и далее путешествуют по сортировке вместе. Если далее встретится еще равная запись, то и она присоединится к списку. Таким образом, сортировка производится за несколько итераций вне зависимости от количества одинаковых фактов.

% пузырьки легкие всплывают, а тяжелые тонут

% а пузырьки одинаковые - цепляются к друг дружке

domains

ИмяЗаписи = string

НомерЗаписи, ЗначениеЗаписи = integer

МояЗапись=моя_запись(НомерЗаписи, ИмяЗаписи, ЗначениеЗаписи);

  мои_записи(МоиЗаписи); пусто

МоиЗаписи = МояЗапись*

database - мои_записи

мз(МояЗапись)

predicates

показать_мои_записи

значение_записи(МояЗапись,ЗначениеЗаписи)

запись_выбрать(МояЗапись З1, МояЗапись З2,

МояЗапись Вставить, МояЗапись Наверх)

запись_вставить(МояЗапись)

записи_вставить(МоиЗаписи)

сортировка(МояЗапись Вниз, МояЗапись Вверх) - (i,o)

сортировка

запись_выбрать_вниз(МояЗапись, МояЗапись, МояЗапись Вниз, МояЗапись)

запись_выбрать_вверх(МояЗапись, МояЗапись, МояЗапись, МояЗапись Вверх)

записи_сложить(МояЗапись,МояЗапись,МояЗапись) - (i,i,o)

clauses

% сложить две записи с одинаковым значением

записи_сложить(Запись1,Запись2,мои_записи([Запись1,Запись2])):-    !.

% взять значение записи

значение_записи(моя_запись(_,_,Значение),Значение):-!.

значение_записи(мои_записи([Запись|_]),Значение):

значение_записи(Запись,Значение),!.

% выбрать какую запись добавить, а какую передать далее

запись_выбрать(Запись1,Запись2,Запись1,Запись2):-

               значение_записи(Запись1,Значение1),

               значение_записи(Запись2,Значение2),

               Значение1Значение2,

               !.

запись_выбрать(Запись1,Запись2,Запись2,Запись1):-!.

% если записи равны, то их обоих нужно собрать в список и тащить вниз

запись_выбрать_вниз(Запись1,Запись2,ЗаписьВниз,пусто):-

               значение_записи(Запись1,Значение1),

               значение_записи(Запись2,Значение2),

               Значение1=Значение2,

               записи_сложить(Запись1,Запись2,ЗаписьВниз),

               !.

% если не равны, то обычное сравнение

запись_выбрать_вниз(пусто,Запись,Запись,пусто):-!.

запись_выбрать_вниз(Запись,пусто,Запись,пусто):-!.

запись_выбрать_вниз(Запись1,Запись2,ЗаписьВниз,ЗаписьВверх):-

               запись_выбрать(Запись1,Запись2,ЗаписьВниз,ЗаписьВверх),

               !.

% если записи равны, то их обоих нужно собрать в список и тащить вверх

запись_выбрать_вверх(Запись1,Запись2,пусто,ЗаписьВверх):-

               значение_записи(Запись1,Значение1),

               значение_записи(Запись2,Значение2),

               Значение1=Значение2,

               записи_сложить(Запись1,Запись2,ЗаписьВверх),

               !.

% если не равны, то обычное сравнение

запись_выбрать_вверх(Запись,пусто,пусто,Запись):-!.

запись_выбрать_вверх(пусто,Запись,пусто,Запись):-!.

запись_выбрать_вверх(Запись1,Запись2,ЗаписьВниз,ЗаписьВверх):-

               запись_выбрать(Запись1,Запись2,ЗаписьВниз,ЗаписьВверх),

               !.

% вставить список записей

записи_вставить([Запись|Записи]):-

               запись_вставить(Запись),

               записи_вставить(Записи),

               !.

записи_вставить([]):-!.

% вставить запись или список записей

запись_вставить(пусто):-!.

запись_вставить(мои_записи(Записи)):-

               записи_вставить(Записи),

               !.

запись_вставить(Запись):-

               asserta(мз(Запись)),

               !.

% сама  
                                                       сортировка фактов 

сортировка(ЗаписьВниз,ЗаписьНаверх):-

% вытащить текущий факт из базы

               retract(мз(Запись1)),

% посмотреть, что далее вниз пойдет

               запись_выбрать_вниз(ЗаписьВниз,Запись1,ЗаписьВниз1,ЗаписьВставить1),

% вызвать рекурсию сортировки (продолжим далее)

               сортировка(ЗаписьВниз1,ЗаписьНаверх1),

% посмотреть, что вернуть наверх, а что положить в базу знаний

               запись_выбрать_вверх(ЗаписьВставить1,

ЗаписьНаверх1,ЗаписьВставить,ЗаписьНаверх),

               запись_вставить(ЗаписьВставить),

               !.

% конец фактов - запомним последний

сортировка(Запись,пусто):-

               запись_вставить(Запись),

               !.

% для показа записей на экран

показать_мои_записи:-

               мз(Запись1),

               nl,write(Запись1),

               откат.

показать_мои_записи:-!.

% вызов сортировки

сортировка:-

               сортировка(пусто,Запись),

               запись_вставить(Запись),

               показать_мои_записи,

%            повторить,

               !.

вот результаты сортировки:

Итерация 1

Моя_запись(4,"она",1)

моя_запись(2,"ты",3)

моя_запись(3,"он",2)

моя_запись(1,"я",23)

моя_запись(4,"она",123)

моя_запись(6,"вы",213)

моя_запись(7,"кто",23)

моя_запись(8,"что",20)

моя_запись(9,"где",13)

моя_запись(10,"когда",12)

моя_запись(1,"я",5)

моя_запись(2,"ты",55)

моя_запись(3,"он",24)

моя_запись(10,"когда",4)

моя_запись(6,"вы",33)

моя_запись(7,"кто",44)

моя_запись(8,"что",20)

моя_запись(9,"где",113)

моя_запись(5,"они",223)

моя_запись(5,"они",223)

Итерация 2

моя_запись(4,"она",1)

моя_запись(3,"он",2)

моя_запись(2,"ты",3)

моя_запись(10,"когда",4)

моя_запись(1,"я",23)

моя_запись(4,"она",123)

моя_запись(7,"кто",23)

моя_запись(8,"что",20)

моя_запись(9,"где",13)

моя_запись(10,"когда",12)

моя_запись(1,"я",5)

моя_запись(2,"ты",55)

моя_запись(3,"он",24)

моя_запись(8,"что",20)

моя_запись(6,"вы",33)

моя_запись(7,"кто",44)

моя_запись(9,"где",113)

моя_запись(6,"вы",213)

моя_запись(5,"они",223)

моя_запись(5,"они",223)

Итерация 3

моя_запись(4,"она",1)

моя_запись(3,"он",2)

моя_запись(2,"ты",3)

моя_запись(10,"когда",4)

моя_запись(1,"я",5)

моя_запись(1,"я",23)

моя_запись(7,"кто",23)

моя_запись(8,"что",20)

моя_запись(9,"где",13)

моя_запись(10,"когда",12)

моя_запись(8,"что",20)

моя_запись(2,"ты",55)

моя_запись(3,"он",24)

моя_запись(6,"вы",33)

моя_запись(7,"кто",44)

моя_запись(9,"где",113)

моя_запись(4,"она",123)

моя_запись(6,"вы",213)

моя_запись(5,"они",223)

моя_запись(5,"они",223)

Итерация 4

моя_запись(4,"она",1)

моя_запись(3,"он",2)

моя_запись(2,"ты",3)

моя_запись(10,"когда",4)

моя_запись(1,"я",5)

моя_запись(10,"когда",12)

моя_запись(8,"что",20)

моя_запись(9,"где",13)

моя_запись(8,"что",20)

моя_запись(7,"кто",23)

моя_запись(1,"я",23)

моя_запись(3,"он",24)

моя_запись(6,"вы",33)

моя_запись(7,"кто",44)

моя_запись(2,"ты",55)

моя_запись(9,"где",113)

моя_запись(4,"она",123)

моя_запись(6,"вы",213)

моя_запись(5,"они",223)

моя_запись(5,"они",223)

Итерация 5

моя_запись(4,"она",1)

моя_запись(3,"он",2)

моя_запись(2,"ты",3)

моя_запись(10,"когда",4)

моя_запись(1,"я",5)

моя_запись(10,"когда",12)

моя_запись(9,"где",13)

моя_запись(8,"что",20)

моя_запись(8,"что",20)

моя_запись(1,"я",23)

моя_запись(7,"кто",23)

моя_запись(3,"он",24)

моя_запись(6,"вы",33)

моя_запись(7,"кто",44)

моя_запись(2,"ты",55)

моя_запись(9,"где",113)

моя_запись(4,"она",123)

моя_запись(6,"вы",213)

моя_запись(5,"они",223)

моя_запись(5,"они",223)

%

Вообще, есть классическая сортировка с помощью бинарных деревьев. Такая сортировка работает быстрее описанного выше метода. Но ее недостаток в том, что она выполняет полную сортировку до полного упорядочивания всех элементов списка. А предложенная мной сортировка делается не полностью, лишь увеличивая вероятность появления нужного факта в начале базы фактов ПРОЛОГа Мною была проведена тестовая оценка классической сортировки и предложенной:

Так для количества записей 100 в базе, классическая сортировка делает 800 сравнений, а предложенная в статье (за два прохода): 378. Для 400 записей, соответственно: 11600 и 1500 (за два прохода). Однако если учесть, что время на выполнение одного сравнения в предложенном методе уходит больше и количество проходов при увеличении записей возрастает, выгодность классического метода увеличивается. Вот классический пример сортировки на ПРОЛОГе:

% сортировка с использованием Reference Domains

% То есть когда значение предает как ссылка

% файл пример находится в ch11e04.pro к VIP5.5

% и показывает как использовать ссылочные значения

% в классической сортировке по методу бинарного дерева

/* Program ch11e05.pro */

DOMAINS

tree = reference t(val, tree, tree)

val  = integer

list = integer*

PREDICATES

insert(integer,tree)

instree(list,tree)

nondeterm treemembers(integer,tree)

sort(list,list)

CLAUSES

insert(Val,t(Val,_,_)):-!.

insert(Val,t(Val1,Tree,_)):-

                Val&gtVal1,

               !,

               insert(Val,Tree).

insert(Val,t(_,_,Tree)):-

               insert(Val,Tree).

instree([],_).

instree([H|T],Tree):-

               insert(H,Tree),

               instree(T,Tree).

treemembers(_,T):-

               free(T),

               !,

               fail.

treemembers(X,t(_,L,_)):-

               treemembers(X,L).

treemembers(X,t(Refstr,_,_)):-

               X = Refstr.

treemembers(X,t(_,_,R)):-

               treemembers(X,R).

sort(L,L1):-

% рассортировывает элементы списка в бинарное дерево

               instree(L,Tree),

% преобразовывает бинарное дерево обратно в список

               findall(X,treemembers(X,Tree),L1).

GOAL

               sort([3,6,1,4,5],L),

               write("L=",L),nl.

% Здесь значения-ссылки используются только в домайне tree