Náročnost úlohy – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Figa0
Super člen
10. 6. 2010   #1
-
0
-

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;
}
}

Místo int může být použit i jiný datový typ. Jak moc je to náročné na výpočetní výkon? Předem děkuji za odpověď.

Nahlásit jako SPAM
IP: 87.249.133.–
Reklama
Reklama
Wizard0
Stálý člen
10. 6. 2010   #2
-
0
-

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.

Nahlásit jako SPAM
IP: 85.216.193.–
morph
~ Anonymní uživatel
10 příspěvků
10. 6. 2010   #3
-
0
-

O(i)

Nahlásit jako SPAM
IP: 89.103.132.–
yetty_001
~ Redaktor
+5
Super člen
10. 6. 2010   #4
-
0
-

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...

Nahlásit jako SPAM
IP: 94.74.221.–
Figa0
Super člen
10. 6. 2010   #5
-
0
-

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.

Nahlásit jako SPAM
IP: 87.249.133.–
yetty_001
~ Redaktor
+5
Super člen
11. 6. 2010   #6
-
0
-

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.

Nahlásit jako SPAM
IP: 212.20.66.–
Figa0
Super člen
11. 6. 2010   #7
-
0
-

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.

Nahlásit jako SPAM
IP: 87.249.133.–
Krychlik
~ Anonymní uživatel
195 příspěvků
11. 6. 2010   #8
-
0
-

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.

Nahlásit jako SPAM
IP: 78.128.199.–
Figa0
Super člen
11. 6. 2010   #9
-
0
-

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

Nahlásit jako SPAM
IP: 87.249.133.–
KIIV+42
God of flame
11. 6. 2010   #10
-
0
-

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)

Nahlásit jako SPAM
IP: 94.142.234.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Krychlik
~ Anonymní uživatel
195 příspěvků
11. 6. 2010   #11
-
0
-

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.

Nahlásit jako SPAM
IP: 78.128.199.–
Krychlik
~ Anonymní uživatel
195 příspěvků
11. 6. 2010   #12
-
0
-

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

Nahlásit jako SPAM
IP: 78.128.199.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 69 hostů

Podobná vlákna

Časová náročnost — založil Luke

Úlohy — založil ukulele

Opakované úlohy — založil Anonym

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý