Uvod
Kada vidiš dobar potez - potrudi se da pronađeš još bolji!Emanuel Lasker (bivši prvak sveta u šahu)
Jedna od najvažnijih osobina dobrog programera (možda i najvažnija), je težnja ka pronalaženju najoptimalnijeg algoritma u svakoj situaciji.
Iako krajnji cilj u većini slučajeva nije lako postići, svakako se možemo - i moramo(!) - potruditi.
Kroz svojevrstan šematski prikaz, uz upotrebu veoma jednostavnog primera, ilustrovaćemo kako proces pronalaženja optimalnog rešenja izgleda u praksi.
Problem
Problem koji ćemo koristiti za primer u ovom članku je sledeći: potrebno je pronaći koliko puta se u unetom broju ponavlja najveća cifra.
Recimo, u broju 98888817, najveća cifra (9) ponavlja se jednom, a u broju 41322224, najveća cifra (4) ponavlja se dvaput.
Zadatak nije ni malo težak (ali ni "skroz jednostavan"), a glavni problem je što u ogromnoj većini programskih jezika ne postoji način da se direktno pristupi ciframa brojčanih promenljivih.
Samo izdvajanje cifara izvodi se na sledeći način: preko operatora % možemo očitati cifru jedinica ....
int broj = 587;
desna_cifra = broj % 10;
// promenljiva desna_cifra dobija vrednost 7
.... a prostim deljenjem sa 10 (budući da je u pitanju celobrojna promenljiva) ....
broj = broj / 10;
// promenljiva broj dobija vrednost 58
.... cifru jedinica praktično uklanjamo iz celobrojne promenljive (osim naravno u slučaju jednocifrenih vrednosti, kada deljenje sa 10 neće vratiti "ništa", već nulu).
Rešenje #1 - Naivno rešenje
Ukoliko nismo u stanju da odmah iznedrimo najoptimalnije rešenje, moramo se prvo potruditi da uopšte rešimo problem (bilo kako). U takvom slučaju, algoritam koji nastaje u početnom stadijumu obično je vrlo 'grub' i neefikasan, a samo rešenje se često naziva "naivno rešenje".
U našem slučaju, naivno rešenje može se implementirati po sledećem algoritmu:
- pre svega ćemo kopirati unetu vrednost, da bismo je sačuvali za dalju obradu (jer sam postupak izdvajanja cifara podrazumeva 'uništavanje' početne vrednosti unetog broja) i potom dvaput proći kroz cifre unetog broja
- prvi put, poređenjem cifara, ustanovićemo koja cifra unetog broja je najveća (a datu vrednost ćemo zapamtiti)
- u drugom prolasku ćemo prebrojati koliko puta se data cifra pojavljuje
.... čemu odgovara sledeći kod:
#include<stdio.h>
void main()
{
int broj, cifra, p, brojac = 0, max_cifra = -1;
scanf("%d", &broj);
p = broj;
// Pronalazimo najvecu cifru:
while (p > 0) {
cifra = p % 10;
p /= 10;
if (cifra > max_cifra) max_cifra = cifra;
}
// Proveravamo koliko puta se najveca cifra
// pojavljuje u unetom broju:
p = broj;
while (p > 0) {
cifra = p %10;
p /= 10;
if (cifra == max_cifra) brojac++;
}
printf("Najveca cifra broja %d je %d.\n", broj, max_cifra);
printf("Broj ponavljanja najvece cifre: %d.\n", brojac);
}
Ovakav program ni izdaleka nije posebno problematičan i neefikasan (sam po sebi) i sasvim bi "mogao da prođe", ali, budući da je, kao što smo već naveli, u pitanju svojevrstan šematski prikaz procesa optimizacije algoritama u opštem smislu (a ne diskusija o problemu koji smo izabrali za primer, u bukvalnom smislu), nastavljamo sa pretpostavkom da je neprihvatljivo da dvaput prolazimo kroz broj (posle jednog pregleda svih cifara, moramo biti u stanju da damo odgovor na pitanje koliko puta se najveća cifra pojavljuje u unetom broju).
Rešenje #2 - Optimizacija upotrebom pomoćnih struktura podataka
Ukoliko je u implementaciji algoritma prihvatljivo da povećamo memorijsko zauzeće u određenoj meri (na šta ćemo se dodatno osvrnuti posle pregleda oba optimalna algoritma), problem se lako rešava u jednom prolasku kroz cifre broja, upotrebom pomoćnog niza od deset elemenata čiji indeksi od 0 do 9 odgovaraju ciframa dekadnih brojeva:
#include<stdio.h>
void main()
{
int broj, p, max_cifra = -1;
int cifre[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
scanf("%d", &broj);
p = broj;
// Prolazimo jednom kroz cifre promenljive p:
while (p > 0) {
cifra = p % 10;
p /= 10;
cifre[cifra]++; // Povećavamo vrednost u nizu koja se nalazi
// na indeksu koji odgovara trenutno očitanoj
// cifri (ako je trenutno očitana cifra 4, mi
// praktično "gađamo" poziciju cifre[4] i
// povećavamo "brojač četvorki" za jedan;
// navedeno važi i za ostale cifre)
if (cifra > max_cifra) max_cifra = cifra;
}
// Odgovor na pitanje koliko puta se najveca cifra
// pojavljuje u unetom broju zabelezen je na adresi:
// cifre[max_cifra]
printf("Najveca cifra broja %d je %d.\n", broj, max_cifra);
printf("Broj ponavljanja najvece cifre: %d.\n", cifre[max_cifra]);
}
Međutim, ukoliko ne smemo povećavati memorijsko zauzeće (ne smemo koristiti pomoćne strukture), moramo smisliti još efikasniji algoritam.
Rešenje #3 - Dodatna optimizacija algoritma
Ako je algoritam potrebno "zategnuti" koliko god je moguće u odnosu na određeno rešenje koje je krajnje prihvatljivo (kao što je algoritam #2 koji smo prethodno videli), u opštem smislu ćemo najčešće dolaziti u situacije gde se moramo dosta potruditi.
Ipak, u slučaju našeg algoritma sa brojem ponavljanja najveće cifre, nećemo se previše mučiti i lako ćemo zaključiti sledeće:
- kada u određenom koraku očitamo cifru jedinica, doći ćemo u jednu od tri moguće situacije: cifra će biti manja od najveće pronađene cifre, veća od nje, ili identična
- ako je trenutno očitana cifra jedinica veća od do tada najveće pronađene cifre, odmah možemo zanemariti sve informacije o prethodno pronađenoj najvećoj cifri (brojač za najveću cifru, koji je prethodno korišćen, ponovo kreće od 1, tako da se i dalje koristi ista promenljiva)
- ako je pronađena cifra jednaka najvećoj pronađenoj cifri, samo ćemo uvećavati brojač za jedan
- ako je pronađena cifra manja od najveće pronađene cifre, zanemarićemo je
.... što ćemo lako pretočiti u konkretnu implementaciju:
#include<stdio.h>
void main()
{
int broj, cifra, p, brojac = 0, max_cifra = -1;
scanf("%d", &broj);
p = broj;
// Prolazimo kroz cifre broja p jedanput:
while (p > 0) {
cifra = p % 10;
p /= 10;
// Ukoliko smo pronašli novu max_cifru
// možemo u potpunosti zanemariti prethodnu i ....
if (cifra > max_cifra) {
max_cifra = cifra;
// .... započeti brojanje od 1!
brojac = 1;
}
else {
// Ako je trenutna cifra identična maksimalnoj
if (cifra == max_cifra) {
// .... uvećaćemo brojač za 1.
brojac++;
}
}
}
p = broj;
printf("Najveca cifra broja %d je %d.\n", broj, max_cifra);
printf("Broj ponavljanja najvece cifre: %d", brojac);
}
Rešenje je sada skroz 'utegnuto': cifre unetog broja smo posmatrali samo jedanput, po završetku prolaska kroz cifre imamo informaciju o broju ponavljanja najveće cifre i - nismo koristili dodatne strukture podataka.
Šta je (zapravo) najoptimalnije rešenje?
Na kraju nam ostaje da se pozabavimo pitanjem šta je zapravo najoptimalnije rešenje za određeni zadatak - u najširem kontekstu?
Jednostavnog, nedvosmislenog odgovora i rešenja koje paše u svim situacijama - nema. Optimizacija programa zahteva iskustvo i poznavanje svih (ili bar - što više) aspekata konkretne implementacije.
U obzir moramo uzeti: ne samo da li je algoritam optimizovan koliko god je moguće - već i jednostavnost/preglednost koda (što posebno igra ulogu u timskom programiranju, kada na jednom projektu sarađuje više programera), sposobnost/nesposobnost određenog rešenja da bude prošireno ili dopunjeno u situaciji kada se stvore novi uslovi koji do tada nisu postojali (kao i bar još poneki detalj).
U tom smislu, ako se vratimo na primer sa prebrojavanjem cifara, iako poslednji algoritam koji smo videli jeste najoptimalniji sam po sebi, možda bi u određenoj situaciji (ako zaključimo da se dodatno memorijsko zauzeće može zanemariti), bolji izbor bilo izrazito jednostavno i pregledno rešenje, kao što je algoritam #2 koji koristi dodatni niz.
Sve zavisi od toga kako ćemo proceniti ravnotežu između dodatnog memorijskog zauzeća, povećanja kompleksnosti i ostalih stavki koje smo prethodno naveli: dodavanje niza od 40 bajta (niz od deset int promenljivih) kao u primeru #2, koje je ovde simbolički predstavljalo situaciju u kojoj određeni algoritam unosi nedopustivo povećanje memorijskog zauzeća, zbog čega ga je bilo potrebno optimizovati - u praksi je praktično zanemarljivo i ne bi bilo na teret algoritma #2 (pa bismo odluku doneli na osnovu ostalih okolnosti).
Nije uvek ovako lako doći do najoptimalnijeg rešenja, ali, temeljitim proučavanjem teorije programiranja (algoritama i struktura podataka) i uz iskustvo koje se stiče pisanjem velikog broja kvalitetnih programa, polako i postepeno dolazićete do sve boljih i boljih rešenja za probleme koje treba rešiti ....