Performance

[Guest]

Hi,

ich lese mit folgender Methode alle Ordnerpfade von einem Server ein.

private ArrayList<String> files = new ArrayList<String>();

private void sucheOrdner(File f) {
    if(ebene < maxEbene) {
        File[] root = f.listFiles();
        if((root = f.listFiles()) != null) {
            for(int i = 0; i < root.length; i++) {
                if(root[i].isDirectory()) {
                    files.add(root[i].getPath());
                    ebene++;
                    sucheOrdner(root[i]);
                    ebene--;
                }
            }
        }
    }
}

Wenn ich jetzt alle Ordnerpfade einlesen möchte, dann schafft der anfangs ein paar hundert pro Sekunde. Aber mit der Zeit wenn er bei ca. 20000 angekommen ist, nur noch 1-2 pro Sekunde. Liegt das an der ArrayList, weil die bei so einer Größe zu langsam wird? Gibt es eine schnellere Alternative?

 

[semi]

ArrayList hat intern ein Array. Jedesmal, wenn dieses Array zu klein wird, um weitere Dateien aufzunehmen,
wird ein neues erzeugt und das ganze wird umkopiert. Versuch's für's erste mit LinkedList, sollte um einiges
schneller werden.

Übrigens, ändere das hier

File[] root = f.listFiles(); 
if((root != null) {

Halbiert die Zeit :wink:

 

[Guest]

cool danke, das geht echt schon viel schneller

 

[Reality]

Schau mal in der Java-API nach. Du kannst auch gleich im vornherein sehr viel Speicherplatz für die Liste reservieren, dann muss nicht so oft umkopiert werden.
Müsste sowohl bei ArrayList als auch bei LinkedList möglich sein.

EDIT: ArrayList al = new ArrayList(40000) müsste funktionieren. Gleiches für LinkedList.

Liebe Grüße
Reality

 

[Franco]

cool danke, das geht echt schon viel schneller

Ich weiss nicht warum das jetzt bei dir schneller geht, es liegt aber sicher nicht am Umstellen von ArrayList auf LinkedList.

Hier ein kleiner Test:

import java.util.*;

public class ListTest {

    public static void main(String[] args) {
       test(new ArrayList<String>(), "ArrayList");
       test(new LinkedList<String>(), "LinkedList");
    }

    
    private static void test(List<String> l, String type) {
        long time = System.currentTimeMillis();
        for (int i = 0; i < 50000; i++) {
            l.add(Integer.toString(i));
        }
        System.out.println(type + " - " + (System.currentTimeMillis() - time));
    }
}

ArrayList - 31
LinkedList - 47

d.h. der Test fügt 50.000 Strings je in eine ArrayList und eine LinkedList ein. Er braucht insgesamt nur 31 bzw. 47 Millisekunden. -> Es liegt mit Sicherheit nicht an der Liste.

Wenn du den Test für 5 Millionen Einträge durchführst, dann wirst du sehen, dass das Anfügen an eine ArrayList schneller geht. Bei einer LinkedList kann man schneller Daten an eine bestimmte Position einfügen.

Siehe java.sun.com/docs/books/tutorial/collections/implementations/list.html

Franco

 

[SlaterB]

@Reality

für LinkedList vorher Platz reservieren?!
da bitte nochmal drüber nachdenken

> Bei einer LinkedList kann man schneller Daten an eine bestimmte Position einfügen.

und der sequentielle Durchlauf ist schneller

 

[Guest]

für LinkedList vorher Platz reservieren?!

Was soll das bringen? Ohne Initialisierung benötigt mein Test weniger als 50 Millisekungen für 50.000 Einträge, der Gewinn kann eigentlich nicht messbar sein!!!

und der sequentielle Durchlauf ist schneller

Nein! Sun schreibt (siehe Link weiter oben):
"But you pay a big price in performance. Positional access requires linear-time in a LinkedList and constant-time in an ArrayList."

und weiter:

"...ArrayList is usually faster."

ausser wenn folgende Situation vorliegt:

"If you frequently add elements to the beginning of the List or iterate over the List to delete elements from its interior, you should consider using LinkedList."

Der Fall ist hier ja wohl gar nicht gegeben.

 

[Guest]

Wenn ich schon mal dabei bin...

private ArrayList<String> files = new ArrayList<String>();

private void sucheOrdner(File f) {
    if(ebene < maxEbene) {   
    // 'ebene' sollte keine Klassenvariable sein, sie wird nur in dieser Funktion verwendet (denke ich)

        File[] root = f.listFiles(); 
        // hier wird die Fileliste gelesen und in root gespeichert

        if((root = f.listFiles()) != null) {
            // hier wird die Fileliste nochmal gelesen und in root gespeichert
            // DAS könne ein Performance Problem sein...

            for(int i = 0; i < root.length; i++) {
                if(root[i].isDirectory()) {
                    files.add(root[i].getPath());
                    ebene++;
                    sucheOrdner(root[i]);
                    ebene--;
                }
            }
        }
    }
}

Besser:

private ArrayList<String> files = new ArrayList<String>();

private void sucheOrdner(File f, int ebene) {
 
        File[] root = f.listFiles(); 
 
        if(root != null) {
 
            for(int i = 0; i < root.length; i++) {
                if(root[i].isDirectory()) {

                    files.add(root[i].getPath());

                    if (ebene < maxEbene) {
                        sucheOrdner(root[i], ebene + 1);
                    }

                }
            }
        }
   
}

Aufrufen wird die Funktion einfach mit:

   sucheOrdner(file, 1);

 

[Illuvatar]

@Franco:

Also erstmal, solche Benchmarks sind eigentlich nicht sehr aussagekräftig (z.B. weil der JIT-Compiler mitreinspielt, das Thema hatten wir schon öfter in Forum).

Ich krieg mit deinem Code zu ca. 50% (hab das Programm mehrmals gestartet) das Ergebnis

ArrayList - 31
LinkedList - 16

ansonsten auch öfters mal zwei fast gleiche Werte, und auch schon das genau umgekehrte Resultat.
Mit einer obergrenze von 500000 ist das ganze schon beständiger, nämlich sowas in der Art:

ArrayList - 343
LinkedList - 203

Und dann hab ich mal Elemente am Anfang hinzugefügt (immer noch 500000)

l.add(0, Integer.toString(i));

ArrayList - 108280
LinkedList - 515

Was sagt uns das alles?
Man muss in jedem Fall einzeln entscheiden, und für <10000 Werte lohnt sich das Nachdenken eigentlich nicht.

 

[SlaterB]

für LinkedList vorher Platz reservieren?!

Was soll das bringen? Ohne Initialisierung benötigt mein Test weniger als 50 Millisekungen für 50.000 Einträge, der Gewinn kann eigentlich nicht messbar sein!!!

ich habe doch selber die Aussage in Frage gestellt, was fragst du also mich?
für LinkedList kann man nämlich von Natur aus gar keinen Platz reservieren, da etwa kein Array angelegt wird

Ohne Initialisierung benötigt mein Test weniger als 50 Millisekungen für 50.000 Einträge, der Gewinn kann eigentlich nicht messbar sein!!!

nana, man findet doch immer einen Test, der 1000x länger dauert,
dann wird jeder Unterschied irgendwann relevant

und der sequentielle Durchlauf ist schneller

Nein! Sun schreibt (siehe Link weiter oben):
"But you pay a big price in performance. Positional access requires linear-time in a LinkedList and constant-time in an ArrayList."

?
'Positional access' ist in LinkedList langsamer, ja
aber eben sequentieller Durchlauf (per Iterator) nicht, da ist die LinkedList schneller

 

[Guest]

Mein Programm ist mit einer LinkedList auch schneller, da ich die Ordner nach dem Einlesen auch noch mit einer anderen Ordnerliste vergleiche. Also ich überprüfe ob Ordner gelöscht wurden. Ich geh die komplette Liste ja damit noch einmal durch. Daran wird es wohl auch liegen. Ich bin mit dem Vergleichen und ohne den einen Fehler von 3.50min auf 1.30min runter gekommen. Bei 25000 Ordnern

 

[SlaterB]

> Ich geh die komplette Liste ja damit noch einmal durch. Daran wird es wohl auch liegen.

mit einem Durchlauf, der minimal schneller ist,
hat man den höheren Zeitverbrauch beim Zusammenbau der Liste noch nicht wieder wettgemacht

aber ist auch egal, durch einfaches Einfügen und Durchlaufen wird man mit 25000 Ordern kaum mehr als ne Sekunde belegen,
99% deiner Zeit geht also für was anderes drauf
(grob angenommen, so genau kann man das natürlich nicht sagen ohne kompletten Code,
schlimm wirds z.B. wenn du zwei große Listen paarweise durchläufst,
also 25000x eine andere Liste komplett durchläufst)

 

[Guest]

So schlimm ist es nun auch nicht :wink:
Ich geh die neue Liste durch und gucke per Binärsuche ob der jeweilige Eintrag in der alten Liste vorhanden ist.

 

[Guest]

Es könnte daran liegen, dass ich alle Ordnerpfade die nicht mehr vorhanden sind in einen String schreibe. Bei 14 Ordner hat das gerade 30sec läger gedauert. Aber irgendwie kann ich mir das nicht so ganz vorstellen.

 

[Reality]

@Franco:
Ich krieg mit deinem Code zu ca. 50% (hab das Programm mehrmals gestartet) das Ergebnis

ArrayList - 31
LinkedList - 16

ansonsten auch öfters mal zwei fast gleiche Werte, und auch schon das genau umgekehrte Resultat.
Mit einer obergrenze von 500000 ist das ganze schon beständiger, nämlich sowas in der Art:

ArrayList - 343
LinkedList - 203

Und dann hab ich mal Elemente am Anfang hinzugefügt (immer noch 500000)

l.add(0, Integer.toString(i));

ArrayList - 108280
LinkedList - 515

Zur Klarstellung:
Wenn du 50 000 Objekte hinzufügst und am Anfang für 50 000 Einträge reservierst, ist das bei dir deutlich langsamer, als wenn du den Default-Wert nimmst? ???:L

Liebe Grüße
Reality

 

[Illuvatar]

Äh ne
Ich hab da bloß die Anzahl der Objekte verändert die ich hinzufüge... ansonsten hab ich an Francos Code nichts geändert.

 

[Reality]

Wieviel Objekte hast du denn hinzugefügt?

Liebe Grüße
Reality

 

[Illuvatar]

Mit einer obergrenze von 500000

Damit meinte ich, 500.000 Objekte hinzugefügt.

 

[Reality]

@all + Illuvatar ;-):
Vertauscht die Instantiierung der Objekte:

public static void main(String[] args) {
    	test(new LinkedList<String>(), "LinkedList");
    	test(new ArrayList<String>(), "ArrayList");
       
    }

Bei mir kommt das folgendes Ergebnis raus:

LinkedList - 1372
ArrayList - 480

Vertausche ich die Instantiierung wieder, sind ArrayList und LinkedList ungefähr auf gleicher Höhe.

Aber wenn ich wie Illuvatar die Elemente am Anfang hinzufüge, braucht ArrayList deutlich länger!

l.add(0, Integer.toString(i));

Liebe Grüße
Reality