PriorityQueue selbst implementieren

[DerMathematiker]

Hallo zusammen,

ich möchte Dijkstra implementieren.
Da mein Graph wegen Komplexität als AdjazenzArray implementiert ist möchte ich nicht die Knoten die als int vorliegen in Integer wandeln um die Standard PriorityQueue zu verwenden.
(int[] statt ArrayList brachte bei Bellmann Ford 30% verbesserung)

Darum wollte ich fragen ob jemand eine Implementierung kenne (z.B. binaryHeap,FibonacciHeap...)
die den Umweg über Objekte weglassen und alles über pointer arrays machen.

Danke!

 

[Marcinek]

Integer ist ein wrapper für int und afaik genauso Speicherintensiv wie int.

Woher kommen die 30 % verbesserung? - Welche Belege gibt es dafür?

 

[DerMathematiker]

Ich meine in erster Linie die Zeit

wenn ich nur mit primitiven Datentypen arbeite verlier ich sehr viel Performanz wenn ich die mit Integer wrappen muss.

Ich habe jetzt selbst einen BinaryHeap auf int mit pointerMagic 🙂 optimiert.

Dijkstra braucht auf meinem Testgraphen mit der Standard Java PriorityQueue Implementierung
3805 ms und mit meiner eigenen 220 ms bei einem pos. Graph mit 490 000 Knoten und 1 470 000 Kanten.

 

[LoR]

Integer ist ein wrapper für int und afaik genauso Speicherintensiv wie int.

Nein. Wie kommst du auf so eine Aussage?

 

[Marcinek]

Siehe Java Doc 1. Zeile

 

[LoR]

Siehe Java Doc 1. Zeile

Ja, und? Da steht:

The Integer class wraps a value of the primitive type int in an object. An object of type Integer contains a single field whose type is int.

D.h. ~ int + Objektkosten

 

[Marcinek]

Nein..

Objektkosten = int + summe aller attribute und deren attribute

 

[ice-breaker]

Da ein int nur 4 byte kostet und ein Objekt eine Ecke mehr (ich erinnere mich irgendwas an eine Größenordnung von 8 Byte) ist das schon ein Unterschied.
Zudem natürlich noch unnötige Rechenzeit für jedes (un)wrappen hinzukommt.

 

[Marcinek]

Ich habe vin Objektoverheads gelesen, aber noch keine Zahl dafür gefunden.

Da intern das int schon vorhanden ist, sollte es mit intValue() keine Probleme mit umwrappen geben.

Ohne für den Test verwendeten Code kann man jetzt nicht viel mehr sagen.

 

[DerMathematiker]

Ich habe BellmannFord vergleichweise als FIFO queue implementiert und getestest

Im Vergleich zu einer arraybasierten(int[] mit 2 pointern für anfang/ende) FIFO
hat FIFO als LinkedList<Integer> (getFirst(),removeFirst(),addLast()) 50% länger gedauert
hat FIFO als ArrayList<Integer> (get(0),remove(0),add()) um den Faktor 50!! länger gedauert.

Der Code ist etwas umfangreicher da ich über Wochenende(ca. 35Std / 1000 LOC) einen ganzen Framework für ShortestPathProblem programmiert habe.

Wenn jemand Lust hätte wäre ich sehr über unabhängige Ergebnisse freuen.
Als Graph habe ich den Grid-SSquare aus http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.8746&rep=rep1&type=pdf mit ca. 4 Mio Knoten und 12 Mio Kanten genommen.

 

[maki]

Im Vergleich zu einer arraybasierten(int[] mit 2 pointern für anfang/ende) FIFO
hat FIFO als LinkedList<Integer> (getFirst(),removeFirst(),addLast()) 50% länger gedauert
hat FIFO als ArrayList<Integer> (get(0),remove(0),add()) um den Faktor 50!! länger gedauert.

Klingt plausibel, musst bedenken dass das Collections Framework eben sehr allgemein gehalten ist und ich behaupte mal bei über 90% der Anwendungen die 50% Ersparniss deiner FIFO Implementierung zur Standard LinkedList nicht relevant sind.
Dass die ArrayList nicht wirklich als FIFO geeignet ist sollte auch einleuchten, ein remove(0) kopiert mal das ganze Array bis auf das erste Element.
Habe selber auch schon eigene Datenstrukturen in Java for obskure Anforderungen geschrieben, man muss halt wirklich durch Messungen beweisen dass der Aufwand gerechtfertigt ist.

Vielleicht hilft dir ja das bei deiner Suche: What is the most efficient Java Collections library? - Stack Overflow

 

[kay73]

Hi Mathematiker, habe mir das Paper gezogen und das splib.tar besorgt. grid_ssquare killt meinen Rechner. Was kommt da nachher raus, wenn das durchgelaufen ist?

 

[DerMathematiker]

Wie meinst du, was rauskommt? Es kommt halt ein Graph raus auf dem man die verschiedenen kürzeste Wege Algorithmen testen kann. Ich habe alles in java implementiert

Hier sind paar beispiele.
<Name>: <Zeit in ms>
<durchschnittlicherExpansionsgrad (scans)> <minExpansion> <maxExpansion> bzgl. einem Knoten

PapeStrategy: 193 distance: 1629725.0
1.2616872341642984 7 1
PallottinoStrategy: 156 distance: 1629725.0
1.2616948635297258 7 1
FifoLinkedListStrategy: 3530 distance: 1629725.0
45.00893780159835 114 1
FifoArrayStrategy: 2754 distance: 1629725.0
45.00893780159835 114 1
FifoArrayPCStrategy: 2408 distance: 1629725.0
38.457559747468004 113 1
DijkstraPriorityQueueStrategy: 1288 distance: 1629725.0
1.0 1 1
DijkstraBinaryHeapStrategy: 181 distance: 1629725.0
1.0 1 1

 

[kay73]

Wie meinst du, was rauskommt?

Sorry, ich habe das mißverständlich ausgedrückt. Ich meinte Infos wie Dateigröße, Format und wie lange diese Shellscripte laufen. Bei mir ist das RAM dermaßen explodiert, dass ich den Rechner hart ausschalten musste. Ist es möglich und vertretbar, die files zu TAR-BZ2en und irgendwo hochzuladen?

Grüße,

Kay

 

[DerMathematiker]

Ich hab den Graphen und Algorithmen in Java neu implementiert.
Alles so effizient wie möglich mit arrays gemacht.

Alle ist gerade work in progress ... ich werds aber mal schicken wenn es eine stabile Version gibt

 

[kay73]

Ich meinte eigentlich die Testvektoren. Die kann ich irgendwie nicht erzeugen.