Náročnost úlohy – C / C++ – Fórum – Programujte.com

Ahoj mám dotaz v aplikaci potřebuji každých 100ms udělat tuto úlohu.

int position = 25;

int elements[20000];

for(int i = 0; i<20000;i++) {

	if(position==elements[i]) {

		break;

	}

}

Ked chces zistit narocnost vypoctu treba spocitat pocet operacii. Operacia = nahranie dat z pamate do registru, inkrementacia dat, zapis dat do pamate a pod. V tvojom pripade by to malo byt minimalne 9 operacii na jeden prechod cyklom (je dost mozne ze som to zle spocital ale princim je taky, ze ked chces porovnat tak musis najprv data precitat z pamate a takisto taky pristup v poli to mas hned 3 operacie a pod.). No samozrejme kompilator moze veci riesit rozne a tych operacii moze byt viac => najlepsie je pozriet sa na to zec disassembler. No a ked spocitas pocet operacii tak cas, ktory to zaberia jednoducho vypocitas podla frekvencie procesora.

O(i)

To morph : Ano, je to O(i). Pro zlepšení výkonu bych doporučil použít místo pole pro elements nějakou jinou datovou strukturu. Třeba pomocí nějakého hashe...

No pokud dobře počítám tak instrukci je cca deset za sekundu * 20000 = 200000 a musí se to provést 10x za sekundu. takže to máme nějakých 2000000 operaci za sekundu coz jsou 2MHz takže náročnost je zanedbatelná. Pokud vše správně chápu. Jinak moc děkuji.

To Figa : Jasně, u takovýchto malých čísel a dnešních výkonů počítačů to zanedbatelné je. Ale jde o princip, programování není jen o tom "aby to fungovalo", spíše jde o vyřešení problému pokud možno co nejideálnějším postupem. A pokud máš provádět 1000x neefektivní skript, z programátorského hlediska je to hnus. Mnohem lepší je si data nějak přeskupit, což provedeš jednou a poté můžeš teoreticky dosáhnout až konstantní časové náročnosti.

No mam objekt ktery se pochubuje po hracim poli kde jsou prekazky a tak vzdy pred dalsim pohybem musim projit vsechny souradnice prekazek abych mohl vyhodnotit kolizi. nenapadl me lepsi zpusob. Jinak s tebou samozrejme uplne souhlasim.

Kde jsou prekazky, nebo kde se pohybujou prekazky? Protoze jestli se nepohybuji tak je staci "zatavit" do bitmapy a pak konstantne testovat jestli jsi u prekazky. Pripadne pro hardcore reseni si prekazky nacpat do quadtree (jestli jsou dost slozite), ale to bude asi s delem na vrabce.

Prekazky se nepohybuji jsou konstantni. Jak budu kontrolovat jejich blízkost? :)

nebo si muzes udelat jen zmenseninu pole .. na jeden zatah dejme tomu okoli do vzdalenosti 10 bodu...
a az kdyz dojedes na jeho okraj tak projet zase okoli 10 bodu ... omezilo by se to na mene caste kontrolovani celeho pole (jen na generovani toho zmenseneho)

To Figa :Predpocitani- vezmes si "mapu": pole intu nebo booleanu , podle potreby- jestli staci "jsem na prekazce/nejsem na prekazce" booleanu nebo jestli potrebujes "jestli jsem na prekazce,tak na ktere" tak inty a nasekas tam vsecky prekazky- proste je projedes a na to misto kde je napises bool ze tam je, nebo int cislo prekazky.
(Pokud potrebujes i vzdalenost od prekazky, tak pust vlnu od kazde prekazky a zapisuj si vzdalenost.
Pokud potrebujes i cislo nejblizsi prekazky tak si do pole zapisuj aj cislo prekazky od ktere jdes.)
Potom v samotnem programu jenom delas toto: Podivas se do mapy na pozici- je tam nula nebo nejaky jiny specialni znak pro "neni prekazky" tak tam neni prekazka, nebo tam bude cislo prekazky- jsi na prekazce. Toto jde kontrolovat treba i pro sousedni policka jestli chces. Predpokladam diskretni prostor, jinak by nesla vytvorit mapa.

Nejspi se nekdo chyti "diskretni" , tak edit: predpokladam, ze souradnice jsou cela cisla, nebo neco slusne vychovaneho.