Algoritamska efikasnost

U računarskoj nauci, algoritamska efikasnost je svosjtvo algoritma koje je povezano sa količinom računarskih resursa koje algoritam koristi. Algoritam mora biti analiziran da bi se odredilo njegovo korišćenje resursa. Algoritamska efikasnost može biti zamišljena i kao analogna sa inžinjerskom produktivnošću tokom ponavljanog ili kontinualnog procesa.

Za maksimalnu efikasnost želimo da minimiziramo korišćenje resursa. Međutim, različiti resursi (npr. vreme, prostor) ne mogu biti poređeni direktno, tako da to koji je od dva algoritma efikasniji često zavisi od toga koja mera za efikasnost je najvažnije, npr. potreba za velikom brzinom, minimalnim korišćenjem memorije ili neka druga mera.

Obratite pažnju da ovaj članak nije o optimizaciji, koja je diskutovana u programskoj optimizaciji, optimizaciji kompajlera, optimizaciji petlje itd. Termin "optimizacija" je sama po sebi zbunjujuća, jer sve to generalno može da se zamisli kao "poboljšanje".

Pozadina

Važnost efikasnosti je u prošlosti naglasila Ada Lavlejs 1843. primenom mehaničkog analitičkog motora Čarlsa Bebidža:

"U skoro svakom računanju moguća je velika raznolikost uređenja nasledstva procesa, i različita razmatranja moraju da utiču na selekciju među njima za svrhe računajućeg motora. Jedan važni objekat je biranje uređenja koje teži da smanji minimalno vreme potrebno za završavanje računice.

Stari elektronski računari su vrlo ograničeni i od strane brzine operacija i količine dostupne memorije. U nekim slučajevima je uviđeno da postoji prostor-vreme razmena, pri čemu zadatak može biti rešen korišćenjem brzog algoritma koji zauzima prilično puno memorije, ili korišćenjem sporog algoritma koji koristi vrlo malo radne memorije. Inžinjerska razmena je onda bila da se koristi najbrži algoritam koji bi stao u dostupnu memoriju. Moderni računari su mnogo brži od ranih računara, i imaju mnogo veću količinu dostupne memorije (gigabajte umesto kilobajta). Ipak, Donald Knut je naglasio da je efikasnost i dalje važna za razmatranje:

"U utvrđenim inžinjerskim disciplinama 12% poboljšanja, lako dobijenih, nikada nije smatrano marginalnim i ja verujem da isti način gledanja treba da bude primenjen u softverskom inžinjerstvu"

Pregled

Algoritam se smatra efikasnim ako njegova potrošnja resursa (ili računska vrednost) na ili ispod nekog prihvatljivog nivoa. Grubo rečeno, "prihvatljivih" znači: radiće razumno mnogo vremena na dostupnom računaru. Od 1950-ih kompjuteri su doživeli dramatično povećanje dostupne računarske moći i dostupne memorije, tako trenutni prihvatljivi nivoi bi bili neprihvatljivi čak i pre 10 godina.

Proizvođači kompjutera često donose nove modele, često sa boljim performansama. Cene softvera mogu biti vrlo visoke, tako da je u nekim slučajevima najjednostavniji i najjeftiniji način da se dobiu bolje performanse da se kupi brži računar, uz obezbeđenje da je kompatibilan sa postojećim računarom.

Postoji mnogo načina merenja koliko algoritam koristi resursa: dva najčešća merenja su brzina i korišćenje memorije; druga merenja bi mogla da uključuju brzinu prenosa, privremeno korišćenje diska, dugoročno korišćenje diska, potrošnja energije, cena posedovanja, vreme reagovanja na spoljašnje stimulacije, itd. Mnoge od ovih merenja zavise od veličine unosa u algoritam (npr. količina podataka koji treba da se procesuiraju); mogu takođe da zavise od načina na koji su podaci raspoređeni (npr. neki algoritmi za sortiranje se loše pokazuju na podacima koji su već sortirani, ili koji su sortirani u obrnutom redosledu).

