Rekursive Verweise erkennen?

Übersicht BlitzMax, BlitzMax NG Allgemein

Neue Antwort erstellen

Kernle 32DLL

Betreff: Rekursive Verweise erkennen?

 BeitragMi, März 03, 2010 13:00
Antworten mit Zitat
Benutzer-Profile anzeigen
Hiho,
Seit gestern Abend versuche ich ein generelles Problem in meinem Code zu erkennen (bzw. erkennen lassen): Rekursive Verweise. Ich habe mir dazu eine Funktion (Methode) geschrieben, die versucht eben diese zu erkennen, und ggf. auszugeben.

Zwar erkennt die Methode die Rekursionen korrekt, doch die Ausgabe ist es nicht. Ich habe dazu mal folgenden Code geschrieben, in der Hoffnung die entsprechende Funktion ist irgendwie verständlich. Hat jemand einen Ansatz was ich falsch mache?

Die Idee dahinter ist die eigene Instanz auf einen Stack (hier die TList RecursionList) zu legen, und dann vom ObjektVerweis aus Rekursiv zu prüfen (und dabei auch disese Instanzen auf den Stack legen). Wenn die eigene Instanz im Stack auftaucht dann drehen wir uns im Kreis und wir haben einen Rekursiven Verweis.

Ach ja, der Return Wert soll aussagen ob das Objekt nur einen Rekursiven Verweis hat oder nicht.

Das dazu gehörige Gedankenmuster:
user posted image

BlitzMax: [AUSKLAPPEN] 
SuperStrict

Framework BRL.StandardIO
	Import BRL.LinkedList

Type TTestData
	Field Name:String
	Field ObjektVerweis:TTestData
	
	Method CheckRecursion:Byte()
		Global RecursionList:TList = New TList
		
		If Self.ObjektVerweis
			If RecursionList.Contains(Self.ObjektVerweis)
				Print "Rekursiver Verweis in " + TTestData(RecursionList.First()).Name + " gefunden:"
				For Local Objekt2:TTestData = EachIn RecursionList
					Print "~t" + Objekt2.Name
				Next
				
				Return True
			Else
				RecursionList.AddLast(Self)
					Local detected:Byte = Self.ObjektVerweis.CheckRecursion()
				RecursionList.Remove(Self)
				
				If detected Then Return True
			EndIf
		EndIf
		
		Return False
	End Method
End Type

'Objekte erstellen
Local TestData:TTestData[5]
For Local I:Int = 0 To 4
	TestData[I] = New TTestData
	TestData[I].Name = "Test Datensatz "+(I+1)
Next

'Verweise erstellen
TestData[0].ObjektVerweis = TestData[1]
TestData[1].ObjektVerweis = TestData[2]
TestData[2].ObjektVerweis = TestData[0]
TestData[3].ObjektVerweis = TestData[2]
TestData[4].ObjektVerweis = TestData[3]

'Ergebnisse?
For Local I:Int = 0 To 4
	Print TestData[I].Name + " Rekursiv: " + TestData[I].CheckRecursion() + "~n"
Next


So long,
Kernle
Mein PC: "Bluelight" - Xtreme Gamer PC [Video]
Meine Projekte: Cube-Wars 2010 [Worklog]
Anerkennungen: 1. Platz BCC #7 , 1. Platz BCC #22 , 3. Platz BAC #89
Ich war dabei: NRW Treff III, IV ; Frankfurter BB Treffen 2009

mpmxyz

 BeitragMi, März 03, 2010 19:30
Antworten mit Zitat
Benutzer-Profile anzeigen
Für jedes Objekt wird einzeln getestet und es gibt nur eine Referenz pro Objekt?
Dann ist die Lösung relativ einfach:
BlitzMax: [AUSKLAPPEN] 
Type TTestData
	'''
	Global LastRecSearchID:Int 'Diese Globale wird dafür genutzt, das Zurücksetzen des Feldes "RecSearchID" zu vermeiden.
	
	Field RecSearchID:Int
	'''
	Field Name:String
	Field ObjektVerweis:TTestData
	
	Method CheckRecursion:Byte()
		'''
		LastRecSearchID:+1
		Local SearchObject:TTestData=Self.ObjektVerweis
		While SearchObject.RecSearchID<>LastRecSearchID 'Folge den Referenzen so lange, bis man irgendeinen Zyklus bemerkt
			SearchObject.RecSearchID=LastRecSearchID
			If SearchObject=Self Then Return True 'Wenn man wieder zum Startpunkt kommt, zeigt das Objekt - wenn auch mit Umwegen - auf sich selbst.
			SearchObject=SearchObject.ObjektVerweis
		Wend
		'''
	EndMethod
EndType

Wenn es mehrere Referenzen pro Objekt gibt, muss der Algorithmus angepasst werden.
mfG
mpmxyz
Moin Moin!
Projekte: DBPC CodeCruncher Mandelbrot-Renderer

Kernle 32DLL

 BeitragMi, März 03, 2010 21:12
Antworten mit Zitat
Benutzer-Profile anzeigen
Okay, das hätte ich sagen sollen, im Original hat das Objekt tatsächlich leider mehrere Referenzen. Ich denke aber ich denke ich kann deine Methode umschreiben, so schwer sollte das nicht sein wenn ich deine Idee richtig verstanden habe. Sehe ich das richtig das du quasi eine "Kette" ziehst, und dann prüfst ob du irgendwie mit dieser Kette kollidierst? Das würde zumindest Sinn machen Wink

Ich weis üprigens ehrlich gesagt nicht ob Objekte 4 und 5 auch als Rekursiv erkannt werden sollten oder nicht. Sie selber sind ja nicht Rekursiv, münden aber in eine Rekursive Kette, und sind daher doch als eine solche anzusehen oder?
Mein PC: "Bluelight" - Xtreme Gamer PC [Video]
Meine Projekte: Cube-Wars 2010 [Worklog]
Anerkennungen: 1. Platz BCC #7 , 1. Platz BCC #22 , 3. Platz BAC #89
Ich war dabei: NRW Treff III, IV ; Frankfurter BB Treffen 2009

mpmxyz

 BeitragMi, März 03, 2010 21:35
Antworten mit Zitat
Benutzer-Profile anzeigen
Ja, von der Logik gesehen, ist es nicht viel komplizierter; aus der Kette wird nur ein Baum:
Pseudo-Code: [AUSKLAPPEN]
Startobjekt: Self
Repeat ... Forever:
  Man geht die Liste der Objektreferenzen durch und nimmt das erste unbesuchte Objekt aus der Liste.
  (Wenn wirklich eines gefunden wurde:)
    Wenn dieses Objekt das Self-Objekt ist, dann wurde ein Zyklus gefunden. ->Return True
    Das alte aktive Objekt wird vor dem Wechsel hinten an eine temporäre Liste angefügt.
    Das neue Objekt wird als besucht markiert.
  Wenn kein unbesuchtes Objekt gefunden wurde:
    Wenn die temporäre Liste leer ist, dann wurden alle erreichbaren Objekte untersucht und kein das Objekt betreffender Zyklus gefunden. ->Return False
    Das aktuelle Objekt ist jetzt das letzte Objekt der temporären Liste.
    Der entsprechende Eintrag wird aus der temporären Liste entfernt.

Wenn du die "Tiefensuche" kennst, wird dir das Verfahren bekannt vorkommen.

Zu der anderen Frage:
Wozu soll das ganze dienen?
Soll der Garbage Collector 'unterstützt' werden?
("EndGame()-Free" oder "CheckeUngenutzteSachen()"?)
Da solltest du ein anderes System nutzen.

mfG
mpmxyz
Moin Moin!
Projekte: DBPC CodeCruncher Mandelbrot-Renderer

Kernle 32DLL

 BeitragMi, März 03, 2010 21:37
