Rekurze vs zasobnik – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Rekurze vs zasobnik – C / C++ – Fórum – Programujte.comRekurze vs zasobnik – C / C++ – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
fitness
~ Anonymní uživatel
7 příspěvků
28. 7. 2010   #1
-
0
-

Ahoj zkousel jsem si delat nerekurzivni pruchod stromem (inorder) pomoci zasobniku, jenze pri mereni jsem zjistil ze tento zpusob zabere pro 1000 000 cisel 6.6 sekund. Pak sem zkusil rekuzivni zpusob a ten trva jenom 2.5 s. Jakto ze je to takto pomale ??? Muze to byt kvuli toho zasobniku kde se musi prvky jak vkladat tak vypisovat a odebirat nebo je to jenom muj spatny algoritmus ( coz nemuzete posoudit ) Diky za odpovedi...

Nahlásit jako SPAM
IP: 77.48.244.–
Reklama
Reklama
liborb
~ Redaktor
+18
Guru
28. 7. 2010   #2
-
0
-

Když píšeš "... musí se prvky vypisovat a odebírat ..." (odebírat by nemusely), tak jestli děláš v tom nerekurzivním něco navíc proti rekurzivnímu (zejména nějaký ten výpis navíc), tak tomu rozdílu nemůžeš divit.

Jinak takto obecně položená otázka ... tak odpovědí budou takové ty obecně platné pravdy. Vždycky jde napsat jedna verze super optimálně a druhá super neoptimálně - řekl bych, že hodnotit se dá pouze konkrétní implementace.

Nahlásit jako SPAM
IP: 85.207.166.–
KIIV+42
God of flame
28. 7. 2010   #3
-
0
-

pokud ty cisla vypisujes na obrazovku tak si opravdu potrebnej cas vynasob cislem mezi 10 az 1000 :)

jinak pokud je to udelany dobre, nemelo by se to moc lisit

Nahlásit jako SPAM
IP: 62.168.56.–
Program vždy dělá to co naprogramujete, ne to co chcete...
fitness
~ Anonymní uživatel
7 příspěvků
28. 7. 2010   #4
-
0
-

To KIIV : no tak ty cisla se vypisujou do souboru jak v rekurzivnim tak nerekurzivnim...

Nahlásit jako SPAM
IP: 77.48.244.–
fitness
~ Anonymní uživatel
7 příspěvků
28. 7. 2010   #5
-
0
-

To fitness : ja si jinak nedokažu představit jak chci použít zasobnik tak že ten posledni prvek vždycky nevyberu a nevložím nějaky další ...

Nahlásit jako SPAM
IP: 77.48.244.–
KIIV+42
God of flame
28. 7. 2010   #6
-
0
-

toz hod komplet at se mrknem

nebo se ponor do taju programovani a zkus profiler

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

To KIIV : ono je to hodně špatně napsane (vim že se goto nema používat) ale je to prostě napsane tak aby to šlo, určitě to ještě někdy nějak spravim abych to goto odstranil a další "nepřesnosti" tak mi prosim dejte vědět co a jak díky




Tree *sklad = new Tree();
Tree *co = new Tree();
int d = 0;
void inorder()
{
tree = koren;
zkuscyklus:
while(d==0)
{
while(tree!=NULL)
{
xx.push(tree);
if(tree->left==NULL)
{
break;
}
tree = tree->left;

}

pryc:
if(tree->right!=NULL)
{
sklad = xx.top();
cout<<sklad->hodnota;
tree = tree->right;
xx.pop();

}
else
{
sklad = xx.top();
cout<<sklad->hodnota;
xx.pop();
if(xx.empty())
{
d=1;
goto zkuscyklus;
}

tree = xx.top();
goto pryc;
}




}


}

Nahlásit jako SPAM
IP: 77.48.244.–
liborb
~ Redaktor
+18
Guru
29. 7. 2010   #8
-
0
-

Na okraj poznámka: filipika proti goto je takový kolorit, ale před časem jsem musel uznat, že jeho úplné zatracování je stejně nesmyslné jako každá jiná "slepá víra". V tomto tvém případě použití se ukazuje, jak může být program s použití goto značně nepřehledný. Ovšem při jeho vhodném použití lze ušetřit poměrně dost.

A teď k tomu tvému programu. Proč sem nedáš oba ty algoritmy? I to jak plníš ten strom atd. prostě kompletně celé. A nejlépe tak, jak si to měřil (zápis do souboru). Pokud chceš říct, proč je to v tvém konkrétním případě tak a tak, tak se musíš dát konkrétní kód.

Nahlásit jako SPAM
IP: 85.207.166.–
fitness
~ Anonymní uživatel
7 příspěvků
29. 7. 2010   #9
-
0
-

To liborb : no ja jsem stejne meril jenom cas inorderu bez vkladani, ktere sem delal nebo snazil delat bez rekurze (jinak je tam pouzito cteni a zapis ze souboru z C)



#include <iostream>
#include <stack>
#include <ctime>
using namespace std;

struct Tree
{
Tree *left;
Tree *right;
int hodnota;
};

stack<Tree*> xx;