U praksi, postoje drugi faktori koji utiču na efikasnost algoritma, kao što su zahtevi za preciznošću i/ili pouzdanošću. Dole objašnjen, način na koji je algoritam implementiran može imati veliki efekat na efikasnost, kroz mnogo aspekata ovo je povezano sa problemima optimizacije.

Teoretske analize

U teoretskoj analizi algoritama, normalna praksa je da se proceni njihova kompleksnost u asimptotskom smislu, npr. korišćenje notacije veliko O da se reprezentuje kompleksnost algoritma kao funkcije sa ulazom veličine n. Ovo je generalno dovoljno precizno kada je n veliko, ali može biti sputavajuće za male vrednosti n (npr. babl sort može biti brži od kviksorta kada samo nekoliko stvari treba da se sortira).

Neki primeri velikog O uključuju:

Notation	Name	Examples
$O(1)\,$	konstantno	Proveravanje da li je broj prav ili prost; korišćenjem tabele konstantne veličine; korišćenjem odgovarajuće heš funkcije za traženje.
$O(\log n)\,$	logaritamsko	Traženje u sortiranom nizu sa binarnim pretraživanjem ili balansirano pretraživačko drvo kao i sve operacije u binomialnoj gomili.
$O(n)\,$	linearno	Traženje u nesortiranoj listi ili nepravilnom drvetu (najgori slučaj) ili u nesortiranom nizu; Sabiranje dva n-bitna cela broja sa ripl kerijem.
$O(n\log n)\,$	loglinearno ili kvazilinearno	Izvođenje brze Furijeve transformacije;hipsort, kviksort (najbolji i prosečni slučaj), ili mrdžsort.
$O(n^{2})\,$	kvadratno	Množenje dva n-tocifrena broja jednostavnim algoritmom; babl sort (najgori slučaj ili naivna implementacija), šelsort, kviksort (najgori slučaj), selekšn sort ili inseršn sort.
$O(c^{n}),\;c>1$	eksponencijalno	Traženje egzaktnog rešenja problema putujućeg trgovca korišćenjem dinamičkog programiranja; određivanje da li su dve logičke izjave ekvivalentne korišćenjem brut fors pretraživanja.

Testiranje: merenje performansi

Za nove verzije ili da se omogući poređenje kompetitivnih sistema, testiranje se ponekad koristi, koji asistiraju sa merenjem algoritamskih relativnih performansi. Ako se na primer proizvede novi algoritam za sortiranje može biti upoređen sa svojim precima da bi se osiguralo da je efikasan kao i ranije sa poznatim podacima- uzimajući u obzir sva funkcionalna poboljšanja. Testiranja mogu da koriste mušterije kada upoređuju različite proizvode alternativnih dobavljača da bi procenili koji proizvod će najbolje da odgovara njihovim potrebama u smislu funkcionalnosti i performansi. Na primer u glavnom delu svetskog vlasništva produkata za sortiranje u nezavisnim softverskim kompanijama kao što je Sinksort se takmiče sa produktima koje dobavljaju veliki dobavljači kao što je IBM za brzinu.

Neka testiranja obezbeđuju prilike za proizvođenje analize koja upoređuje relativnu brzinu različitih sastavljenih i interpretiranih jezika na primer i The Computer Language Benchmarks Game upoređuje performanse implementacija tipičnih programerskih problema u nekoliko programskih jzika.

(Čak i stvaranje "uradi sam" testiranja da bi se dobila makar neka zahvalnost relativnih performansi različitih programskih jezika, korišćenjem različitih kriterijuma specificiranih od strane korisnika, je lako da se proizvede "okupljanje grupe devet performansnih jezika" od Kristofera Kovela demonstrira na primeru)

Problemi implementacije

Problemi impementacije mogu da imaju efekat na efikasnost, kao što je izbor programskog jezika, ili načina na koji je algoritam kodiran, ili izbor kompajlera za određeni jezik, ili kompilacija pomenutih opcija, ili čak koji se operativni sistem koristi. U nekim slučajevima jezik koji se implementira od strane interpretatora može biti mnogo sporiji od jezika implementiranog od strane kompajlera.

