% Egy érdekes Prolog feladat % ========================== % felreforditasa(+L, -FL): % Az L lista 2n elemű. Az ebből előállítandó FL lista szintén 2n elemű, % első n eleme megegyezik az L első n elemével, hátsó n eleme az L utolsó n % eleméből álló lista megfordítása. % Egy, a lists könyvtárat használó n^2-tel arányos lépésszámú lehetséges % megoldás (a kommentekben ++ két lista összefűzését jelöli). felreforditasa(L, F) :- append(Eleje, Vege, L), % Eleje ++ Vege = L, same_length(Eleje, Vege), % Eleje és Vege azonos hosszúak reverse(Vege, FordVege), % FordVege Vege megfordítása append(Eleje, FordVege, F). % Eleje ++ FordVege = F % Írjon olyan Prolog programot, amely ezt a feladatot egy 2n hosszúságú % bemenetre n+c redukciós lépésben (azaz ennyi eljáráshívással) oldja meg, % ahol c egy konstans. % A végső cél az, hogy a megoldás teljesítse az alábbi ún. *erős* % feltételeket: összesen 3 (azaz három) klózból álljon, ne használjon sem % beépített, sem könyvtári eljárást (még vágót sem), továbbá se diszjunkció % se feltételes szerkezet ne legyen benne. % Érdemes lehet először egy *gyengített* feltételrendszer melletti % megoldáson gondolkozni. Ebben nem korlátozzuk a klózok számát, és % megengedjük a következő beépített predikátumokat: = /2, length/2, !/0, % is/2, valamint az aritmetikai összehasonlító eljárásokat: < /2, =< /2, % =:= /2 stb. Ezek hívásai nem számítanak redukciós lépésnek. Diszjunkció % és feltételes szerkezet is használható. % Két fontos megjegyzés % --------------------- % 1. megjegyzés: A redukciók számának csökkentésére elvben lehetne % használni a redukciós lépések összevonásának módszerét. Erre példa az % append/3 eljárás alábbi változata, amely egyszerre 5 elemet dolgoz fel % (ez csak összefűzésre használható, szétszedésre nem): app5([], L, L). app5([A,B,C,D,E|L1], L2, [A,B,C,D,E|L3]) :- !, app5(L1, L2, L3). app5([A|L1], L2, [A|L3]) :- app5(L1, L2, L3). % Az app5/3 eljárás a közönséges appendhez képest ötödannyi redukciós % lépést hajt végre. Ha 5 elem helyett k elemet kezelünk egy redukciós % lépésben, akkor a redukciós lépések számát k-ad részére lehet csökkenteni. % Következésképpen, ha ezt a módszert a kitűzött feladatban megengedjük, % akkor a lépések számát nemcsak n-re, hanem n/k-ra is lehetne csökkenteni, % ahol k tetszőlegesen nagy adott szám. % Jelen feladat megoldásában az összevonásos módszer alkalmazását nem % engedjük meg. Fontos megjegyezni, hogy az önmagában nem gond, ha egy % redukciós lépésben egy lista elejéről két vagy több elemet leveszünk. Ez % csak akkor baj, ha ezt abból a célból tesszük, hogy két vagy több % redukciós lépést egyetlen lépésbe összevonjunk. % 2. megjegyzés: Egy Prolog redukciós lépés futási ideje nem feltétlenül % korlátos. Ha L1 és L2 két k hosszúságú, azonos elemekből álló lista, % akkor az L1 = L2 hívás futtatása k-val arányos idejű (lásd a fájl végén a % (=)/2 jelű futtatás időmérését). Így, annak ellenére, hogy egy Prolog % hívás n redukciós lépésben lefut, futási ideje lehet n^2-tel arányos, % vagy akár még ennél is nagyobb. % Ezért fontos kikötnünk, hogy felreforditasa/2 eljárás futási ideje a % bemeneti lista hosszával legyen arányos. % Az alábbiakban a felreforditasa eljaras néhány további megvalósítását, % egy időmérést végző segédeljárást (stat/3), valamint a % példa-megvalósítások tesztelését végző eljárásokat mutatjuk be. % A program a SICStus és SWI Prolog rendszerekben is futtatható. % A fájl végén találhatók futási példák, időméréssel. :- use_module(library(lists)). felreforditasa1(L, F) :- length(L, Len), Len mod 2 =:= 0, N is Len//2, length(Eleje, N), append(Eleje, Vege, L), reverse(Vege, ForditottVege), append(Eleje, ForditottVege, F). felreforditasa2(L, F) :- length(L, Len), Len mod 2 =:= 0, N is Len//2, replace_tail(N, L, Vege, F, VegeF), reverse(Vege, VegeF). % replace_tail(+N, ?OldList, ?OldTail, ?NewList, ?NewTail): % OldList és NewList első N eleme megegyezik, % OldList első N elemének elhagyása után OldTail marad, % NewList első N elemének elhagyása után NewTail marad. % Egy átfogalmazás: % Létezik egy olyan L N-elemű lista, hogy: % OldList = L ++ OldTail, és NewList = L ++ NewTail. % Futási példák: % | ?- replace_tail(2, [a,b,c], OldT, NewL, NewT). % OldT = [c], % NewL = [a,b|NewT] ? ; % no % | ?- replace_tail(2, OldL, OldT, NewL, NewT). % OldL = [_A,_B|OldT], % NewL = [_A,_B|NewT] ? ; % no replace_tail(0, OldList, OldTail, NewList, NewTail) :- !, OldList = OldTail, NewList = NewTail. replace_tail(N, [H|L], OldTail, [H|NL], NewTail) :- N1 is N-1, replace_tail(N1, L, OldTail, NL, NewTail). % Futási idő jelentést készít a Pred eljárás M hosszúságú listával való % Rep-szeres futtatásáról. stat(Pred, Rep, M) :- statistics(runtime, [_,T0]), % T0 a megelőző statistics(runtime, _) hívás % óta eltelt CPU idő, ezredmásodpercekben T is T0*1000//Rep, prolog_flag(dialect, D0), dialect_name(D0, D), format('\nPred ~|~w,~t~16+ len =~|~t~w~9+, ~w time:~|~t~3d~10+ msec', [Pred,M,D,T]). % dialect_name(System, Name): a System nevű Prolog rendszer megjelenítendő % neve Name. dialect_name(sicstus, 'SICStus'). dialect_name(swi, 'SWI'). :- ( prolog_flag(dialect, sicstus) -> use_module(library(between)) ; set_prolog_flag(stack_limit, 2147483648) ). % repeat(Test, Rep): A Test fajtájú eljárást SICStusban Rep-szer futtatjuk. repeat(ff, 50). repeat(unify, 100). % repeat_times(Test, Rep): A Test fajtájú eljárást Rep-szer futtatjuk. repeat_times(Test, Rep) :- repeat(Test, Rep0), ( prolog_flag(dialect, sicstus) -> Rep = Rep0 ; Rep is Rep0//10 % Mivel az SWI Prolog átlagosan kb. 7-szer lassabb, % a futtatások számát tizedére csökkentjük. ). % A felreforditasa feladatot megvalósító kétargumentumú Pred eljárást % 2N hosszú listára futtatja, és erről jelentést készít. run_ff(N, Pred) :- M is 2*N, numlist(1, M, L), repeat_times(ff, Rep), % Rep az ismételt futások száma statistics(runtime, _), % Nullázzuk a relatív időmérést ( between(1, Rep, _), % Rep-szer sikerül call(Pred, L, _), fail % meghiúsulásos ciklus folytatása ; stat(Pred, Rep, M) ). % Két azonos, N hosszú lista egyesítését futtatja, % és erről jelentést készít. run_unify(N) :- numlist(1, N, L1), numlist(1, N, L2), repeat_times(unify, Rep), statistics(runtime, _), ( between(1, Rep, _), L1=L2, fail ; stat(= /2, Rep, N) ). % Jelentést készít a felreforditasa feladatot megvalósító eljárások % időigényéről. run_felreforditasa :- ( member(N, [2000,4000,8000,16000]), run_ff(N, felreforditasa), fail ; nl, member(N, [100000,1000000,10000000]), run_ff(N, felreforditasa1), fail ; nl, member(N, [100000,1000000,10000000]), run_ff(N, felreforditasa2), fail ; true ). % Jelentést készít két azonos lista egyesítésének időigényéről. run_unify :- ( member(N, [100000,1000000,10000000]), run_unify(N), fail ; true ). run_all :- run_unify, nl, nl, run_felreforditasa. end_of_file. % A futtatások Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz processzoron, % SICStus 4.5.0 ill. SWI 8.2.2 Prolog rendszerekkel készültek. (=)/2, len = 100000, SWI: 2.700 msec, SICStus: 0.920 msec (=)/2, len = 1000000, SWI: 27.900 msec, SICStus: 9.500 msec (=)/2, len = 10000000, SWI: 283.100 msec, SICStus: 94.980 msec felreforditasa, len = 4000, SWI: 192.200 msec, SICStus: 10.580 msec felreforditasa, len = 8000, SWI: 765.000 msec, SICStus: 41.780 msec felreforditasa, len = 16000, SWI: 3072.200 msec, SICStus: 165.800 msec felreforditasa, len = 32000, SWI: 12260.600 msec, SICStus: 658.380 msec felreforditasa1, len = 200000, SWI: 24.600 msec, SICStus: 4.020 msec felreforditasa1, len = 2000000, SWI: 247.800 msec, SICStus: 42.140 msec felreforditasa1, len = 20000000, SWI: 2648.200 msec, SICStus: 451.580 msec felreforditasa2, len = 200000, SWI: 20.000 msec, SICStus: 2.920 msec felreforditasa2, len = 2000000, SWI: 201.000 msec, SICStus: 30.320 msec felreforditasa2, len = 20000000, SWI: 2012.800 msec, SICStus: 301.680 msec