die laufzeit einer rekrusiven methode fixen

[Hm...]

hi leute,

ich versuch gerade folgende methode zu beschleunigen:

  
private static HashMap<Integer,Double[]> p(HashMap<Integer,Double[]> map, Integer stationID, int t, int T)  
	{  
		if(T==t+1)  
			return map;  
		  
		NodeDataIterator graph = new NodeDataIterator();  
		graph.selectStation(stationID);  
		ArrayList<NodeData> nachfolger = graph.getNexts();  
				  
		  
		for(int n=0;n<nachfolger.size();n++)//alle in der naechsten zeiteinheit zu erreichende  
		{  
			if(map.containsKey(nachfolger.get(n).id))  
			{  
								  
				Double[] d = map.get(nachfolger.get(n).id);  
				if(Controller.edgesWK.containsKey(String.valueOf(StochastischeMatrix.kombi(stationID, nachfolger.get(n).id))) &&  
						Controller.edgesWK.get(String.valueOf(StochastischeMatrix.kombi(stationID,stationID))).zahl[1]!=0)  
				{  
					  
					d[t] = Controller.edgesWK.get(String.valueOf(StochastischeMatrix.kombi(stationID, nachfolger.get(n).id))).zahl[0]  
							/Controller.edgesWK.get(String.valueOf(StochastischeMatrix.kombi(stationID, stationID))).zahl[1]; //nachfolger.get(n).id  
					  
				}  
				else d[t] = 0.0;  
				map.put(nachfolger.get(n).id, d);  
				if(d[t]!=0){  
					t = t + 1;  
					return p(map,nachfolger.get(n).id,t,T);  
				}  
			}  
			else  
			{  
				Double[] d = new Double[T];  
				for(int i=0; i<T; i++)  
				{//initialisieren  
					d[i] = 0.0;  
				}  
				  
								  
				if(Controller.edgesWK.containsKey(String.valueOf(StochastischeMatrix.kombi(stationID, nachfolger.get(n).id))) &&  
						Controller.edgesWK.get(String.valueOf(StochastischeMatrix.kombi(stationID, stationID))).zahl[1]!=0)  
				{	  
					d[t] = Controller.edgesWK.get(String.valueOf(StochastischeMatrix.kombi(stationID, nachfolger.get(n).id))).zahl[0]  
										/Controller.edgesWK.get(String.valueOf(StochastischeMatrix.kombi(stationID, stationID))).zahl[1];  
					  
				}  
				else d[t] = 0.0;  
				  
				map.put(nachfolger.get(n).id, d);  
				if(d[t]!=0){  
					t = t + 1;  
					return p(map,nachfolger.get(n).id,t,T);  
				}  
			}  
		}  
		return map;  
		  
	}  

der code soll folgendes tun:

wir haben einen graphen, dessen Knoten Integer sind (ID's), wir starten zum zeitpunkt t=0 am knoten stationID und speichern in map alle Nodes die wir erreichen können, sowie die dazugehörigen kantengewichte aus Controller.edesWK.

Input:
1. HashMap<Integer,Double[]> map
Die integer sind nodeID's und das Double Array enthält die kantengewichte. erreichen wir einen node erst nach t schritten, so speichern wir das kanten gewicht als map.get(nodeID)[t]=gewicht.

2. stationID
das ist die ID von der aus wir im graphen starten.

3. t
ist der aktuelle zeitpunkt

4. T
ist der letzte zeitpunkt den wir betrachten wollen.

Output:
gefüllte map

erkennt ihr irgendwelche laufzeitsünden? eigendlich müsste das in O(T+nachfolger.size()) = O(nachfolger.size()) laufen, verbraucht trotzdem aber ordentlich laufzeit (T ist kleiner als 60)

[Hm...]

die laufzeit ist doch höher als vermutet, mein problem ist eigentlich:

gegeben: Graph G = (V,E), Startknoten S aus V und die Anzahl der zugehenden Schritte T

und ich möchte mir nun alle Knoten speichern, die ich von Knoten aus S innerhalb von T schritten erreichen kann und auch die dazugehörigen kantengewichte. außerdem hat G zykel.

weiß eventuell jemand, wie man so etwas machen kann, ohne dabei massig laufzeit zu verbrauchen?

[Whouzuo]

die laufzeit ist doch höher als vermutet, mein problem ist eigentlich:

gegeben: Graph G = (V,E), Startknoten S aus V und die Anzahl der zugehenden Schritte T

und ich möchte mir nun alle Knoten speichern, die ich von Knoten aus S innerhalb von T schritten erreichen kann und auch die dazugehörigen kantengewichte. außerdem hat G zykel.

weiß eventuell jemand, wie man so etwas machen kann, ohne dabei massig laufzeit zu verbrauchen?

Ah, eine schon viel bessere Beschreibung.

Ja, ich würde sagen, das geht wesentlich besser. An deiner Stelle würde ich mich an Dijkstra orientieren. Der berechnet in einem Graphen von einem Startknoten aus für jeden Knoten die geringste Distanz. Etwas angepasst kann man sogar mit vergleichsweise wenig Aufwand eine "Tabelle" anlege, über die man später sehr schnell den kürzsten Weg von jedem Knoten zu jedem anderen Knoten finden kann.

Guck dir also mal an, wie man Dijkstra effizient implementiert (insbesondere die Datenstrukturen), dann kriegst du das, was du willst sicherlich in _wesentlich_ geringerer Laufzeitkomplexität leicht über O(n*log(n)) hin.

[hm....]

Ja, ich würde sagen, das geht wesentlich besser. An deiner Stelle würde ich mich an Dijkstra orientieren. Der berechnet in einem Graphen von einem Startknoten aus für jeden Knoten die geringste Distanz. Etwas angepasst kann man sogar mit vergleichsweise wenig Aufwand eine "Tabelle" anlege, über die man später sehr schnell den kürzsten Weg von jedem Knoten zu jedem anderen Knoten finden kann.

hi und danke :)