Postoje drugi faktori koji mogu da utiču na vremenske ili prostorne probleme, ali koji mogu biti van kontrole programera; oni uključuju usklađivanje podataka, granularnost podataka, skupljače đubreta, paralelizam na nivou instrukcija, pozivi podrutina.

Neki procesori imaju sposobnost vektorskog procesuiranja, koje dozvoljava da jedna instrukcija operiše nad više operanada; to može i ne mora da bude lako programerima ili kompajlerima da koriste. Algoritmi dizajnirani za sekvencijalno procesuiranje možda treba da budu potpuno redizajnirani da bi se iskoristilo paralelno procesuiranje.

Još jedan problem koji može da nastane sa kompatibilnim procesorima je da oni mogu da implementiraju instrukciju na različite načine, tako da instrukcije koje su relativno brze na nekim modelima, na drugim modelima mogu da budu relativno spore; ovo može zagorčati život optimizirajućem kompajleru.

Mere korišćenja resursa

Mere se obično predstavljaju kao funkcije sa veličinom laza n.

Dve najčešće mere su:

• Vreme: koliko je algoritmu potrebno da se završi.
• Prostor: koliko radne memorije (tipično ram) je potrebno algoritmu. Ovo ima dva aspekta: količina memorije potrebna za kod, i količina memorije potrebne za podatke nad kojima kod operiše.

Za kompjutere čija je snaga snadbdevena baterijom (npr. laptopovi), ili vrlo duge/velike kalkulacije (npr. superkompjuteri), druge mere od interesa su:

• Direktna potrošnja snage: snaga potrebna da bi se direktno operisalo računarom.
• Indirektna potrošnja snage: snaga potrebna za hlađenje, osvetljenje, itd.

U nekim slučajevima druge manje česte mere mogu da budu takođe relevantne:

• Veličina prenosa: protok može da bude ograničavajući faktor. Kompresija podataka može da se iskoristi da se smanji količina podataka za slanje. Prikazivanje slike (npr. logo Gugla) može da rezultuje slanjem desetina hiljada bajtova (48 hiljada u ovom slučaju) u poređenju sa slanjem šest bajtova za tekst"Google".
• Spoljašnji prostor: prostor potreban na disku ili na drugojm spoljašnjem uređaju; ovo može da se koristi za privremeno skladištenje dok se algoritam izvršava, ili može biti dugoročna memorija potrebna za kasnije referenciranje.
• Vreme odziva: ovo je posebno važno za aplikaciju u realnom vremenu kada komjuterski sistem treba brzo da reaguje na spoljašnje događaje.
• Ukupna cena posedovanja: posebno ako je kompjuter namenjen za jedan poseban algoritam.

Vreme

Teorija

Analiziranje algoritma, tipično korišćenjem analize vremenske kompleksnosti da se dobije prosek vremena izvršavanja kao funkcija za veličinu unetih podataka. Rezultat je obično predstavljen notacijom veliko O. Ovo je korisno za upoređivanje algoritama, posebno kada se velika količina podataka procesuira. Detaljnije procene su potrebne za poređenje algoritama kada je količina podataka mala (iako u ovoj situaciji vreme ne može da bude neki problem u svakom slučaju). Algoritmi koji uključuju paralelno procesuiranje mogu da budu teži za analiziranje.

Praksa

Korišćenje testiranja da se izmeri korisnost algoritma. Mnogi programski jezici imaju dostupnu funkciju koja daje potrošnju vremena procesora. Za algoritme koji dugo traju proteklo vreme može biti značajno. Rezultati bi generalno trebalo da budu uprosečeni kroz nekoliko testova.

Ovaj tip testiranja može biti veoma osetljiv na hardversku konfiguraciju i mogućnosti programera ili problema da se događaju istovremeno na multi procesuiranom i multi programerskoj okolini.

Ova vrsta testa takođe zavisi mnogo od selekcije određenog programskog jezika, kompajlera, i kompajlerskih opcija, tako algoritmi koji se porede moraju biti implementirani pod istim okolnostima.

Prostor

