Metode za optimizaciju algoritama

Uvod

Kada vidiš dobar potez - potrudi se da pronađeš još bolji! Emanuel Lasker (nekadašnji 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 (pri čemu 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, program mora biti u stanju da ponudi odgovor na pitanje koliko puta se najveća cifra pojavljuje u unetom broju.)

Rešenje #2 - Optimizacija upotrebom pomoćnih struktura podataka

Jedan od načina da se određeni algoritamski postupak optimizuje, podrazumeva uvođenje pomoćnih struktura podataka preko kojih se (praktično) beleže dodatne informacije koje mogu biti od pomoći u rešavanju problema.

U slučaju problema 'prebrojavanja najveće cifre': 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, ukoliko nije moguće koristiti pomoćne strukture, potrebno je (ako je ikako izvodljivo :)), optimizovati sam postupak.

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, nije potrebno previše se 'mučiti', to jest, lako se dolazi 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' (svaka cifra unetog broja uzeta je u obzir samo jedanput; po završetku (prvog i jedinog) prolaska kroz cifre, postoji informacija o broju ponavljanja najveće cifre - i nisu korišćene 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, 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.