Prolog spartos analizė Spausdinti
( 0 Votes )
Parašė Aurimas Šimkus   

Viena iš svarbiausių programavimo kalbos charakteristikų - programų vykdymo laikas. Atlikome nedidelį tyrimą, Prolog kalbos vykdymo laikui nustatyti ir palyginti su kitomis populiariomis kalbomis.

Buvo lyginamos šios programavimo kalbos:

  • C++ (kompiliatorius - VS10) - pasirinkta, kaip etalonas. Kompiliuojama kalba.
  • Python (interpretatorius - Python 2.7.1) - viena populiariausių interpretuojamų kalbų.
  • Prolog (interpretatorius - SWI-Prolog 6.2.2) - vienas populairiausių Prolog interpretatorių, naudojamas ir mūsų pamokose.
  • Prolog (interpretatorius - SICStus 4.2.3) - komercinis, vienas greičiausių Prolog interpreatorių ir kompiliatorių.

Taip pat buvo lyginama ir kompiliuota Prolog programos versija (SICStus).

 

Pasirinkta nagrinėti greito rikiavimo algoritmą. Iškart pabrėžiame, kad tokia programa turbūt nėra viena iš esminių loginio programavimo kalbos sričių. Ji buvo pasirinkta, norint įvertinti kalbos efektyvumą atliekant rekursines operacijas. Tiek C++, tiek Python, tiek Prolog kalbų variantai buvo realizuoti panaudojant rekursiją. Programą sudaro trys funkcijos: pagrindinė "rikiuoti(N)", kur N - elementų skaičius. Iš jos kreipiamasi į funkciją "sarasas", kuri sugeneruoja N sveikųjų skaičių iš intervalo [1 1000000]. Tada nuimamas atskaitos laikas T1 ir vykdomas sugeneruoto skaičių rinkinio rikiavimas - "q_sort". Po rikiavimo paimamas pabaigos laiaks T2 ir apskaičiuojama vykdymo trukmė T=T2-T1. Buvo lyginam programos vykdymo laikai rikiuojant 1000, 10000, 100000, 200000, 500000 ir 1000000 elementų.

Gauti programinį kodą 

 

Tyrimas buvo atliktas naudojant šių specifikacijų kompiuterį:

  • Procesorius -                       Intel E6750 @ 2.66GHz
  • Operatyvioji atmintis (RAM) - 2x 1GB @ 800MHz
  • Operacinė sistema -             MS Windows 7 32bit 

 

Tyrimo rezultatai

Rezultatatų lentelė, duomenys pateikti sekundėmis:

  1000 el. 10000 el. 100000 el. 200000 el. 500000 el. 1000000 el.
C++             0 0 0,02 0,04 0,09 0,18
Python 0 0,06 0,72 1,55 4,25 9,49
SWI-Prolog 0 0,14 2,67 Fail Fail Fail
Sictus 0 0,11 1,45 3,23 Fail Fail
Sictus Compiled 0 0,02 0,2 0,4 1,1 Fail


Matome, kad C++ be konkurencijos buvo greičiausia. Antra liko ir nuo C++ daugiau nei 10 kartų atsiliko kompiliuota Prolog versija. Tai yra labai geras rezultatas prolog kalbai. Tačiau nei vienas Prolog variantas nesugebėjo surikiuoti 1000000 elementų masyvo (žym. fail) - taip nutiko dėl rekursijos metu išnaudojamos ir nebeužtenkamos vykdomosios atminties. Trečioje vietoje liko Python kalba, tačiau sugebėjo surikiuoti visų bandytų dydžių sekas. Interpretuojamosioms Prolog versijoms sekėsi prasčiausiai. Blogiausiai pasirodė SWI-Prolog, daugiausiai sugebėjusi surikiuoti 100000 el. Ji nuo SICStus varianto atsilikiniejo 30-80%, nuo Python - 2-4 kartus.

 

Grafikas, vizualizuojantis logaritmuotus rezultatus:

Prolog prieš Pyhon, prieš C++

Logaritminis grafikas geras tuo, nes suartina didelius ir mažus skirtumus, taigi lengviau interpretuoti netolygiai besiskiriančius dydžius. Atkreipkite dėmesį, kad kuo platesnė kalbos kreivė - tuo daugiau elementų jai pavyko surikiuoti. Taip pat, kuo ji žemesnė - tuo rikiavimas buvo greitesnis. Be to, kuo kreivė tiesesnė, tuo rikiavimas (programos veikimas) stabilesnis. Matome, kad C++ žymiai priekyje. Kompiliuota Prolog versija pasirodė gerai, tačiau jos veikimas nėra stabilus. Toliau attinkamai išsirikiuoja Pyhon, SICStus ir SWI-Prolog.

 

Išvados

  • Kadangi Python programos paprastai naudoja rekursiją, jos gali turėti bėdų su labai dideliais duomenų kiekiais analizuojamais rekursijoje (didelis rekursijos gylis).
  • Prolog turėtų būti pakankamai sparti loginiams daug rekursijos išteklių nereikalaujantiems uždaviniams.
  • Interpretuojamos Prolog programos per daug neatsilieka nuo tokių interpretuojamų kalbų kaip Python, taigi gali konkuruoti.
  • Kompiliuojamos Prolog programos yra greitesnės už Python ir ne per daug atsilieka nuo C++, taigi gali būti naudojamos ir našioms programoms realizuoti.
  • Komercinis SICStus Prolog variantas yra ~50% greitesnis už nemokamą SWI-Prolog interpretatorių.