den dijkstra und bellman etc. kenne ich noch (vertiefe mich in der algorithmisch diskreten mathematik, wo es unter anderem früher um netzwerkalgorithmen ging - speziell den simplex), aber ich möchte nicht nur die kürzesten wege berechnen, sondern alle.

die knoten meines graphen sind zustände eines markovgraphen.
für zwei knoten i,j aus V gilt, dass jeder weg von i nach j eine sogenante dynamik ist, also eine abfolge von ereignissen die ein objekt (welches zuerst den startzustand i hatte) auf den zustand j bringt.
(über eine abschätzung zur siebformel, sowie das verrechnen aller dynamiken zwischen i und j erhalte ich die wahrscheinlichkeit, dass ein objekt, welches zustand i hat, nach t zeiteinheiten zustand j annimmt - was auch ganz gut funktioniert, nur mein code ist an einigen stellen etwas langsam)

vielleicht kann ich die laufzeit über einen guten algortihmus verringern, eventuell aber auch einfach durch irgendwas software mäßiges oder datenbank mäßiges (mit beiden kenne ich mich nicht gut aus - hashmaps kenn ich zb erst seit wenigen monaten)

[Whouzuo]

den dijkstra und bellman etc. kenne ich noch (vertiefe mich in der algorithmisch diskreten mathematik, wo es unter anderem früher um netzwerkalgorithmen ging - speziell den simplex), aber ich möchte nicht nur die kürzesten wege berechnen, sondern alle.

Du hast geschrieben:

und ich möchte mir nun alle Knoten speichern, die ich von Knoten aus S innerhalb von T schritten erreichen kann

Dafür berechnest du von Knoten S aus zuerst die kürzesten Distanzen (= kürste Anzahl T Schritte) zu allen anderen Knoten mit Dijkstra. Dann gehst du diese allen anderen Knoten durch und guckst für jeden, ob die kürzeste gefundene Distanz kleiner als T Schritte ist. Diesen speicherst du dann -> Ziel erreicht.
Oder habe ich dich falsch verstanden?

[unknown]

Dafür berechnest du von Knoten S aus zuerst die kürzesten Distanzen (= kürste Anzahl T Schritte) zu allen anderen Knoten mit Dijkstra.

Das klingt für mich aber nicht optimal, da du hierfür Knoten mehrfach durchläufst.
     ------A------
   /               \ S-                   -C
   \               /
     ------B------
Um die Distanz zu C zu berechnen müsstest du A und B durchlaufen. A und B müsstest du nochmal durchlaufen um die Distanz zu diesen beiden Knoten selbst zu berechnen.

Das optimale Vorgehen dürfte doch sein, alle von S erreichbaren Knoten zu durchlaufen, diese dabei in S zu speichern und diese schon gespeicherten bei einem weiteren Treffer zu updaten.
Wenn ein Update notwendig war(wegen einer kürzeren Distanz) diesen Knoten nochmal nach unten durchtraversieren, sonst weitermachen mit dem Nächsten.
     ------A------         ------D------
   /               \     /               \ S-                   -C-                   -F - G
   \               /     \               /
     ------B------         ------E------
     \                                 /
       ---------------H---------------
Von S aus:
A, C, D, F, G, E, F(schon vorhanden, gleiche Tiefe - kein Update notwendig), B, C(schon vorhanden, gleiche Tiefe - kein Update notwendig -> weiter mit nächstem Knoten), G, F(schon vorhanden, andere Tiefe - update), G(update)

[unknown]

Von S aus:
A, C, D, F, G, E, F(schon vorhanden, gleiche Tiefe - kein Update notwendig), B, C(schon vorhanden, gleiche Tiefe - kein Update notwendig -> weiter mit nächstem Knoten), G, F(schon vorhanden, andere Tiefe - update), G(update)

Falsch, das 2. G ist ein getarntes H!

A, C, D, F, G, E, F(schon vorhanden, gleiche Tiefe - kein Update notwendig), B, C(schon vorhanden, gleiche Tiefe - kein Update notwendig -> weiter mit nächstem Knoten), H, F(schon vorhanden, andere Tiefe - update), G(update)

[hm1]

mein gesamtes programm läuft auch bei großen datenmengen in weniger als 10 minuten durch, nur bei der besaten methode habe ich großes laufzeitprobleme und muss wahrscheinlich eine der beiden vergehensweisen wählen:

