Rekursive Dateisuche Stack overflow
-
Hallo Leute!
ich hoffe ihr könnt mir helfen. Ich schreibe mir grade ein Tool für die Arbeit ,die Nummernkreise prüft und die Lücken anzeigen soll. Das Auslesen klappt eigentlich soweit, nun wollte ich jedoch die ausgelesen Werte in einer Klasse speichern und später weiter verarbeiten. Durch die Rekursion scheint es aber Probleme zu geben. Die Klasse übergebe ich via Call-by-reference... Ergebnis: Stack-Overflow. Ohne Klasse im übergabeparameter wurden mir auch alle Dateien angezeigt!
Bin halt kein gelernter Programmierer, hoffe ihr könnt helfen:
Programmiert wird unter:
Microsoft Visual Studio 2008 Professional Edition// [22.10.2010] Archive Check.cpp : Definiert den Einstiegspunkt für die Konsolenanwendung. // #include "stdafx.h" #include<windows.h> #include <sstream> #include <iostream> #include <cstring> #include <string> #include <tchar.h> using namespace std; //########## KLASSEN #################################### class DB { private: int AGU_count, ARX_count, ARE_count, AGU_count_toosmall, ARX_count_toosmall, ARE_count_toosmall, AGU_toosmall[10000], ARE_toosmall[10000], ARX_toosmall[10000], AGU[10000000], ARE[10000000], ARX[10000000]; public: void set_are(int tmp); void set_agu(int tmp); void set_arx(int tmp); void set_are_toosmall(int tmp); void set_agu_toosmall(int tmp); void set_arx_toosmall(int tmp); int teile(int *Array,int links ,int rechts); void quicksort(int *Array, int links, int rechts); void sortieren(); void init(void); }; void DB::init(void) { AGU_count=0; ARX_count=0; ARE_count=0; AGU_count_toosmall=0; ARX_count_toosmall=0; ARE_count_toosmall=0; for (int i=0;i<10000000;i++) { AGU[i]=0; ARX[i]=0; ARE[i]=0; } for (int i=0;i<10000;i++) { AGU_toosmall[i]=0; ARE_toosmall[i]=0; ARX_toosmall[i]=0; } } void DB::set_are(int tmp) { ARE[ARE_count]=tmp;ARE_count++; } void DB::set_agu(int tmp) { AGU[AGU_count]=tmp;AGU_count++; } void DB::set_arx(int tmp) { ARX[ARX_count]=tmp;ARX_count++; } void DB::set_are_toosmall(int tmp) { ARE_toosmall[ARE_count_toosmall]=tmp;ARE_count_toosmall++; } void DB::set_agu_toosmall(int tmp) { AGU_toosmall[AGU_count_toosmall]=tmp;AGU_count_toosmall++; } void DB::set_arx_toosmall(int tmp) { ARX_toosmall[ARX_count_toosmall]=tmp;ARX_count_toosmall++; } int DB::teile(int *Array,int links ,int rechts) { int i,j,pivot,temp; i=links; j=rechts-1; pivot=Array[rechts]; do{ while(Array[i]<=pivot && i<rechts) {i++;} while(pivot<=Array[j] && j>links) {j--;} if (i<j) { //Variablen Tauschen [START] temp=Array[i]; Array[i]=Array[j]; Array[j]=temp; //Variablen Tauschen [ENDE] } }while(i<j); //Variablen Tauschen [START] temp=Array[i]; Array[i]=Array[rechts]; Array[rechts]=temp; //Variablen Tauschen [ENDE] return i; } void DB::quicksort(int *Array, int links, int rechts) { int teiler; if (links<rechts) { teiler=teile(Array,links,rechts); quicksort(Array,links,teiler-1); quicksort(Array,teiler+1,rechts); } } void DB::sortieren() { quicksort(ARE,0,ARE_count); quicksort(AGU,0,AGU_count); quicksort(ARX,0,ARX_count); quicksort(ARE_toosmall,0,ARE_count_toosmall); quicksort(AGU_toosmall,0,AGU_count_toosmall); quicksort(ARX_toosmall,0,ARX_count_toosmall); } //########## KLASSEN ENDE #################################### void search_files(wchar_t input[],DB &db) { wchar_t path[41]; wchar_t path_tmp[41]; lstrcpy(path,input); lstrcat(path,L"*"); HANDLE fHandle; WIN32_FIND_DATA wfd; fHandle=FindFirstFile(path,&wfd); do { // Eintrag nur behandeln, wenn es nicht . oder .. ist (werden nur bei Unterverzeichnissen mit zurückgeliefert) // hier könnte man z.B. auch mit lstrcmp auf . und .. vergleichen, was allerdings nicht ganz so effizient ist if (!( (wfd.cFileName[0]=='.') && ( (wfd.cFileName[1]=='.' && wfd.cFileName[2]==0) || wfd.cFileName[1]==0 ) )) { if (wfd.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) { lstrcpy(path_tmp,input); lstrcat(path_tmp,wfd.cFileName); lstrcat(path_tmp,L"\\"); wcout<<"[D]..."<<path_tmp<<endl; search_files(path_tmp,db); } else { //Logik für Dateien } } } while (FindNextFile(fHandle,&wfd)); FindClose(fHandle); } // ############################################################################### int main() { DB db; DB* db_para; db_para=&db; db.init(); //Angabe des Pfades + Konvertiereung für die spätere Funktion int i=0; stringstream s; s<<"W:\\"; //Suchpfad wchar_t wohin[150]; while (s.str()[i]!=NULL) { wohin[i]=s.str()[i]; i++; }wohin[i]='\0'; //Ermittelt alle Dateien im Suchpfad search_files(wohin,db); getchar(); return 0; }Schonmal Vielen Dank für eure Hilfe!
-
Rekursivität in C/C++ sollte vermieden werden wenn sie zu tief wird.
Löse es iterativ (perfomanter)
-
Wenn ich es könnte, würd ich es tun
-
Hast du einmal vom Debugger Gebrauch gemacht? Was aber extrem ins Auge sticht, ist, dass du <string> einbindest, von dem std::string jedoch keinen Gebrauch machst. Dinge wie
wchar_t path[41]; wchar_t path_tmp[41];schreien geradezu nach Überlauf.
Iterativ könnte man es so lösen, dass gefundene Verzeichnisse in einen std::vectorstd::string gepackt und die gefundenen Verzeichnisse jeweils einzeln ausgewertet werden.
Gibt es eigentlich einen Grund dafür, den Quicksort selber zu implementieren? Der Algorithmus der Standardbibiothek ist viel besser getestet als alles, was man selbst schreiben könnte.
-
-
Nach meiner Denkweise wäre es doch nun für mich am einfachsten, wenn ich den Stack erhöhe
Aendere deine Denkweise!
-
Ohje.
AGU_toosmall[10000], ARE_toosmall[10000], ARX_toosmall[10000], AGU[10000000], ARE[10000000], ARX[10000000];Wie konnte ich das übersehen
?
-
@knivil: Denkweise geändert! War nur ne Idee.
@Vicious Falcon:
Für die Datenmenge brauch ich halt platzIm Crosspost link von Martin Richter findet ihr auch die komplette Begründung.
Die Quicksort-Funktion stammt noch aus meinen Informatikunterrichtsstunden die schon was her sind
Tauschen kann ich den später immer noch ; )
-
Für die Datenmenge brauch ich halt platz
Das DB-Objekt wird aber auf dem Stack abgelegt. Der Heap waere die bessere Wahl.
-
knivil schrieb:
Für die Datenmenge brauch ich halt platz
Das DB-Objekt wird aber auf dem Stack abgelegt. Der Heap waere die bessere Wahl.
Nein! Ein dynamischer Container wäre die korrekte Wahl.
-
Muh_Q schrieb:
Wenn ich es könnte, würd ich es tun
Alles was du rekursiv lösen kannst, kannst du auch iterativ lösen!
Und dein Programm wird immer an einem Stack Overflow sterben, wenn deine Funktion sich zu oft selbst aufruft. Der Stack ist begrenzt, selbstverständlich kannst du ihn erweitern (Zur Compiletime, wenn deine DB größer wird musst du das Programm ändern und neu kompilieren), aber wieso eine schlechte Lösung der guten vorziehen?Lösungen wurden schon hier genannt: STL(Vector, List, Queue, Map,...)
AGU_toosmall[10000], ARE_toosmall[10000], ARX_toosmall[10000], AGU[10000000], ARE[10000000], ARX[10000000];Du beliebst zu scherzen...
-
1. Rekusivität ist ganz böse und sollte unbedingt vermieden werden. Was da mit den CPU-Registern gemacht wird ist einfach zu redundant.
2. Der Stack eines Threads ist für gewöhnlich auf ... wie viel war das noch ... 1 MB reduziert? Und allein mit diesen Feldern hier:
GU_toosmall[10000], //40.000 Bytes ... ARE_toosmall[10000],//... und noch einmal. ARX_toosmall[10000],//Once again, for old times sake. AGU[10000000],//Hier direkt 40 Millionen ... ARE[10000000],//... und noch einmal ... ARX[10000000];//... und noch einmal.reservierst du Speicher in der Größe von 114 Megabytes auf dem Stack. Mein Vorschlag: verwende Zeiger, benutze Container oder noch besser, programmiere sie selbst, damit du einen Einblick in die Speicherverwaltung bekommst und lernst, genügsamer zu sein.
3. Es ist theoretisch möglich, den Stack zu erhöhen, aber das wirklich nur in Ausnahmefällen. Wenn du Visual Studio verwendest, kannst du in den Projekteinstellungen die Stapelcommit- und Stapelreservierungsgröße verändern. Aber das wirklich nur in Ausnahmefällen.
