Средства разработки приложений


Prolog_facts.shtml - часть 5


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

Так для количества записей 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

 


Начало  Назад  Вперед



Книжный магазин