Tree *tree=NULL;
Tree *prevnod = new Tree;
Tree *koren = new Tree;
int c = 0;

void uzel(int cislo)
{
tree = new Tree;
tree->hodnota = cislo;
tree->left = NULL;
tree->right = NULL;

}
void vloz(int cislo)
{


if(c==0)
{
uzel(cislo);
koren = tree;

c=1;
}
else
{
tree=koren;
while(true)
{
if(cislo<tree->hodnota)
{
if(tree->left == NULL)
{
prevnod = tree;
uzel(cislo);
prevnod->left = tree;

break;
}
else
{
tree = tree->left;
}
}
if(cislo>tree->hodnota)
{
if(tree->right == NULL)
{
prevnod = tree;
uzel(cislo);
prevnod->right = tree;

break;
}
else
{
tree = tree->right;
}
}
if(cislo==tree->hodnota)
break;


}


}

}

Tree *sklad = new Tree();
Tree *co = new Tree();
int d = 0;
//inorder
void inorder()
{

FILE *fw;

char *text2;
text2 = new char[15];
text2 = "setrideno.txt";
fw=fopen(text2, "w");
//nastavim na koren stromu
tree = koren;
zacatekcyklu:
while(d==0)
{
while(tree!=NULL)
{
xx.push(tree);
if(tree->left==NULL)
{
break;
}
tree = tree->left;


}


pryc:
if(tree->right!=NULL)
{
sklad = xx.top();
fprintf(fw, "%d\n", sklad->hodnota);
tree = tree->right;
xx.pop();

}
else
{
sklad = xx.top();
fprintf(fw, "%d\n", sklad->hodnota);
xx.pop();
if(xx.empty())
{
d=1;
goto zacatekcyklu;
}

tree = xx.top();
goto pryc;
}




}


}



int main()
{

FILE *fr;
int c;
int i = 0;

cout<<"Zadej s kym chces prunik\n";
char *text;
text = new char[15];
cin>>text;

if ((fr = fopen(text, "r")) == NULL)
{
cout<<"Soubor cisla se nepodarilo otevrit\n";



return 0;
}
//vkladani
while (fscanf(fr, "%d", &c) != EOF)
{
vloz(c);
}
cout<<"\nPracuji na inorderu";
//mereni a inorder
clock_t start, end;

start = clock();
inorder();
end = clock();

cout<<"Cas\n"<<(
(double)( end - start ) / (double)CLOCKS_PER_SEC );


}

Nahlásit jako SPAM
IP: 77.48.244.–
liborb
~ Redaktor
+18
Guru
29. 7. 2010   #10
-
0
-

Ještě tu nejdůležitější část - rekurzivní verzi inorder :). A přepodkládám, že pro naplnění stromu si pro obě varianty použil stejnou fukvi vloz i stejný zdrojový soubor plný čísel, je to tak?

Nahlásit jako SPAM
IP: 85.207.166.–
fitness
~ Anonymní uživatel
7 příspěvků
29. 7. 2010   #11
-
0
-

To liborb : ja sem tu rekurzivni funkci pouzil z internetu



void inorder1(Tree *tree)
{

if(tree!=NULL)
{
inorder1(tree->left);
cout<<tree->hodnota<<" ";//tady fprintf
inorder1(tree->right);

}
}


jo naplneni sem udelal u obou stejne (metoda i cisla)

Nahlásit jako SPAM
IP: 77.48.244.–
liborb
~ Redaktor
+18
Guru
29. 7. 2010   #12
-
0
-

Ještě otázka ... v jaké konfiguraci si to měřil (Debug - _DEBUG/Release - NDEBUG)? Nesmíš zapomenou, že stack (a další) jsou objekty ... což samo o sobě může vést k nějakému zdržení, ale v ladícím režimu (Debug) je to ještě navíc prošpikováno různými kontrolami atd., takže tu o zdržení není nouze (na jednom volání to nikdo nepozná, na milionu volání už to poznat je).

Samozřejmě k tomu kódu mám výhrady, ale pokud je funkční, tak budiž :) No a pokud si to měřil v Release konfiguraci a chceš dosáhnout větší rychlosti,t ak si asi budeš muset napsat svůj jednoúčelový a tudíž optimálnější stack.

Nahlásit jako SPAM
IP: 85.207.166.–
fitness
~ Anonymní uživatel
7 příspěvků
29. 7. 2010   #13
-
0
-

no predtim sem to zmeril v debug kde to trvalo 6.6 sekund...
ted jsem to zkusil znova v release konfiguraci a trvalo to pouze 1.66 sekund a rekurzivni verze trvala 1.616 takze opravdu minimalni rozdil...
jinak ten vlatsni zasobnik sem mel v planu si udelat (uz sem ho skoro mel) ale jednodussi moznost mi prisla pouzit nejaky uz napsany... jinak ti diky za vysvetleni

Nahlásit jako SPAM
IP: 77.48.244.–
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, 79 hostů

Podobná vlákna

Rekurze — založil CML

Rekurze — založil NevimCoSemVyplnit

Rekurze — založil johny

Použití rekurze — založil ST33L

Rekurze SPĚCHÁ — založil Hanmir1

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ý