a) die methode in C programmieren

oder

b) einen neuen algorithmus finden

bei einer eingabe von startvec.size()=100 und T=31 läuft das ding mehrere minuten lang, allerdings möchte ich diese methode für mehrere tausend Eid's ausführen (von denen ca. jede 10. einen startvector der länge 100 hat, die meisten haben nur eine länge von 1)

hm... ich guck erstmal, wie man so eine funktion in c bauen und von java aus aufrufen kann

[unknown]

a) die methode in C programmieren

Das wird nicht schneller werden.

bei einer eingabe von startvec.size()=100 und T=31 läuft das ding mehrere minuten lang, allerdings möchte ich diese methode für mehrere tausend Eid's ausführen (von denen ca. jede 10. einen startvector der länge 100 hat, die meisten haben nur eine länge von 1)

Wie dein Graph aussieht und was du hier/wirklich erreichen willst habe ich noch nicht so ganz durchstiegen.

[hm1]

a) die methode in C programmieren
Das wird nicht schneller werden.

bei einer eingabe von startvec.size()=100 und T=31 läuft das ding mehrere minuten lang, allerdings möchte ich diese methode für mehrere tausend Eid's ausführen (von denen ca. jede 10. einen startvector der länge 100 hat, die meisten haben nur eine länge von 1)
Wie dein Graph aussieht und was du hier/wirklich erreichen willst habe ich noch nicht so ganz durchstiegen.

ich hate tatsächlich noch einen kleinen logik fehler drin, den ich dank dir gefunden habe, der code ist nun (dank bubbles verbesserung) der folgendes:

  
private static HashMap<Integer,Double[]> p(HashMap<Integer,Double[]> map, Integer stationID, int t, int T) {  
        if(T == t+1) {  
                return map;  
        }  
  
        NodeDataIterator graph = new NodeDataIterator();  
        graph.selectStation(stationID);  
        ArrayList<NodeData> nachfolger = graph.getNexts();  
  
        for(NodeData node: nachfolger.toArray(new NodeData[nachfolger.size()])) {  
                Double[] d = map.get(node.id);  
                if(d == null) {  
                        d = new Double[T];  
                        for(int i=0; i<T; i++) {  
                                d[i] = 0.0;  
                        }  
                        map.put(node.id, d); //[1]  
                }  
  
                Tupel edgeWK0 = Controller.edgesWK.get(String.valueOf(StochastischeMatrix.kombi(stationID,node.id)));  
                Tupel edgeWK1 = edgeWK0 == null ? null : Controller.edgesWK.get(String.valueOf(StochastischeMatrix.kombi(stationID,stationID)));  
  
                if(edgeWK1 != null && edgeWK1.zahl[0] != 0) {  
                	if(d[t] != 0.0)  
                        d[t] = edgeWK0.zahl[0]/edgeWK1.zahl[1];  
                	else {  
                		Double[] prob = {d[t], (edgeWK0.zahl[0]/edgeWK1.zahl[1])};  
                		d[t] = gemVerteilung(prob);  
                	}  
                }  
                else {  
                        d[t] = 0.0;  
                }  
                //map.put(node.id, d);[1]  
                if(d[t] != 0) {  
                        return p(map, node.id, t+1, T);  
                }  
        }  
        return map;  
}  

aufgerufen durch:

  
for(Integer item: startvec.toArray(new Integer[startvec.size()]))  
		{  
	        p(map, item, 0, T);  
		}  

ich möchte folgendes tun:

gegeben: G=(V,E), S aus V, und T

für alle A, B aus E gilt, dass das kantengewicht w(A,B) die wahrscheinlichkeit dafür ist, dass von knoten A zu knoten B gewechselt wird innerhalb eines schrittes.

berechnen möchte ich eine HashMap map die als key die ID eines jeden knoten enthält, welchen wir erreichen können innerhalb von t schritten sowie die dazugehörigen kantengewichte.

beispiel:

T=2, S={A}

und G sei:
A -> A (selbstabbildung)
A -> B

dann ist die ausgabe:

map.get(NodeID)[t] = wahrscheinlichkeit im t-ten schritt Node mit NodeID zu erreichen und auf diesem node zu stehen (imt t-ten schritt mit t <= T)

map.get(B)[1] = w(A,B) für A -> B
map.get(B)[2] = gemVerteilung(w(A,A),w(A,B)) für A -> A -> B

map.get(A)[1] = w(A,A) für A -> A
map.get(A)[2] = gemVerteilung(w(A,A),w(A,A)) für A -> A -> A

und das möchte ich beschleunigen, eventuell kann ich den aufruf reinziehen in die rekrusive methode oder was in C oder so drehen....

[unknown]

berechnen möchte ich eine HashMap map die als key die ID eines jeden knoten enthält, welchen wir erreichen können innerhalb von t schritten sowie die dazugehörigen kantengewichte.

Die Frage ist ja, brauchst du auch immer ALLE, oder ist diese map nur dazu da im Fall der Fälle schnell für EINEN Knoten oder EIN best. t den Wert zu liefern? Also vielleicht kommst du besser nur dann wenn du es benötigst die Berechnung durchzuführen.

