Učinkovitost

Članek govori o izboljševanju učinkovitosti v programskem jeziku Prolog.

Prolog je prostorsko neučinkovit ker shranjuje vse podatke višje v drevesu na sklad. Učinkovitost lahko izboljšamo z različnimi mehanizmi:

assert, retract

Assert in retract lahko uporabljamo za shranjevanje že izračunanih zadev. Potem že izračunane podatke lahko uporabljamo iz naše baze znanja ki nastaja sproti.

Rez

Omogoča kontrolo avtomatskega vračanja. Če vemo da neko avtomatsko vračanje ni potrebno vračanje lahko "odrežemo" z rezom ( zapisan kot ! )

repeat, fail

Simulacija iteracije, ker je rekurzija potratna zadeva. Izplača se nam zato ker v iteraciji ne zasedamo sklada.

Razlika dveh seznamov

Kako hitro dostopati do konca seznama?

[a,b,c,d|X]-X

X

kazalec na konec seznama

Običajni način - prehodimo cel seznam, da pridemo do repa

dodaj_konec(Element,[],[Element]).
dodaj_konec(Element,[G|Rep],[G|Rep1]):-
  dodaj_konec(Element,Rep,Rep1).

Hitrejši način, vemo že kje je rep, zato ga lahko uporabimo

[a,b,c] [a,b,c|X]-X
[]      X-X
%dodaj_hitro(Seznam-X,Element,Novi_seznam-Y)
dodaj_hitro(Seznam-[Element|Y],Element,Seznam-Y).

?- dodaj_hitro([a,b,c|X]-X,d,Novi).
X = [d|Y]
Novi = [a,b,c,d|Y]-Y

Stik 2 seznamov

%stik(Sez1,Sez2,Novi seznam)
stik(Sez1-Raz1,Raz1-Raz2,Sez1-Raz2).

?- stik([a,b,c|X]-X, [d,e,f,g|Y]-Y, Novi).
X = [d,e,f,g|Y]
Novi = [a,b,c,d,e,f,g|Y]-Y

Obračanje seznama

obrnir([],X-X).  %X-X je prazen seznam
obrnir([G|Rep],Sez):-
  obrnir(Rep,S1),
  stik(S1,[G|X]-X,Sez).

FIFO Vrsta

(z ene strani gredo podatki v vrsto in na drugi strani ven)

potrebujemo hitri dostop do konca seznama

dodaj_vrsta(E,Vrsta-[E|Y],Vrsta-Y).

vzemi_vrsta([E|Vrsta]-X,E,Vrsta-X).

?- dodaj_vrsta(f,[a,b,c,d,e|X]-X,Nova).
X = [f|Y]
Nova = [a,b,c,d,e,f|Y]-Y

?- vzemi_vrsta([a,b,c,d,e,f|X]-X,E,Nova).
E = a
Nova = [b,c,d,e,f|Y]-X

?- vzemi_vrsta(X-X,E,Nova).
X = [E|Y]
Nova = Y-[E|Y]

Vrstni red

• stavkov znotraj procedure
• ciljev v telesu stavka

Vrstni red vpliva na izvajanje ker lahko drevo preiskujemo na različne načine.

Več enosmernih procedur namesto ene večsmerne

Preverjanje operatorjev

• atom(X)

X je atom

• number(X)

X je število

• atomic(X)

X je konstanta (atom ali število)

• var(X)

X je neopredeljena spremenljivka

• nonvar(X)

X ni neopredeljena spremenljivka

naslednik_hiter(Nasl,Pred):-
  otrok(Nasl,Pred).
naslednik_hiter(Nasl,Pred):-

naslednik_hiter(Nasl,Pred):-
 

naslednik_najhitrejsi(Nasl,Pred):-
  atom(Pred),!, %prednik je podan
  naslednik2(Nasl,Pred). %išče navzdol
naslednik_najhitrejsi(Nasl,Pred):-
  naslednik1(Nasl,Pred). %išče navzgor