Rekursion Dauer

[eQuest]

Hi Community,
bastel grad an einem Programm und verwende ich auch rekursive Aufrufe für Verzeichnisoperationen. Dazu habe ich auch eine GUI auf der eine ProgressBar läuft, welche den Fortschritt wiedergeben soll. Nun hat sich mir die Frage gestellt, wie ich denn abschätzen kann, wie lang so ein rekursiver Aufruf dauert.
Eigentlich geht das doch garnicht oder? Denn ich müsste im Vorhinein schon wissen, wie viele Dateien ich ingesamt kopieren will, um einen Fortschritt feststellen zu können (also immer, wenn ein Hunderstel von den gesamten Dateien kopiert wurde, progressBar.setValue(++j)). Aber das ist ja bei einer rekursiven Methode nicht der Fall, weil man ja nie weiß, wie sich das entwickelt, wie groß der "Baum" wird.

Mal anhand dieses Beispieles:

private int listdir(File dir){
		
		File[] files = dir.listFiles();
		for(int i=0;i<files.length;i++){
			if(files[i].isDirectory()){
				listdir(files[i]);
			}
			else{
				System.out.println(files[i].getName());
			}
		}
		
		return 0;
	}

Habt ihr irgendwelche Ideen?

 

[Marco13]

Abgesehen von dieser Methode wüßte ich da auch nichts konkretes. Ein Mittelding könnte sein, die Rekursion erstmal so durchlaufen zu lassen (mit indeterminate=true) und NUR die Dateien zu zählen. Danach die Rekursion nochmal laufen lassen und die eigentlichen Operationen durchführen, für die man dann eine grobe Schätzung auf Basis der vorherigen Zählung abgeben kann. Sehr grob: Wenn alle Dateien 1 byte groß sind, und die Letzte 10 GB, wird er eine Weile bei 99% stehen bleiben (evtl. könnte man dann statt der Anzahl der Dateien eben die verarbeitete Größe verwenden, aber das muss man sich überlegen)

 

[ice-breaker]

da du eine rekursive Methode hast, die pro Rekursion Arbeit erzeugt gibt es da keine simple Möglichkeit.

Wenn du möglicherweise schon die Größe des Ordners/Laufwerks kennt, könnte man folgendes machen:

private int listdir(File dir, long realSize, MutableLong computedSize){
		
		File[] files = dir.listFiles();
		for(int i=0;i<files.length;i++){
			if(files[i].isDirectory()){
				listdir(files[i], realSize, computedSize);
			}
			else{
				System.out.println(files[i].getName());
				long size = computedSize.addAndGet(files[i].length());
				// update status: size * 100 / realSize
			}
		}
		
		return 0;
	}

Das ist in etwa auch die Art wie Virenscanner den Fortschritt messen, habe ich mal ausprobiert indem ich die Festplatte während des Scannens mit großen Dateien gefüllt habe.

 

[tuxedo]

Auf iteration umbauen und vorher mal durchzählen wieviel durchläufe man in der iterativen schleife braucht. Dann weißt du wieviel zu tun ist ..
Wenn es allerdings nur drum geht den Speicherplatzbedarf aufzusummieren, macht das wenig Sinn.

Dennoch würd' ichs Iterativ machen, wohl mit nem Stack oder so:

Pseudocode:

addToStack(dir)

while (!stack.empty){

   file f = stack.pop()
   if (f.isDirectory()) {stack.push(f)}

   process(f)

}

- Alex

 

[JohannisderKaeufer]

//float mit 1.0
private int listdir(File dir, float factor){
		
		File[] files = dir.listFiles();
                float part = factor / files.length;
		for(int i=0;i<files.length;i++){
			if(files[i].isDirectory()){
				listdir(files[i], part);
			}
			else{
				System.out.println(files[i].getName());
                                addAnotherPartToProcessbar(part);
			}
                        
		}
		
		return 0;
	}

Hier gehe ich davon aus das jedes Element in einem Verzeichnis den gleichen Arbeitsaufwand benötigt.
Bspl

vz 1
  F11
  F12
F 2
F 3

Es gibt 1 Verzeichnis und 2 Dateien.
vz1 hat einen Anteil von 1/3,F2 1/3 F3 1/3.
F11 und F12 die in Vz1 liegen bekommen den factor 1/3 mit woraus sich jeweils 1/6 errechnet.

Also

F11 -> 1/6
F12 -> 1/3
F2   -> 2/3
F3   -> 1

liegen in vz1 hunderte von Dateien sieht das Ergebnis allerdings nicht ganz so harmonisch aus.

 

[mohrenkopf]

Du schreibst von "Verzeichnisoperationen". Ist das Ausgeben/Bestimmen schon die eigentliche Verzeichnisoperation oder willst du mit den Dateien auch noch etwas anderes anstellen (Kopieren, Einlesen)?

Im ersten Fall hast du wahrscheinlich eher verloren, stell dir auf oberster Ebene 100 Verzeichnisse vor, von denen das letzte massig Unterverzeichnisse etc enthält, aus "oberster" Sicht allerdings nur 1% ausmacht. Egal ob Breitensuche oder Tiefensuche, die Überraschung kann überall lauern...

Falls du die Dateien z.B. noch analysieren willst, kannst du ja zuerst per Rekursion eine Liste mit allen abzuarbeitenden Dateien erstellen und bei der Gelegenheit schon mal die Dateigröße etc merken/zählen. Die eigentliche Verarbeitung machst du dann anhand der Liste.

 

[eQuest]

Danke für die zahlreichen Hilfestellungen!
Habe nun die Lösung von ice-breaker umgesetzt und funktioniert super, danke

@mohrenkopf: Will kopieren