Antworten mit Zitat
Benutzer-Profile anzeigen
Der GC ist natürlich ein weiterer Punkt, aber es geht mir dabei vor allem um mein Translations System. Ich will Rekursive Verweise erkennen und blockieren, das ist der Sinn Wink
Mein PC: "Bluelight" - Xtreme Gamer PC [Video]
Meine Projekte: Cube-Wars 2010 [Worklog]
Anerkennungen: 1. Platz BCC #7 , 1. Platz BCC #22 , 3. Platz BAC #89
Ich war dabei: NRW Treff III, IV ; Frankfurter BB Treffen 2009

mpmxyz

 BeitragMi, März 03, 2010 21:48
Antworten mit Zitat
Benutzer-Profile anzeigen
Wenn diese zyklischen Verweise verhindert werden, dann sollte es reichen, wenn erkannt wird, dass das neu erstellte Objekt selbst in einem Zyklus ist.
Denn der Fall, dass es zu einem Zyklus führt, kann nicht eintreten, da ja noch kein Zyklus existiert.
mfG
mpmxyz
Moin Moin!
Projekte: DBPC CodeCruncher Mandelbrot-Renderer

Kernle 32DLL

 BeitragMi, März 03, 2010 21:56
Antworten mit Zitat
Benutzer-Profile anzeigen
Eben nicht, weil die das translations System darauf ausgelegt ist den Inhalt der Translations On-The-Fly zu ändern. D.H. in einem ganz ungünstigen Fall könnte jemand ein paar Translations erstellen, und dann die Inhalte über entsprechende Befehle zu einer Rekursiven Kette ändern.

Ich habe indess mal versucht das ganze anhand einer TList Kette abzubilden. Funktioniert ebenfalls, und braucht kein exta Feld in der Klasse. Theoretisch müsste das auch mit Multiplen Objektverweisen funktionieren, indem man die Liste Global macht und für jeden Verweis Eintrag die Methode Rekursiv ausführt. Dann müsste man nur am Ende der Methode die Kette wieder so weit löschen wie man sie in der Methode selbst (also nicht dem Rekursiven Aufruf insgesamt) geführt hat, damit sich die Ketten korrekt "ausbreiten" können (z.B. ein Objekt mit 2 Verweisen, die jeweils in Zwei Ketten enden, die sich am Ende "schneiden", aber keine Rekursion bilden).

BlitzMax: [AUSKLAPPEN] 
Method CheckRecursion:Byte()
	Local ChainList:TList = New TList 'Ggf. Global für Multiple Verweise
	
	If Not Self.ObjektVerweis Then Return False 'Es gibt keinen Verweis mehr, Ketten Ende
	Local SearchObject:TTestData = Self
	
	While Not ChainList.Contains(SearchObject.ObjektVerweis) 'So lange suchen bis wir auf unsere Kette treffen
		SearchObject = SearchObject.ObjektVerweis
			If Not SearchObject Then Return False 'Es gibt keinen Verweis mehr, Ketten Ende
			ChainList.AddLast(SearchObject) 'Glied der Kette hinzufügen
	Wend
	
	'Die Ausgabe
	Local ChainString:String = Self.Name + " > "
	For Local Objekt:TTestData = EachIn ChainList
		ChainString:+Objekt.Name
		If Objekt <> ChainList.Last() Then ChainString:+" > "
	Next
	Print "Chain: " + ChainString
	
	Return True
EndMethod
  • Zuletzt bearbeitet von Kernle 32DLL am Mi, März 03, 2010 22:30, insgesamt einmal bearbeitet

BladeRunner

Moderator

BeitragMi, März 03, 2010 22:10
Antworten mit Zitat
Benutzer-Profile anzeigen
Algo:
- addiere das Objekt zu einer Vergleichsliste.
- prüfe ob das eben addierte Objekt doppelt in der Liste ist.
-- falls ja: Gehe von Objekt alle Referenzen durch und prüfe ob der erneute Eintrag aufgerufen wird. Ist Dies der Fall, lösche es von der Vergleichsliste.
-- falls nein: verfahre mit allen Objektfeldern des Objektes wie mit dem Objekt selbst.

