nav_dugme codeBlog codeBlog
  • početna
  • Učionica
  • Saveti
  • Zanimljivosti
  • Kontakt

Metode optimizacije algoritama

Viber
zoom_plus zoom_minus

Uvod

Jedna od najvažnijih osobina dobrog programera (možda i najvažnija), je težnja ka pronalaženju najoptimalnijeg rešenja za dati problem.

Krajnji cilj, u većini slučajeva, nije lako postići, ali, svakako se možemo (i moramo!) potruditi.

Kroz svojevrstan šematski prikaz (uz upotrebu veoma jednostavnog primera), ilustrovaćemo kako ovaj proces često izgleda u praksi.

Problem

Problem koji ćemo koristiti za primer u ovom članku je sledeći: pronađimo koliko puta se u unetom broju ponavlja najveća cifra datog broja.

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 baš skroz jednostavan), a glavni problem je što u programskim jezicima (u većini slučajeva) ne postoji način da se direktno pristupi ciframa brojčanih promenljivih.

Ciframa ćemo lako pristupiti na sledeći način: preko operatora % izdvojićemo desnu cifru (cifru jedinica) ....

									
int broj    = 587;
desna_cifra = broj % 10;

// desna cifra dobija vrednost 7
									
								
Slika 1. - Naredba za izdvajanje desne cifre 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 desne cifre iz celobrojne promenljive.

.... praktično ćemo ukloniti cifru jedinica 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 rešimo problem "nekako" (bilo kako). U takvom slučaju, algoritam koji nastaje u početnom stadijumu obično je vrlo 'grub' i neefikasan i ovakvo rešenje se često naziva "naivno rešenje".

Naravno, kada kažemo da se problem mora prvo rešiti "bilo kako", podrazumeva se ipak da i takvo rešenje mora biti u granicama razuma u smislu memorijskog zauzeća, vremena izvršavanja i kompleksnosti algoritma.

U našem slučaju, naivno rešenje moglo bi izgledati ovako:

  • kopiraćemo unetu vrednost da bismo je sačuvali za kraj (jer sam postupak izdvajanja cifara podrazumeva 'uništavanje' početne vrednosti unetog broja)
  • potom ćemo dvaput proći kroz cifre unetog broja
  • prvi put ćemo, poređenjem cifara, ustanoviti 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);
}
									
								
Slika 3. - "Naivno" rešenje - prvo koje obično padne na pamet učenicima koji tek počinju da uče programiranje.

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 u pitanju (kao što smo već naveli) svojevrstan šematski prikaz procesa optimizacije algoritama u optem 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]);
}
									
								
Slika 4. - Optimizovano rešenje koje koristi dodatnu strukturu podataka, niz od 10 elemenata, čiji indeksi odgovaraju ciframa.

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 krajnje prihvatljiva rešenja (kao što je algoritam #2 koji smo 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 samo tri 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č 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ćaćeti 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);
}
									
								
Slika 5. - Optimalno rešenje za problem prebrojavanja najveće cifre, koje zahteva minimalan broj dodatnih promenljivih.

Rešenje je sada skroz 'utegnuto': cifre unetog broja smo posmatrali samo jedanput i, po završetku prolaska kroz cifre, imamo informaciju o broju ponavljanja najveće cifre.

Šta je najoptimalnije rešenje

Na kraju nam ostaje da se pozabavimo pitanjem šta je najoptimalnije rešenje za određeni zadatak? Jednostavnog, nedvosmislenog odgovora i rešenja koje paše u svim situacijama - nema. Optimizacija programa zahteva iskustvo i poznavanje konkretne implementacije u najširem kontekstu.

U obzir moramo uzeti što više stvari: 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 i tome slično.

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 programerkse probleme koje treba rešiti ....

Autor članka Nikola Vukićević Za web portal www.codeblog.rs
Napomena: Tekstovi, slike, web aplikacije i svi ostali sadržaji na sajtu www.codeblog.rs (osim u slučajevima gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta www.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.
©2021. Sva prava zadržana.
Viber
početna Početna > Članci > Metode optimizacije algoritama

Info & povezani članci

Info

trejler_sat Datum objave: 04.03.2020.

trejler_dokument Jezici: C

trejler_teg_narandzasti Težina: 7/10

Povezani članci

Strukture podataka Klase složenosti algoritama - (O notacija) Postfiksna notacija - kako računari računaju? Binarno stablo pretrage BFS i DFS - Pronalaženje putanje kroz lavirint Objektno orijentisano programiranje Visinski balansirano (AVL) stablo Uvod u relacione baze podataka i SQL AVL Stablo - Implementacija Shunting Yard - Implementacija
Preuzmite PDF verziju
Abstraction is the elimination of the irrelevant and the amplification of the essential.
Robert C. Martin
codeBlog codeBlog
Projekat posvećen popularizaciji kulture i veštine programiranja među mladim programerima.
Napomena: Tekstovi i slike na sajtu www.codeblog.rs (osim u slučajevima, gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta www.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 odobrenja autora.
© 2021. Sva prava zadržana.
Facebook - logo
Instagram - logo
LinkedIn - logo
Twitter - logo
E-mail
Naslovna
   •
Uslovi korišćenja
   •
Obaveštenja
   •
FAQ
   •
Kontakt