TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
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...
Fórum › C / C++
Rekurze vs zasobnik
Nahlásit jako SPAM
IP: 77.48.244.–
GuruKdyž 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.
God of flamepokud 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
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;
}
}
}
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.
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 );
}
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)
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.
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
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žení videa
Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
Uživatelé prohlížející si toto vlákno
Uživatelé on-line: 0 registrovaných, 67 hostů
Moderátoři diskuze