Ova sekcija se bavi korišćenjem glavne memorije (često RAM) dok se algoritmi dešavaju. Kao i vremenska analiza iznad, analiza algoritama, tipično koristeći analizu vremenske kompleksnosti da se proceni memorija potrebna za funkciju za unesene podatke. Rezultat je često predstavljen notacijom veliko O.

Postoji čak četiri aspekta korišćenja memorije koji treba da se razmotre:

• Količina memorije potrebna da sačuva kod algoritma.
• Količina memorije potrebna za unete podatke.
• Količina memorije potrebna za unesene podatke (neke algoritme, kao što je sortiranje, često samo premeštaju podtake koji u uneseni i nije im potreban prostor za izlazne podatke).
• Količina memorije potrebne za radni prostor tokom kalkulacije (ovo uključujeu imenovane promenljive i svaki stk prostor potreban rutinama koje se zovu tokom kalkulacije; ovaj stek prostor može biti vrlo važan za algoritme koji koriste rekurzivne tehnike).

Rani elektronski računari, i rani domaći računari, imaju relativno malu količinu radne memorije. Npr. 1949 EDSAC je imao maksimalnu radnu memoriju od 1024 17-bitnih reči, dok 1980 Sinclair ZX80 je u početku imao 1024 8-bitne bajtove radne memorije.

Trenutni računari imaju relativno veliku količinu memorije (moguće Gigabajte), tako da skupljanje algoritma u što manju memoriju je mnogo manji problem nego što je nekada bio. Ali prisustvo tri različite kategorije memorije može biti vrlo važno:

• Keš memorija (često statička RAM) - ona operiše brzinom sličnom procesorskoj.
• Glavna fizička memorija (često dinamička RAM) - ona operiše nešto sporije od procesorske.
• Virtuelna memorija (često na disku) - ona daje iluziju velike memorijet, i operiše hiljadama puta sporije od RAM.

Algoritam čija memorija treba da stane u keš memoriju će biti mnogo brža od algoritma koji staje u glavnu memoriju, što će za uzvrat biti mnogo brže od algoritma koji je u virtuelnoj memoriji, Da dalje zakomplikujemo problem, neki sistemi imaju do tri nivoa keš memorije, sa varirajućim efikasnim brzinama. Različiti sistemi će imati različite količine ovih različitih tipova memorije, tako da efekat memorije koja je potrebna algoritmu varira poprilično od jednog sistema do drugog.

U ranim danima elektronskog računarstva, ako algoritam i njegovi podaci ne staju u glavnu memoriju onda algoritam ne može da se koristi. Danas korišćenje virtuelne memorije izgleda da doprinosi mnogo memorije, ali na račun performansi. Ako algoritam i njegovi podaci staju u keš memoriju, onda se može postići velika brzina; u ovom slučaju minimiziranje prostora bi takođe doprinelo minimiziranju vremena. Algoritam koju ne može u potpunosti da stane u keš memoriju ali koji pokazuje lokalnost referenci može poprilično dobro da se pokaže.

Primeri efikasnih algoritama

• quicksort prvi poznati algoritam sa brzinom reda $O(n\log n)\,$.
• heapsort Još jedan algoritam brzog sortiranja.
• Binarna pretraga - Pretraživanje složene tabele.
• Bojer-Mur algoritam za pretragu niski - Traženje stringa uz pomoć drugog stringa.

Kritika trenutnog stanja programiranja

• David May FRS a, britanski računarski naučnik i trenutno profesor informatike na Univerzitetu Bristol i osnivač i CTO XMOS Semiconductor, veruje da je jedan od problema to što postoji oslanjanje na Murov zakon da bi se rešile neefikasnosti. On je unapredio 'alternativni' to Moore's law (May's law) koji kaže sledeće:

  Softverska efikasnost se prepolovljava svakih osamnaest meseci, kompenzujući Murov zakon

  Nadovezuje se

  U sveprisutnim sistemima, prepolovljavanje egzekutovanih instrukcija može da udvostruči život baterije i veliki setovi podataka donose velike prilike za bolji softver i algoritme: Smanjujući broj operacija sa N x N na N x log(N) ima dramatičan efekat kada je N veliko... za N = 30 milijardi, ova promena je dobra kao pedeset godina unapređivanja tehnologije