und das möchte ich beschleunigen, eventuell kann ich den aufruf reinziehen in die rekrusive methode

Das bringt sicher keine spürbare Verbesserung.

oder was in C oder so drehen....

Warum soll das schneller sein?

static HashMap<Integer,Double[]> p(HashMap<Integer,Double[]> map, Integer stationID, int t, int T) {

Keine Ahnung wie das in Java ist, in C++ würde jedesmal beim Aufruf und beim return eine Kopie der map erzeugt werden. Ist das in Java automatisch eine Referenz?

[hm1]

berechnen möchte ich eine HashMap map die als key die ID eines jeden knoten enthält, welchen wir erreichen können innerhalb von t schritten sowie die dazugehörigen kantengewichte.
Die Frage ist ja, brauchst du auch immer ALLE, oder ist diese map nur dazu da im Fall der Fälle schnell für EINEN Knoten oder EIN best. t den Wert zu liefern? Also vielleicht kommst du besser nur dann wenn du es benötigst die Berechnung durchzuführen.

ich benötige alle, da jeder pfad von A nach B eine wahrscheinlichkeit hat und die wahrscheinlichkeit allerpfade verrecnet werden muss

und das möchte ich beschleunigen, eventuell kann ich den aufruf reinziehen in die rekrusive methode
Das bringt sicher keine spürbare Verbesserung.

hm...

oder was in C oder so drehen....
Warum soll das schneller sein?

dachte ich mir so, ich kenne mich mit C noch nicht aus

static HashMap<Integer,Double[]> p(HashMap<Integer,Double[]> map, Integer stationID, int t, int T) {
Keine Ahnung wie das in Java ist, in C++ würde jedesmal beim Aufruf und beim return eine Kopie der map erzeugt werden. Ist das in Java automatisch eine Referenz?

das weiß ich leider nicht

[unknown]

das weiß ich leider nicht

Soweit ich dass jetzt auf die schnelle rausgefunden habe ist es wie in JS, alles byValue, aber komplexe Datentypen selbst sind Referenzen.

[hm1]

ich habe die map rausgezogen und als globale variable in die classe gesetzt, dass hat aber keine verbesserung ergeben

komisch finde ich, dass die laufzeit bei einem startvec von vielen elementen (30-100) sehr hoch ist im vergleich zu einem startvec von nur einem element

das sieht so aus, als würde die laufzeit exponentiell mit der länge des startvecs wachsen und mir ist nicht klar warum

[unknown]

ich habe die map rausgezogen und als globale variable in die classe gesetzt, dass hat aber keine verbesserung ergeben

Ja, weil nur eine Referenz kopiert wird, nicht die ganze map.

komisch finde ich, dass die laufzeit bei einem startvec von vielen elementen (30-100) sehr hoch ist im vergleich zu einem startvec von nur einem element

Es hängt ja davon ab, wieviele Knoten unter dem einem und wieviele im Schnitt/Worst Case unter denen im startvec hängen.

[unknown]

Ein einfacher Test, stecke in den startvec 100 mal den einen Knoten, den du vorher betrachtet hast, dass sollte 100 mal länger dauern.

[unknown]

Ansonsten bist du mit deinem eine Knoten vielleicht auch kurz vor der Swappinggrenze.
Wenn Teile deinem Graphen ständig ausgelagert werden und wieder reingeladen werden dauert das natürlich auch.
Wie sieht den der Speicherverbrauch aus?

[hm1]

Ansonsten bist du mit deinem eine Knoten vielleicht auch kurz vor der Swappinggrenze.
Wenn Teile deinem Graphen ständig ausgelagert werden und wieder reingeladen werden dauert das natürlich auch.
Wie sieht den der Speicherverbrauch aus?

mein test mit den 100 zusätzlichen knoten ging über:

  
if(startvec.size()==1)  
		{  
			for(int i=0; i<100; i++)  
				startvec.add(startvec.get(0));  
		}  

ich habe hier weiterhin eine schnelle laufzeit bei denjenigen startvectoren welche um 100 knoten erweitert wurden und eine langsame bei den alten 30-100 dingern

ansich gehe ich davon aus, dass jeder knoten gleichviele nachbarn hat (im mittel), da ich folgende konstruktion verwendet habe:

ereignisse: a,b,c

werden wie zu knoten:
A=true
B=a,true
C=a,false
D=a,b,true
E=b,true
F=b,false
G=b,c,true
H=b,c,false
I=c,true
J=c,false

usw. eine kante existiert immer dann, wenn die ereignisse eines knotens teilmenge eines anderen sind (true und false hierbei ausgenommen und jeweils auf zwei ereignisse pro knoten beschränkt).

ich teste jetzt die speicherkapazität

[hm1]

hm... nochmal ein wenig getestet, eventuell erhöht sich die laufzeit doch pro neuem element in startvec und zwar um ca. 1 sekunde

freienspeicher habe ich während diese methode ausgeführt wird immer mindestens 250 mb

[unknown]

hm... nochmal ein wenig getestet, eventuell erhöht sich die laufzeit doch pro neuem element in startvec und zwar um ca. 1 sekunde

Proportional? Oder wie meinst du das?

freienspeicher habe ich während diese methode ausgeführt wird immer mindestens 250 mb

Mag sein, aber wird ausgelagert? Schneller Test: leuchtet irgendwann die Festplatten LED (fast) dauerhaft?

[hm1]

hm... nochmal ein wenig getestet, eventuell erhöht sich die laufzeit doch pro neuem element in startvec und zwar um ca. 1 sekunde
Proportional? Oder wie meinst du das?

proportional

freienspeicher habe ich während diese methode ausgeführt wird immer mindestens 250 mb
Mag sein, aber wird ausgelagert? Schneller Test: leuchtet irgendwann die Festplatten LED (fast) dauerhaft?

ich arbeite auf einer virtual maschin

ich glaube, ich habe eine laufzeit von N^32 wobei N sehr groß sein könnte, eventuell dreh ich etwas am algorithmus oder finde andere software möglichkeiten zur schnelleren berechnung

[unknown]

hm... nochmal ein wenig getestet, eventuell erhöht sich die laufzeit doch pro neuem element in startvec und zwar um ca. 1 sekunde
Proportional? Oder wie meinst du das?

proportional

Ja was hast du denn erwartet? Dass 100 Berechnungen genauso lange dauern wie eine?

freienspeicher habe ich während diese methode ausgeführt wird immer mindestens 250 mb
Mag sein, aber wird ausgelagert? Schneller Test: leuchtet irgendwann die Festplatten LED (fast) dauerhaft?

ich arbeite auf einer virtual maschin

Die hat ja dann meist wenig Speicher und lagert schneller aus.

ich glaube, ich habe eine laufzeit von N^32 wobei N sehr groß sein könnte,

Wenn N die Breite und 32 die Tiefe ist, ja, für einen Knoten. Das hast du aber für jeden, also m*n^t. Das wäre jedenfalls der Ideal-(Worst Case)-Fall. Weniger kann es ja nicht sein, wenn du immer alles betrachten MUSST.

[hm1]

jep, ich gucke, ob ich eventuell einen besseren algorithmus konstruieren kann.

vorlage ist:

http://tcs.rwth-aachen.de/lehre/DA/SS2011/uebung/loes10.pdf

der auf seite 3 unten. dazu dann noch eine passende datenstruktur und dann sehe ich obs funktioniert ^^

[unknown]

jep, ich gucke, ob ich eventuell einen besseren algorithmus konstruieren kann.

vorlage ist:

http://tcs.rwth-aachen.de/lehre/DA/SS2011/uebung/loes10.pdf

der auf seite 3 unten. dazu dann noch eine passende datenstruktur und dann sehe ich obs funktioniert ^^

Das ist ja aber wieder was anderes.
Du willst ALLE von S erreichbaren Knoten bis zu einer Tiefe t.
In dem Beispiel werden alle Wege von S zu einem best. Knoten K gesucht.

[hm1]

jep, ich gucke, ob ich eventuell einen besseren algorithmus konstruieren kann.

vorlage ist:

http://tcs.rwth-aachen.de/lehre/DA/SS2011/uebung/loes10.pdf

der auf seite 3 unten. dazu dann noch eine passende datenstruktur und dann sehe ich obs funktioniert ^^

Das ist ja aber wieder was anderes.
Du willst ALLE von S erreichbaren Knoten bis zu einer Tiefe t.
In dem Beispiel werden alle Wege von S zu einem best. Knoten K gesucht.

jep, die einfachste (aber immernoch unoptimale variante) wäre:

diese suche für alle infragekommenden nodes auszuführen und immer dann nicht zu speichern, wenn das array mehr als T elemente enthält

dadurch hätte ich eine laufzeit von n^4

aber ich habe gerade kopfschmerzen, kann sein das ich etwas übersehen habe

[unknown]

Das ist ja aber wieder was anderes.
Du willst ALLE von S erreichbaren Knoten bis zu einer Tiefe t.
In dem Beispiel werden alle Wege von S zu einem best. Knoten K gesucht.

jep, die einfachste (aber immernoch unoptimale variante) wäre:

diese suche für alle infragekommenden nodes auszuführen und immer dann nicht zu speichern, wenn das array mehr als T elemente enthält

dadurch hätte ich eine laufzeit von n^4

Tut mir leid, ich kann dir nicht mehr folgen. So wie du es bisher dargestellt hast ist das nicht möglich.

[bubble]

freienspeicher habe ich während diese methode ausgeführt wird immer mindestens 250 mb

Freier Speicher. Bezieht sich das auf die Computer-VM oder auf die JVM? Was der JVM zur Verfügung steht ist ja auch abhängig davon, mit welchen Parametern die JVM initialisiert wird.

Wenn die VM 512MB Arbeitsspeicher bekommt, die JVM mit 128MB initialisiert wird, kannst du 384MB Arbeitsspeicher haben und dein Programm geht in die Knie weil der GC andauernd aufräumen muss weil die 128MB JVM-Speicher knacke-voll sind.

Und wenn der GC dann auch nichts mehr machen kann, kann man auf die OutOfMemoryException warten.

MfG
bubble

[bubble]

das weiß ich leider nicht
Soweit ich dass jetzt auf die schnelle rausgefunden habe ist es wie in JS, alles byValue, aber komplexe Datentypen selbst sind Referenzen.

Primitive Typen und Strings sind Call-by-value, Arrays und Objekte sind eigentlich Call-by-reference.

Wenn ich mich richtig erinnere ist an sich alles Call-by-value, da aber bei Object bla = new WasAuchImmer(); eine eine Reference erzeugt wird auf das eigentliche Objekt und man diese Referenz an die Funktion weiter gibt und kopiert wird, hat man immernoch mit dem gleichen Objekt zu tun, obwohl eigentlich kopiert wurde.

Dadurch sind Konstrukte wie in C# public bool test(Object obj, out string details); nicht möglich.

MfG
bubble

[hm1]

anscheind bekomme ich genau dann eine hohe laufzeit, wenn mein startvec viele elemente enthält, enthält startvec aber nur ein element ist alles schnell - ich vermute dass ich noch irgendwo einen laufzeitfehler gemacht habe

[unknown]

anscheind bekomme ich genau dann eine hohe laufzeit, wenn mein startvec viele elemente enthält, enthält startvec aber nur ein element ist alles schnell - ich vermute dass ich noch irgendwo einen laufzeitfehler gemacht habe

Dann wirst du bei dem einen Element einen kurzen Teilast erwischt haben.

[Whouzuo]

berechnen möchte ich eine HashMap map die als key die ID eines jeden knoten enthält, welchen wir erreichen können innerhalb von t schritten sowie die dazugehörigen kantengewichte.
Die Frage ist ja, brauchst du auch immer ALLE, oder ist diese map nur dazu da im Fall der Fälle schnell für EINEN Knoten oder EIN best. t den Wert zu liefern? Also vielleicht kommst du besser nur dann wenn du es benötigst die Berechnung durchzuführen.

ich benötige alle, da jeder pfad von A nach B eine wahrscheinlichkeit hat und die wahrscheinlichkeit allerpfade verrecnet werden muss

Also jetzt schreib doch bitte mal, was du WIRKLICH ALLES benötigst und was dein ZIEL ist. Eine fachliche Beschreibung bitte. Benutz NICHTS aus deinem Sourceode, sondern mach es wie bisher auch mit formalen Beschreibungen wie "G=(V,E), S aus V, und T" usw.
Und gib bitte präzise und formal an, was du als ENDERGEBNIS (nicht Zwischenergebnis!) haben willst. Als komplettes Endergebnis, wenn man dein Programm ausführt oder dort eine bestimmte Aktion tätigt.

Dann müssen wir auch nicht Rätseln, was du da genau machen willst.
Unknown hat übrigens Recht, das Umschreiben nach C wird dir fast keinen Performancegewinn bringen, da das Problem bei dir in der Laufzeitkomplexität liegt und nicht in aufwendigen Berechnungen. Zumindest nach dem bisher bekannten fachlichen Stand.

[Whouzuo]

Dafür berechnest du von Knoten S aus zuerst die kürzesten Distanzen (= kürste Anzahl T Schritte) zu allen anderen Knoten mit Dijkstra.
Das klingt für mich aber nicht optimal, da du hierfür Knoten mehrfach durchläufst.

Da hast du Recht, daher schrieb ich auch "wesentlich besser" und nicht "optimal" ;)

Wenn ein Update notwendig war(wegen einer kürzeren Distanz) diesen Knoten nochmal nach unten durchtraversieren, sonst weitermachen mit dem Nächsten.
     ------A------         ------D------
   /               \     /               \ S-                   -C-                   -F - G
   \               /     \               /
     ------B------         ------E------
     \                                 /
       ---------------H---------------
Von S aus:
A, C, D, F, G, E, F(schon vorhanden, gleiche Tiefe - kein Update notwendig)

Nur dann kein Update nötig, wenn Die Distanz nicht verringert wurde oder schon <= 10 beträgt!

[hm1]

hi,

danke für die antworten, heute beschäftige ich mich wieder mit diesem thema.

ich hab, glaube ich, beim geschreiben des problems etwas vergessen ^^

ich möchte nicht nur die knoten speichern, sondern auch deren katen bewertungen und zwar von allen kanten. beispiel:

Knotenmenge={A,B,C} mit

A: kunde hat ins geschäfts fenster geguckt
B: kunde hat geschäft betreten
C: kunde hat etwas gekauft

ein kantengewicht w(A,B) gibt die wahrscheinlichkeit an, dass jemand der auf knoten A steht zu knoten B wechselt.

graph könnte sein:

A -> B -> C
A -> C
usw.

also interessiere ich mich nicht nur für jeden knoten den ich zb von der menge {A,B} erreichen kann innerhalb von T zeiteinheiten (schritten), sondern auch für alle dazugehörigen kantenbewertungen, dabei interessiere ich mich auch für die langen pfade.

im beispiel speichere ich also nicht nur A->C sondern auch A->B->C wenn T>1 :)

