Metode za optimizaciju algoritama

Uvod

Kada vidiš dobar potez - potrudi se da pronađeš još bolji! Emanuel Lasker (bivši prvak sveta u šahu)

U najopštijem smislu, može se reći da je težnja ka pronalaženju optimalnog algoritma u svakoj situaciji, jedna je od najvažnijih osobina dobrog programera (možda čak i najvažnija).

Ostvarivanje navedene ideje ponekad zahteva samo minimum truda, ali, u slučaju većine (iole) ozbiljnijih zadataka, krajnji cilj nije lako postići (ponekad nije lako ni prepoznati kako se uopšte treba usmeriti prema postupku koji predstavlja optimalno rešenje), međutim - u praktičnom smislu - uvek postoji obaveza da se oko svega navedenog bar potrudimo (koliko god je moguće).

Programerski zadaci su brojni i raznoliki (veoma brojni i veoma raznoliki :)), i članak zato neće obuhvatiti "sve" zadatke sa kojima se možete sresti.

Umesto (uzaludnih :)) pokušaja da obuhvatimo 'sve i odjednom', pokušaćemo - kroz svojevrstan šematski prikaz (uz korišćenje veoma jednostavnog primera) - da ilustrujemo kako proces pronalaženja optimalnog rešenja može izgledati u praksi.

Problem

Zarad upoznavanja sa različitim pristupima, razmotrićemo sledeći problem: 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 nimalo težak (ali, nije ni "skroz jednostavan"), a glavni problem je to što u ogromnoj većini programskih jezika ne postoji način da se direktno pristupi ciframa celobrojnih promenljivih.

Međutim, izdvajanje cifre jedinica (što je jedina pozicija koja nas zapravo zanima u kontekstu problema koji razmatramo), može se lako izvesti preko operatora % ....

		
int broj    = 587;
desna_cifra = broj % 10;

// promenljiva desna_cifra dobija vrednost 7

Slika 1. - Naredba za izdvajanje cifre jedinica celobrojne promenljive.

.... a prostim deljenjem sa 10 (budući da je u pitanju celobrojna promenljiva) ....

		
broj = broj / 10;

// promenljiva broj dobija vrednost 58

Slika 2. - Naredba za uklanjanje cifre jedinica iz celobrojne promenljive.

.... cifra jedinica se praktično uklanja iz celobrojne promenljive.

Rešenje #1 - Naivno rešenje

Ukoliko nismo u stanju da odmah 'iznedrimo' optimalno rešenje, moramo se prvo potruditi da uopšte rešimo problem ("bilo kako"). *

U navedenim okolnostima, algoritam koji nastaje u početnom stadijumu, obično je vrlo 'grub' i neefikasan, i poznat pod popularnim nazivom "naivno rešenje".

U slučaju zadatka kojim se bavimo, naivno rešenje može se implementirati na sledeći način:

pre svega, potrebno je kopirati unetu vrednost u pomoćnu promenljivu, da bi vrednost bila sačuvana za dalju obradu (jer sam postupak izdvajanja cifara podrazumeva 'uništavanje' početne vrednosti), i potom je potrebno dvaput proći kroz cifre unetog broja
u prvom prolasku, poređenjem cifara se utvrđuje koja cifra unetog broja je najveća (pronađenu vrednost ćemo zapamtiti)
u drugom prolasku, prebrojava se koliko puta se najveća cifra pojavljuje

Opisanom algoritmu odgovara sledeći programski kod:

		
#include<stdio.h>

void main()
{
	int broj, cifra, p, brojac = 0, max_cifra = -1;
	scanf("%d", &broj);
	
	p = broj;
	
	// Preko prve petlje, pronalazi se
	// najveća cifra:
	
	while (p > 0) {
		cifra = p % 10;
		p    /= 10;
		if (cifra > max_cifra) max_cifra = cifra;
	}
	
	// Preko druge petlje, proverava se koliko puta
	// se najveća 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);
}

Slika 3. - Primer "naivnog" rešenja (prvo rešenje kakvo obično padne na pamet učenicima koji tek počinju da izučavaju programiranje).

Prikazani program (tj. algoritam), ni izdaleka nije posebno problematičan i neefikasan (sam po sebi), i sasvim bi "mogao da prođe", ali (kao što smo već naveli), budući da je primer koji koristimo svojevrstan šematski prikaz procesa optimizacije algoritama u opštem smislu (a ne diskusija o konkretnom problemu koji smo izabrali), nastavljamo uz pretpostavku da nije prihvatljivo da se dvaput prolazi kroz cifre broja.