• Softverski autor Adam N. Rosenburg u svom blogu "The failure of the Digital computer", je opisao trenutno stanje programiranja kao približavanju "Horizontu softverskih događaja", (aludirajući na fiktivni "shoe event horizon" opisan od strane Daglas Adams u njegovoj knjizi Hitchhiker's Guide to the Galaxy). On procenjuje da ima 70 dB faktora za gubitak produktivnosti ili "99.99999 procenata, njegove sposobnosti da doprinese", od 1980-ih—"Kada je Artur Č. Klark uporedio realnost računanja u 2001 na kompjuteru HAL u svojoj knjizi Odiseja u svemiru, je istakao kako su predivno mali i moćni računari postali i kako je razočaravajuće kompjutersko programiranje postalo".
• Conrad Weisert daje primere, neke od njih su objavljene u ACM SIGPLAN (Special Interest Group on Programming Languages) Obaveštenja, decembar 1995 u: "Atrocious Programming Thrives"
• Mark Andersen, suosnivač Netscape je citiranu "Mavericks at Work". ISBN 978-0-06-077961-0. rekavši "Pet velikih programera mogu potpuno da premaše 1.000 osrednjih programera."

Takmičenja za najbolje algoritme

Sledeća takmičenja pozivaju na najbolji algoritam zasnovano na nekim arbitrarnim kriterijumima određenim od strane sudija:

• Wired magazine

Vidi još

• Analiza algoritama - kako odrediti resurse potrebne algoritmima
• Arithmetic coding—forma variable-length entropy encoding za efikasnu kompresiju podataka
• Asocijativni niz—struktura podataka koja može biti efikasnija korišćenjem Patricia trees or Judy arrays
• Binarna pretraga—jednostavna i efikasna tehnika za pretraživanje sortiranih nizova
• Benčmark—metod za merenje komparativne egzekucije vremena u definisanim slučajevima
• Best, worst and average case—razmatranja za određivanje vremena egzekucije u tri scenarija
• Branch table—tehnika za redukovanje dužine instrukcije, veličina machine code, (i često takođe memorija)
• Comparison of programming paradigms—paradigma specifične performanse razmatranja
• Optimizacija kompilatora—kompajlerska optimizacija
• Computational complexity of mathematical operations
• Teorija kompleksnosti
• Performanse računara—metrika kompjuterskog hardvera
• Data compression—smanjivanje promene protoka i memorije diska
• Database index—struktura podataka koja poboljšava brzinu operacija vraćanja podataka na tabeli baza podataka
• Entropy encoding—kodiranje podataka efikasno korišćenjem frekvencije pojavljivanja stringova kao kriterijum za zamenu
• Garbage collection—automatsko oslobađanje memorije nakon korišćenja
• Green computing—potez da se implementiraju "zelenije" tehnologije, konzumirajući manje resursa
• Hafmanovi kodovi—algoritam za efikasno kodiranje podataka
• Lokalnost referenci—za izbegavanje keširanih kašnjenja prouzrokovanim ne lokalnim pristupima memoriji
• Optimizacija petlje
• Upravljanje memorijom
• Optimizacija programa
• Performance analysis—metode za merenje performanse algoritma dok radi
• Real-time computing—dalji primeri vremenski kritičnih aplikacija
• Analiza algoritama—procenjivanje očekivanih vremena izvršavanja i algoritamska skalabilnost
• Supernitna obrada
• Simultaneous multithreading
• Spekulativno izvršavanje or Eager execution
• Threaded code—slično virtuelnoj tabeli metoda ili tabeli grana
• Virtual method table—tabela grana sa dinamički postavljenim pokazivačimaza dispečovanje
• Improving Managed code Performance—Microsoft MSDN Library

Literatura

• Gal-Ezer, Judith; Zur, Ela (2004). „The efficiency of algorithms—misconceptions”. Computers & Education. 42 (3): 215—226. doi:10.1016/j.compedu.2003.07.004. 

Spoljašnje veze

• Animation of the Boyer-Moore algorithm (Java Applet)
• "How algorithms shape our world". A TED (conference) Talk by Kevin Slavin.