Sollte zumindest theoretisch funktionieren.
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

mpmxyz

 BeitragMi, März 03, 2010 22:14
Antworten mit Zitat
Benutzer-Profile anzeigen
Kernle:
Bei deiner Methode erkaufst du dir die Speicherersparung gegen Geschwindigkeit:
Für n zusammenhängende Objekte ändert sich die maximale Laufzeit so:
O(n) >>> O(n²)
In wie fern das später zu langsam sein könnte, weiß ich nicht.

Zu deinem Einwand:
Wenn bei jeder Änderung geprüft wird, ob sie einen Zyklus erzeugt, und die Änderung gegebenenfalls wieder Rückgängig gemacht wird, wird es keine Probleme geben, falls in dem Translations-System nicht irgendetwas dazwischenfunkt. (Etwas wie z.B.: "Änderungen werden erst später richtig übernommen." Ich kenne jetzt nicht die Details.)
mfG
mpmxyz
Moin Moin!
Projekte: DBPC CodeCruncher Mandelbrot-Renderer

Kernle 32DLL

 BeitragMi, März 03, 2010 22:29
Antworten mit Zitat
Benutzer-Profile anzeigen
Wenn ich die Änderung sofort wieder zurück nehme ist das kein Problem. Das System basiert darauf das die Translation (also auch nacher der Content) aus sog. Slices, also Teilen besteht. Und wenn ein solcher Slice eine Translation ist holt der sich beim Berechnen des Content halt von dieser Translation deren Content.

Mh mpmxyz, ich will nicht klugscheißen oder so, aber müsste es nicht O(2^n) sein? (wobei n dann für die Anzahl der Verweise pro Objekt steht). Das wäre natürlich noch fataler, aber ich denke wie sich das wirklich auswirkt kann man nur im Praxistest rausfinden. Ich denke so 50 Objekte mit 2-5 Verweisen jeweils sollten ein realistisches Testmuster sein. Jetzt muss ich nurnoch die Methode (gemäß BladeRunner?) schreiben.

Meine bisherige Funktion habe ich auch noch mal umgebaut, da war noch nen Gedankenfehler drin.
BlitzMax: [AUSKLAPPEN] 
Method CheckRecursion:Byte()
	Local ChainList:TList = New TList 'Ggf. Global für Multiple Verweise
	
	If Not Self.ObjektVerweis Then Return False 'Es gibt keinen Verweis mehr, Ketten Ende
	Local SearchObject:TTestData = Self
	
	While Not ChainList.Contains(SearchObject) 'So lange suchen bis wir auf unsere Kette treffen
		ChainList.AddLast(SearchObject) 'Glied der Kette hinzufügen
		SearchObject = SearchObject.ObjektVerweis
		If Not SearchObject Then Return False 'Es gibt keinen Verweis mehr, Ketten Ende
	Wend
	
	Return True
EndMethod
Mein PC: "Bluelight" - Xtreme Gamer PC [Video]
Meine Projekte: Cube-Wars 2010 [Worklog]
Anerkennungen: 1. Platz BCC #7 , 1. Platz BCC #22 , 3. Platz BAC #89
Ich war dabei: NRW Treff III, IV ; Frankfurter BB Treffen 2009

mpmxyz

 BeitragMi, März 03, 2010 22:57
Antworten mit Zitat
Benutzer-Profile anzeigen
Ok, bei so wenigen Objekten sollte die Geschwindigkeit kein Problem sein.
Das, was ich ansprechen wollte, war der Aufruf "ChainList.Contains".
Je mehr Einträge in der Liste sind, desto länger kann die Suche dauern.
(Bei den Formeln bin ich mir gerade nicht so sicher, ob die richtig sind; vielleicht war/bin ich zu müde...)
Da es aber eh so wenige Objekte sind, sollte es egal sein, ob die Methode eptimal ist oder nicht.
So führen halt viele Wege nach Rom. Wink
mfG
mpmxyz
Moin Moin!
Projekte: DBPC CodeCruncher Mandelbrot-Renderer