(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 se memorijsko zauzeće poveća u određenoj meri (na šta ćemo se dodatno osvrnuti posle pregleda oba efikasna algoritma), problem se lako rešava jednim prolaskom kroz cifre broja - uz upotrebu 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;
	
	// Kroz cifre promenljive p, prolazi se jednom:
	
	while (p > 0) {
		cifra = p % 10;
		p    /= 10;
		cifre[cifra]++;
		// Vrednost u nizu koja se nalazi
		// na indeksu koji odgovara trenutno
		// očitanoj cifri, uvećava se za 1
		// (primer: ako je trenutno očitana
		// cifra 4, praktično "gađamo" indeks
		// cifre[4], i "brojač četvorki" se
		// uvećava za 1;
		// navedeni princip naravno važi i za
		// ostale cifre)

		if (cifra > max_cifra) max_cifra = cifra;
	}
	
	// Odgovor na pitanje koliko puta se najveća cifra
	// pojavljuje u unetom broju, zabeležen je na adresi:
	// cifre[max_cifra]
	
	printf("Najveća cifra broja %d je %d.\n", broj, max_cifra);
	printf("Broj ponavljanja najveće cifre: %d.\n", cifre[max_cifra]);
}

Slika 4. - Optimizovano rešenje koje koristi dodatnu strukturu podataka (niz od 10 elemenata, čiji indeksi odgovaraju ciframa).

Međutim, ukoliko se ne sme povećavati memorijsko zauzeće (odnosno, ne smeju se koristiti pomoćne strukture) - potrebno je osmisliti još efikasniji algoritam.

Rešenje #3 - Dodatna optimizacija algoritma

Ako je algoritam potrebno "utegnuti" koliko god je moguće, u odnosu na određeno rešenje koje je krajnje prihvatljivo (kao na primer algoritam #2 koji smo prethodno videli), najčešće ćemo dolaziti u situacije u kojima se moramo 'baš potruditi'.

Ipak, u slučaju konkretnog algoritma kojim se bavimo, nećemo se previše 'mučiti' i lako ćemo doći do sledećih zaključaka:

pošto se u određenom koraku očita cifra jedinica, nastaje jedna od tri moguće situacije: cifra je manja od najveće pronađene cifre, veća od najveće pronađene cifre, ili - identična
ako je pronađena cifra manja od najveće pronađene cifre - pronađena cifra se može zanemariti
ako je pronađena cifra jednaka najvećoj pronađenoj cifri, samo treba uvećavati brojač cifara za 1
ako je trenutno očitana cifra jedinica veća od (do tada) najveće pronađene cifre, odmah se mogu 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)

Opisani algoritam lako se može 'pretočiti' u konkretnu implementaciju:

		
#include<stdio.h>

void main()
{
	int broj, cifra, p, brojac = 0, max_cifra = -1;
	scanf("%d", &broj);
	
	p = broj;
	
	// Kroz cifre broja p, prolazi se jedanput:
	
	while (p > 0) {
		cifra = p % 10;
		p    /= 10;
		
		// Ukoliko je pronađena nova max_cifra,
		// prethodna se može u potpunosti zanemariti
		// i takođe ....

		if (cifra > max_cifra) {                        
			max_cifra = cifra;
			// .... brojanje započinje od 1.
			brojac    = 1;       
		}
		else {
			// Ako je trenutna cifra identična
			// maksimalnoj cifri ....
			if (cifra == max_cifra) {
				// .... brojač se uvećava za 1.
				brojac++;            
			}
		}
	}
	
	p = broj;
	
	printf("Najveca cifra broja %d je %d.\n", broj, max_cifra);
	printf("Broj ponavljanja najvece cifre: %d", brojac);
}

Slika 5. - Optimalno rešenje za problem prebrojavanja najveće cifre (u pitanju je rešenje koje zahteva najmanji broj koraka u obradi, i minimalan broj dodatnih promenljivih).

Može se reći da je rešenje sada skroz 'utegnuto' (cifre unetog broja posmatrali smo samo jedanput; po završetku (prvog i jedinog) prolaska kroz cifre postoji informacija o broju ponavljanja najveće cifre - i nismo koristili dodatne strukture podataka).

Šta je (zapravo) optimalno rešenje?

Na kraju, ostaje da se pozabavimo pitanjem: šta je zapravo optimalno 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 je proces koji zahteva iskustvo, i poznavanje svih aspekata konkretne implementacije (ili, bar - što više aspekata).

Nije dovoljno da se u obzir uzme samo to 'da li je algoritam optimizovan koliko god je moguće', već se u obzir mora uzeti i jednostavnost, tj. preglednost koda (što posebno igra ulogu u timskom programiranju, kada na jednom projektu sarađuje više programera), a svakako je potrebno razmotriti i sposobnost, tj. nesposobnost određenog rešenja da bude prošireno ili dopunjeno u situaciji kada se stvore nove okolnosti koje do tada nisu postojale.

U kontekstu navedenih razmatranja (ako se vratimo na primer sa prebrojavanjem cifara), iako poslednji algoritam koji smo videli jeste optimalno rešenje samo 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 koda i ostalih stavki koje smo prethodno naveli.

Nije uvek lako doći do optimalnog 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 sa kojima ćete se susretati ....

Autor članka Nikola Vukićević Za web portal codeblog.rs

Napomena: Tekstovi, slike, web aplikacije i svi ostali sadržaji na sajtu codeblog.rs (osim u slučajevima gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta codeblog.rs i zabranjeno je njihovo korišćenje na drugim sajtovima i štampanim medijima, kao i bilo kakvo drugo korišćenje u komercijalne svrhe, bez eksplicitnog pismenog odobrenja autora.