statischer Konstruktor

Nimmer

Grünschnabel
Hallo zusammen,

meine Frage besteht heute aus mehreren Teilen. Zum einen haette ich gerne eure Meinung ob der von mir gewaehlte Ansatz ueberhaupt sinnvoll ist. Zum Anderen habe ich eine Frage zur Implementierung dieses Ansatzes.

Das Programm an dem ich gerade arbeite soll Baumsuchen ausfuehren um moeglichst gute Zuege in Spielen zu finden. Wenn ich einen solchen Baum nun aufbaue benoetige ich ja eine ganze Menge von Konstruktoraufrufen, so weit ich weiss sind diese aber recht langsam. Meine Idee war deshalb beim Programmstart eine ganze Reihe von Knoten zu erzeugen und diese dann in den Baum einzufuegen. Wenn dann im naechsten Zug ein neuer Baum erstellt wird kann ich diese Knoten dann wiederverwenden.

So viel zum Ansatz. Macht das Sinn?

Zur Verwaltung der Knoten wollte ich etwas in dieser Art verwenden:
Java:
    private static ArrayList<Node> inUse;
    private static ArrayList<Node> free;
    
    static{
        inUse = new ArrayList<Node>();
        free = new ArrayList<Node>();
        for(int i=0 ; i<100000 ; i++){
            free.add(new Node());
        }
    }
    public static Node getNode(){
        if(free.size() != 0){
            Node ret = free.get(free.size()-1);
            free.remove(free.size()-1);
            inUse.add(ret);
            return ret;
        }else{
            for(int i=0 ; i<1000 ; i++){
                free.add(new Node());
            }
            return getNode();
        }
    }
    public static void freeNode(Node n){
        inUse.remove(n);
        n.reset();
        free.add(n);
    }

So, der Code static{} wird so weit ich weiss erst ausgefuehrt wenn die Klasse die ihn enthaelt das erste Mal verwendet wird. Da das fragliche Programm in zwei Phasen ablaeuft und nur in der zweiten Suchen ausgefuehrt werden verwende ich in der ersten keinen der gespeicherten Knoten. Allerdings habe ich ausreichend Zeit um sie zu erzeugen. Daher ist meine Frage:
Wie bringe ich Java dazu die Knoten schon zu erzeugen wenn ich die fragliche Klasse nicht verwende?

P.S. Entschuldigt bitte die Rechtschreibung. Ich sitze an einer englischen Tastertur und habe keine Ahnung wie ich Umlaute schreiben soll.
 
Hi

Wenn ich einen solchen Baum nun aufbaue benoetige ich ja eine ganze Menge von Konstruktoraufrufen, so weit ich weiss sind diese aber recht langsam. Meine Idee war deshalb beim Programmstart eine ganze Reihe von Knoten zu erzeugen und diese dann in den Baum einzufuegen. Wenn dann im naechsten Zug ein neuer Baum erstellt wird kann ich diese Knoten dann wiederverwenden.

So viel zum Ansatz. Macht das Sinn?
Ein Konstruktor ist zwar nicht langsamer als anderer Code, nur weil er ein Konstruktor ist,
aber ja: So eine Reserveknotensammlung dürfte das Programm verschnellern.
Natürlich auf Kosten vom Speicher.

Zur Verwaltung der Knoten wollte ich etwas in dieser Art verwenden:
...
Eine Arraylist ist allerdings nicht wirklich optimal (Arrayvergrößerungen...).
Und das "vorfüllen" auch nicht.
Unter der Voraussetzung, dass man die Knotenanzahl abschätzen kann,
wäre ein normales Array eine einfache Möglichkeit. Dazu ein int für den Füllstand.

Array am Anfang leer lassen.
Wenn ein Knoten für den Baum gebraucht wird und das Array keinen hat, erzeugen.

Wenn ein Knoten nicht mehr gebraucht wird und Array voll ist: Wegschmeißen.
Deswegen "wenn die Anzahl abschätzbar ist".

Sonst..man könnte ja auch auf Reserveseite einen Baum machen, oder eine echte Liste, oder...

P.S. Entschuldigt bitte die Rechtschreibung. Ich sitze an einer englischen Tastertur und habe keine Ahnung wie ich Umlaute schreiben soll.
Ist doch kein Problem, und ae/oe/ue... sind ja sowieso nicht als Rechtschreibfehler zu zählen.

Gruß
 
Hallo

Code:
		long start = System.currentTimeMillis();
		int loops = 999999;
		System.out.println(loops);
		String path = "/var/tmp/";
		for(int i = 0; i < loops; i++){
			new File(path);
		}
		System.out.println(System.currentTimeMillis() - start);
Ausgabe:
999999
296

Intel i5 @3.2GHZ - natürlich wird da nur ein Core verwendet.

Also, wenn ich eine Million File-Objekte anleg (und da passiert nach dem "new" noch mehr, als einfach nur die Speicheralloziierung), geht das 300ms. Mit Object geht's 0ms *g*, bei 10 Mio "new Objects" geht's 62ms.

Hier noch ein spannender Abschnitt im Wiki:
http://en.wikipedia.org/wiki/Object_pool_pattern#Criticism
... und ich bin da eigentlich gleicher Meinung ...

Ausserdem ist static auch nicht so gut, weil das sind dann Klassenvariabeln, und landen, afaik, im PermGen; da bin ich aber nicht wirklich sicher - jedenfalls, wenn's so ist, wirst du hier wieder Performanceprobleme bekommen, sobald der GC eine stop-the-world-gc macht.

Gruss
slowy
 
Für deinen Fall wäre so etwas wie ein radix trie bzw. PATRICIA-Trie angemessen, siehe https://en.wikipedia.org/wiki/Patricia_trie und http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/
Eine Implementierung ist z.B. https://github.com/rkapsi/patricia-trie

Und auf den static-Block würde ich auch verzichten.
Und die massive Speicherallokation kann man bei gängigen JVMs beschleunigen, indem man per Parameter -Xms512M z.B. 512MB Speicher als Startgröße für die JVM zuweist, damit diese nicht ständig beim Betriebssystem um irgendwelche kleineren Größen betteln gehen muss.
 
klugscheissmodus=on
Ne, statische Variabeln gelangen in den PermGen, da nützen die Xms- und Xmx-Parameter nichts, wenn, dann mit den PermGen-Variabeln -> was aber immer noch zu FullGC's führen wird, wenn dieser Bereich aufgeräumt wird; jedenfalls ist das in der SunVM so.
Und prinzipiell, jedenfalls wird das von uns so gehandhabt, sollte man Xms und Xmx immer auf die gleichen Werte setzen, denn für eine Vergrösserung des Heaps, muss ebenso eine FullGC ausgeführt werden.
/off

Gruss
slowy
 
Zurück