[unknown]

also interessiere ich mich nicht nur für jeden knoten den ich zb von der menge {A,B} erreichen kann innerhalb von T zeiteinheiten (schritten), sondern auch für alle dazugehörigen kantenbewertungen, dabei interessiere ich mich auch für die langen pfade.

Das ist ja dann eigentlich dein Graph.

im beispiel speichere ich also nicht nur A->C sondern auch A->B->C wenn T>1 :)

Also suchst du den Teilgraph für ein bestimmtes T? Also aus
     ------A------         ------D------
   /               \     /               \ S-                   -C-                   -F - G
   \               /     \               /
     ------B------         ------E------
     \                                 /
       ---------------H---------------
willst du für T=3
     ------A------         ------D
   /               \     /
S-                   -C-
   \               /     \      ------B------         ------E
     \        ----H---------F-----------G
erhalten?

[unknown]

eigendlich müsste das in O(T+nachfolger.size()) = O(nachfolger.size()) laufen,

Wie kommst du darauf?
Alleine
for(int n=0;n<nachfolger.size();n++)//alle in der naechsten zeiteinheit zu erreichende
{
  if(map.containsKey(nachfolger.get(n).id))
ist eine Schleife über nachfolger.size() Elemente. map.containsKey ist eine weitere Suche. nachfolger.get auch nochmal (wobei ich nicht weiß, was in Java eine ArrayList ist, könnte also auch nur ein indizierter Zugriff sein).
Und das geht dann so weiter.

Wenn dir dass auf einen Rutsch zu lange dauert, versuche es aufzuteilen, wenn es geht. Also beim Einfügen eines Knoten diesen an allen Anderen mit seinem Gewicht vermerken. Das macht natürlich nur Sinn, wenn die Knoten nicht am Stück eingelesen werden.
Oder mache es nach Bedarf. Wenn du die Werte zu einem Knoten benötigst, sieh nach ob der Knoten mit Gewicht vorhanden ist, dann nimm diese Daten, sonst berechne sie und trage sie ein.

[Hm...]

danke für beide antworten, ich sehe das ich mich da verzahlt habe

mir ist aufgefallen das ich laufzeitprobleme durch den aufruf der methode bekomme, nicht durch die methode an sich.

ich rufe die methode auf durch:

  
for(int i=0; i<startvec.size(); i++)	  
			p(map,startvec.get(i), 0, T);  

könnte ich diesen aufruf in die methode integrieren würde sich die laufzeit wahrscheinlich deutlich verbessern (nach meinen tests)

[bubble]

for(int i=0; i<startvec.size(); i++)
p(map,startvec.get(i), 0, T);

Funktionsaufrufe kosten Zeit.  
  
~~~php
for(ElementType item: startvec.toArray(new ElementType[startvec.size()]) {  
	p(map, item, 0, T);  
}

hat deutlich weniger Funktionsaufrufe, kannst du aber auch nur verwenden, falls sich die Größe von startvec nicht ändert.

Deine p()-Funktion kann man auch noch verbessern, da wird pro Iteration mindestens 3x nachfolger.get(n) aufgerufen.

private static HashMap<Integer,Double[]> p(HashMap<Integer,Double[]> map, Integer stationID, int t, int T) {  
	if(T == t+1) {  
		return map;  
	}  
	  
	NodeDataIterator graph = new NodeDataIterator();  
	graph.selectStation(stationID);  
	ArrayList<NodeData> nachfolger = graph.getNexts();  
	  
	for(NodeData node: nachfolger.toArray(new NodeData[nachfolger.size()]) {  
		Double[] d = map.get(node.id);  
		if(d == null) {  
			d = new Double[T];  
			for(int i=0; i<T; i++) {  
				d[i] = 0.0;  
			}  
		}  
		  
		WasAuchImmer edgeWK0 = Controller.edgesWK.get(String.valueOf(StochastischeMatrix.kombi(stationID,node.id)));  
		WasAuchImmer edgeWK1 = edgeWK0 == null ? null : Controller.edgesWK.get(String.valueOf(StochastischeMatrix.kombi(stationID,stationID)));  
		if(edgeWK0 != null && edgeWK1.zahl[0] != 0) {  
			d[t] = edgeWK0.zahl[0]/edgeWK1.zahl[1];  
		}  
		else {  
			d[t] = 0.0;  
		}  
		map.put(node.id, d);  
		if(d[t] != 0) {  
			return p(map, node.id, t+1, T);  
		}  
	}  
	return map;  
}

edgeWK0 und edgeWK1 sollten wohl noch sinnvolle Namen bekommen ;P Ob man da einen String-Key benutzen sollte ist an sich auch noch fraglich, wenn Controller.edgesWK eine HashMap/ein HashSet ist sollte es reichen für StochastischeMatrix die hashCode()-Funktion zu überschreiben.

Auf das containsKey hab ich verzichtet, da dir ja relativ egal ist, ob der Schlüssel nicht vorhanden ist, oder der Wert null ist.

Und der doppelte Code ist weg.

MfG
bubble

[bubble]

  if(edgeWK0 != null && edgeWK1.zahl[0] != 0) {

  
Angriff der Tippfehler :s das muss edgeWK1 sein:  
  
~~~java
  
		if(edgeWK1 != null && edgeWK1.zahl[0] != 0) {

MfG
bubble

[bubble]

private static HashMap<Integer,Double[]> p(HashMap<Integer,Double[]> map, Integer stationID, int t, int T) {  
	if(T == t+1) {  
		return map;  
	}  
	  
	NodeDataIterator graph = new NodeDataIterator();  
	graph.selectStation(stationID);  
	ArrayList<NodeData> nachfolger = graph.getNexts();  
	  
	for(NodeData node: nachfolger.toArray(new NodeData[nachfolger.size()]) {  
		Double[] d = map.get(node.id);  
		if(d == null) {  
			d = new Double[T];  
			for(int i=0; i<T; i++) {  
				d[i] = 0.0;  
			}  
			map.put(node.id, d); //[1]  
		}  
		  
		WasAuchImmer edgeWK0 = Controller.edgesWK.get(String.valueOf(StochastischeMatrix.kombi(stationID,node.id)));  
		WasAuchImmer edgeWK1 = edgeWK0 == null ? null : Controller.edgesWK.get(String.valueOf(StochastischeMatrix.kombi(stationID,stationID)));  
		if(edgeWK1 != null && edgeWK1.zahl[0] != 0) {  
			d[t] = edgeWK0.zahl[0]/edgeWK1.zahl[1];  
		}  
		else {  
			d[t] = 0.0;  
		}  
		//map.put(node.id, d);[1]  
		if(d[t] != 0) {  
			return p(map, node.id, t+1, T);  
		}  
	}  
	return map;  
}

[1] Da Arrays Call-by-reference sind, muss map.put(node.id, d); auch nur aufgerufen werden, wenn der Eintrag noch nicht existiert.

MfG
bubble

[hm....]

vielen dank für die hilfe, dass probiere ich morgen aus ! :)

[bubble]

vielen dank für die hilfe, dass probiere ich morgen aus ! :)

Falls es noch relevant ist,

 WasAuchImmer edgeWK1 = edgeWK0 == null ? null : Controller.edgesWK.get(String.valueOf(StochastischeMatrix.kombi(stationID,stationID)));  

sollte außerhalb der for-Schleife sein, da sich stationID nicht wärend der Iteration ändert.

Dadurch sollte dann auch edgeWK0 nur angefordert werden, falls edgeWK1 vorhanden und edgeWK1.zahl[1] != null ist.

Dann würde es auch wieder Sinn machen, dieses if außerhalb der for-Schleife zu machen und dann den doppelten Code (For-Scheife mit und ohne if-Anweisung) in Kauf nehmen.

MfG
bubble

[hm1]

vielen dank für die hilfe, dass probiere ich morgen aus ! :)

Falls es noch relevant ist,

WasAuchImmer edgeWK1 = edgeWK0 == null ? null : Controller.edgesWK.get(String.valueOf(StochastischeMatrix.kombi(stationID,stationID)));

> sollte außerhalb der for-Schleife sein, da sich stationID nicht wärend der Iteration ändert.  
>   
> Dadurch sollte dann auch edgeWK0 nur angefordert werden, falls edgeWK1 vorhanden und edgeWK1.zahl[1] != null ist.  
>   
> Dann würde es auch wieder Sinn machen, dieses if außerhalb der for-Schleife zu machen und dann den doppelten Code (For-Scheife mit und ohne if-Anweisung) in Kauf nehmen.  
>   
> MfG  
> bubble  
  
danke, teste ich  

-- 
Wenn 1 + 1 = 0 => 2 = 2, da: 2 = 1 + 1 = 0 = 1 + 1 = 2 .... ich glaube ich studiere nur Mist :)

[hm1]

eventuell kann ich das ganze beschleunigen indem ich den aufruf

  
for(Integer item: startvec.toArray(new Integer[startvec.size()]))  
		{  
	        p(map, item, 0, T);  
		}  

mit in die methode einbaue, also dass direkt iterativ mit den knoten in startvec begonnen wird.

[MudGuard]

Hi,

  

> 		for(int n=0;n<nachfolger.size();n++)//alle in der naechsten zeiteinheit zu erreichende  
> 		{  
> 			if(map.containsKey(nachfolger.get(n).id))  
> 			{  
> 				if(d[t]!=0){  
> 					return p(map,nachfolger.get(n).id,t,T);  
> 				}  
> 			}  
> 			else  
> 				if(d[t]!=0){  
> 					return p(map,nachfolger.get(n).id,t,T);  
> 				}  
> 			}  
> 		}  
> 		return map;  
> 		  
> 	}  
> 

Es wird also pro Schleifendurchlauf noch ein rekursiver Aufruf gemacht, der Schleifendurchlauf ist schon O(n).
Bei einer Ebene der Rekursion sind wir also schon bei O(n*n), bei 2 Ebenen bei O(n*n*n), bei m Ebenen bei O(n^m)
Die Anzahl der Ebenen ergibt sich bei Dir, wenn ich das richtig sehe, aus T - t (+/- 1, das rauszufummeln ist mir jetzt zu doof).
Deine Funktion ist also O(n^(T-t)), nicht O(n) wie von Dir vermutet.

cu,
Andreas