Kernle 32DLL

 BeitragMi, März 03, 2010 23:01
Antworten mit Zitat
Benutzer-Profile anzeigen
Alternativ kann man es ja auch mit ner TMap machen. Einfach Key und Value das gleiche. Macht ja nix, es geht ja nur um den schnellen Look-Up. ich habe es mal simpel mit einer TMap nachgebaut. Besonders bei langen Ketten ist die TMap natürlich deutlich im Vorteil. Ansonsten (das sieht man in untrigem Code nicht) ist die TList Lösung minimal schneller (ca. 20ms). Der Fall den ich programmiert habe ist wirklich der schlimmste Anzunehmende Fall (Eine komplett Rekursive Kette aus 1000 Einträgen).

Morgen gebe ich mich mal an die Multi-Verweis Lösung, mal schauen ob das sich auch rentiert. Ich bedanke mich schonmal für die Gedankenanstöße hier aus dem Thread, das hat schon mal sehr geholfen Smile

BlitzMax: [AUSKLAPPEN] 
SuperStrict

Framework BRL.StandardIO
	Import BRL.LinkedList
	Import BRL.Map

Type TTestData
	Field Name:String
	Field ObjektVerweis:TTestData
	
	Method CheckRecursionTMap:Byte()
		Local ChainList:TMap = New TMap 'Ggf. Global für Multiple Verweise
		
		If Not Self.ObjektVerweis Then Return False 'Es gibt keinen Verweis mehr, Ketten Ende
		Local SearchObject:TTestData = Self
		
		While Not ChainList.Contains(SearchObject) 'So lange suchen bis wir auf unsere Kette treffen
			ChainList.Insert(SearchObject,SearchObject) 'Glied der Kette hinzufügen
			SearchObject = SearchObject.ObjektVerweis
			If Not SearchObject Then Return False 'Es gibt keinen Verweis mehr, Ketten Ende
		Wend
		
		Return True
	EndMethod
	
	Method CheckRecursionTList:Byte()
		Local ChainList:TList = New TList 'Ggf. Global für Multiple Verweise
		
		If Not Self.ObjektVerweis Then Return False 'Es gibt keinen Verweis mehr, Ketten Ende
		Local SearchObject:TTestData = Self
		
		While Not ChainList.Contains(SearchObject) 'So lange suchen bis wir auf unsere Kette treffen
			ChainList.AddLast(SearchObject) 'Glied der Kette hinzufügen
			SearchObject = SearchObject.ObjektVerweis
			If Not SearchObject Then Return False 'Es gibt keinen Verweis mehr, Ketten Ende
		Wend
		
		Return True
	EndMethod
EndType

'Objekte erstellen
Local TestData:TTestData[1000]
For Local I:Int = 0 To TestData.Dimensions()[0]-1
	TestData[I] = New TTestData
	TestData[I].Name = "Test Datensatz "+(I)
Next

'Verweise
For Local I:Int = 0 To TestData.Dimensions()[0]-1
	TestData[I].ObjektVerweis = TestData[(I+1) Mod TestData.Dimensions()[0]]
Next

Print "Checking with " + TestData.Dimensions()[0] + " objects recursive chain:"

For Local Kind:Int = 0 To 1
	Local start:Int = MilliSecs()
	
	'Ergebnisse?
	For Local I:Int = 0 To TestData.Dimensions()[0]-1
		If Kind = 0 Then TestData[I].CheckRecursionTMap()
		If Kind = 1 Then TestData[I].CheckRecursionTList()
		'Print TestData[I].Name + " Rekursiv: " + TestData[I].CheckRecursion() + "~n"
	Next
	
	If kind = 0 Then Print "~tTMap Method: " + (MilliSecs()-start) + " ms"
	If kind = 1 Then Print "~tTList Method: " + (MilliSecs()-start) + " ms"
Next

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Allgemein

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group