Moin!
Vorgeschichte:
Ich bastel gerade an einem prototypbasierten Objektsystem. Dabei habe ich das Problem, dass ich gerne bei Mehrfachvererbung (Mehrfachdelegation) einen Fehler werfen würde, wenn ein Slot von mehr als einem Prototypobjekt angeboten wird. Da die Prototypbeziehung ähnlich wie Self dynamisch modifizierbar ist, habe ich einen vollständigen Graphen und keinen gerichteten azyklischen Graphen; zudem muss ich wegen der möglichen dynamischen Änderung diese Prüfung bei jedem Slotzugriff machen.

Problem:
a) Markierungen der Objekte ist nicht möglich, da das nicht Threadsicher ist.
b) Ich kann die Objekte nicht hashen und auch keine totale Ordnung definieren, von daher keine Table und kein Tree für den lookup (wobei hierbei der Effizienzgewinn wegen des für gewöhnlich recht kleinen Graphen fraglich ist).
c) Der Algorithmus zur Zyklendetektion mit einem "Läufer" ist ungeeignet, da das bei unglücklicher Zyklenlänge recht lange dauern kann bis der terminiert. Ein Zyklus ist ja per se noch kein Fehler.

Bleibt
d) Visited-Liste mit O(n^2) Zeit und O(n) Platzkomplexität. Insbesondere die Alloziierung der Liste beisst dabei.

Frage:
Kennt jemand einen effizienteren Algorithmus?

Habe ich das richtig verstanden, dass in einer
Vererbungshierarchie herausgefunden werden soll,
ob eine Mehrfachvererbung auf eine gemeinsame
Basisklasse (oder Prototypobjekt) zurückgeht?

(Ich kenne prototypbasierte Objektsysteme nicht)

vollständigen Graphen

Vollständig aber nicht in dem Sinne, dass je zwei Knoten
verbunden sind, oder? (dann wäre Zyklendetektion nicht
so spannend)


Also ich kenne mich zwar mit Graphen nicht sonderlich gut aus,
und weiß z.B. nicht, was ein "Läufer" ist, aber ich schreibe
mal meine Ideen auf, auf die Gefahr hin, dass du die auch schon
hattest und sie in a)-d) schon ausgeschlossen hast [img]http://www.fb18.de/gfx/23.gif[/img]


Soll denn (1.) der komplette Graph auf Zyklenfreiheit geprüft
werden oder (2.) immer nur, ob ein momentan verwendetes Objekt
Teil eines Zyklus ist?

Im ersten Fall ist es doch evtl. sinnvoller, diese Prüfung
(nur) bei jeder Änderung des Graphen durchzuführen. Falls
zum Graphen auch noch häufig etwas hinzugefügt werden soll
und selten etwas entfernt (vielleicht gibt es ja eine Müllabfuhr),
würde ich folgendes Verfahren mit O(n)-Zeit und O(n^2)-Platz
(der Platz muss aber nicht jedes mal alloziiert werden) vorschlagen:

Jeder Knoten erhält eine Liste mit (auch indirekt) erreichbaren
Knoten. Dann muss man beim Einfügen einer Kante nur die Listen der
neu verbundenen Knoten übernehmen und sieht direkt, ob ein Zyklus
entsteht. (Eine totale Ordnung wäre natürlich prima, dann
könnte man festlegen, wer wessen Erreichbarkeit speichert, aber
wenn das nicht geht… Aber vielleicht meinst du auch eine totale
Ordnung, die mit der Kanten-Relation verträglich ist,
kläre mich bitte auf [img]http://www.fb18.de/gfx/23.gif[/img])

Ansonsten würde mir noch folgender Algorithmus einfallen.
Der braucht zwar auch O(n^2) Zeit und O(n) Platz, aber
man weiss z.B. vorher, wieviel alloziiert werden muss:

Man lösche (in einer Kopie) schrittweise alle Knoten mit
Grad <=1 (ich gehe mal davon aus, dass Schlingen nicht zugelassen
sind). Wenn dann noch Knoten übrig sind, hat man einen Zyklus
(denn dann hat jeder Knoten mindestens Grad 2 und man kann
sich von Knoten zu Knoten hangeln und kommt mithilfe des
Schubfachschlusses irgendwann wieder bei einem bereits
besuchten an; die Vollständigkeit ist noch offensichtlicher).

Habe ich das richtig verstanden, dass in einer
Vererbungshierarchie herausgefunden werden soll,
ob eine Mehrfachvererbung auf eine gemeinsame
Basisklasse (oder Prototypobjekt) zurückgeht?

Mehrfachvererbung ist kein Problem, aber da ich den "Parent" (bzw. den "Prototyp", das ist das gleiche) zur Laufzeit dynamisch ändern kann, kann dabei ein Zyklus auftreten. Das will ich als Fehler markieren, da dadurch die normalen Lookup-Algorithmen in eine Endlosschleife geraten, und "A erbt von B erbt von C erbt von A" auch konzeptuell irgendwie komisch ist.

(Ich kenne prototypbasierte Objektsysteme nicht)

Objekte sind Sammlungen von benamten Slots. Ein Objekt hat einen (oder mehr) "parent"/"prototyp"-pointer (normalerweise auch slots). Wenn ein Slot in einem Objekt nicht gefunden wird, wird bei den parents geguggt etc.

Objekte werden erstellt, indem man ein Objekt (den "Prototyp") kopiert. Kopieren geht trivial mit leerem Objekt und parent auf Prototyp. Man könnte sagen, dass der "Prototyp" die "Klasse" des neuen Objektes ist - nur, dass die Klasse ein ganz normales Objekt ist (wie in CLOS, aber nicht irgendwie speziell sein muss).

vollständigen Graphen

Vollständig aber nicht in dem Sinne, dass je zwei Knoten
verbunden sind, oder? (dann wäre Zyklendetektion nicht
so spannend)

Äh, ich meinte "vollständig" im Gegensatz zum gerichteten azyklischen graphen, d.h. eben einer mit Zyklen, nicht ungerichtet - sorry :-)

Also ich kenne mich zwar mit Graphen nicht sonderlich gut aus,
und weiß z.B. nicht, was ein "Läufer" ist

Alter Trick zur Zyklendetektion in Listen und Bäumen. Du gehst durch die Struktur nicht einmal, sondern zweimal, gleichzeitig. D.h. du updatest zwei pointer. Der eine geht immer einen Schritt - das ist der normale - und einer geht zwei Schritte - der "Läufer". Wenn irgendwann Läufer=Aktuell ist, hast du nen Zyklus. Platzeffizient O(1) und Rechenzeiteffizient O(2n). Klappt nur nicht mehr in einem DAG.

Hat auch den Nachteil, dass man sich im Zyklus trifft, nicht am Beginn desselbigen.

Soll denn (1.) der komplette Graph auf Zyklenfreiheit geprüft
werden oder (2.) immer nur, ob ein momentan verwendetes Objekt
Teil eines Zyklus ist?

Im ersten Fall ist es doch evtl. sinnvoller, diese Prüfung
(nur) bei jeder Änderung des Graphen durchzuführen.

Yep, das werde ich wohl so machen.

Falls
zum Graphen auch noch häufig etwas hinzugefügt werden soll
und selten etwas entfernt (vielleicht gibt es ja eine Müllabfuhr),
würde ich folgendes Verfahren mit O(n)-Zeit und O(n^2)-Platz
(der Platz muss aber nicht jedes mal alloziiert werden) vorschlagen:

Jeder Knoten erhält eine Liste mit (auch indirekt) erreichbaren
Knoten. Dann muss man beim Einfügen einer Kante nur die Listen der
neu verbundenen Knoten übernehmen und sieht direkt, ob ein Zyklus
entsteht. (Eine totale Ordnung wäre natürlich prima, dann
könnte man festlegen, wer wessen Erreichbarkeit speichert, aber
wenn das nicht geht… Aber vielleicht meinst du auch eine totale
Ordnung, die mit der Kanten-Relation verträglich ist,
kläre mich bitte auf [img]http://www.fb18.de/gfx/23.gif[/img])

Hm. Sinnvoll, danke!
Stellt sich nur die Frage, ob ich den Platzverbrauch pro Knoten zahlen will. Ich sollte mir langsam mal Gedanken machen wie oft sich da was am Parent ändern wird :-]

Ansonsten würde mir noch folgender Algorithmus einfallen.
Der braucht zwar auch O(n^2) Zeit und O(n) Platz, aber
man weiss z.B. vorher, wieviel alloziiert werden muss:

Ich kenne die Größe des Graphen nicht :-)

Man lösche (in einer Kopie) schrittweise alle Knoten mit
Grad <=1 (ich gehe mal davon aus, dass Schlingen nicht zugelassen
sind). Wenn dann noch Knoten übrig sind, hat man einen Zyklus
(denn dann hat jeder Knoten mindestens Grad 2 und man kann
sich von Knoten zu Knoten hangeln und kommt mithilfe des
Schubfachschlusses irgendwann wieder bei einem bereits
besuchten an; die Vollständigkeit ist noch offensichtlicher).

Hm. Die erste Alternative klang sinnvoller :-)

Danke dir!

Moin!
Vorgeschichte:
Ich bastel gerade an einem prototypbasierten Objektsystem. Dabei habe ich das Problem, dass ich gerne bei Mehrfachvererbung (Mehrfachdelegation) einen Fehler werfen würde, wenn ein Slot von mehr als einem Prototypobjekt angeboten wird. Da die Prototypbeziehung ähnlich wie Self dynamisch modifizierbar ist, habe ich einen vollständigen Graphen und keinen gerichteten azyklischen Graphen; zudem muss ich wegen der möglichen dynamischen Änderung diese Prüfung bei jedem Slotzugriff machen.

Ich kenne leider keinen Alg. dafür, aber es würde mich interessieren wie dein Objektsystem im vergleich zum Common Lisp Object System aussieht?

Ich kenne leider keinen Alg. dafür, aber es würde mich interessieren wie dein Objektsystem im vergleich zum Common Lisp Object System aussieht?

CLOS basiert auf generic multi-dispatch, d.h. Methoden, die aufgrund des Typs der Argumente einen Dispatch an die passende Methode machen. Damit sind die Methoden nicht mehr Bestandteil der Objekte/Klassen, sondern nur noch darüber definiert. Objekte sind nur noch records, d.h. name->value mappings, und haben einen Typ.

Zudem ist CLOS "in sich selbst" implementiert, d.h. man hat über das Meta-Object Protocol die Möglichkeit die Arbeitsweise des Systems zu ändern. Klassen sind dadurch auch "nur" Objekte - ganz spezieller Natur, aber eben "nur" Objekte.

Prototypbasierte Objektsysteme schmeissen das gesonderte Konzept der Klasse ganz über den Haufen. Alles ist ein Objekt, alles kann als Prototyp dienen. Dafür haben Objekte wiederum integriert in sich Methoden, die aufgerufen werden können - d.h. Methoden sind wieder (wie in Smalltalk) direkt mit dem Objekt verbunden, und nicht nur über die Typen definiert.

Letzteres ist wohl auch der größte praktische Unterschied. Während die Methoden von CLOS über den Typ jedes Argumentes spezifiziert werden können, werden bei Smalltalk- und Prototypbasierten Objektsystemen die Methoden alleine anhand des Typs des ersten Arguments ausgewählt.

Siehe auch: http://en.wikipedia.org/wiki/Prototype-based_programming

(Liste der indirekt erreichbaren Knoten)

Stellt sich nur die Frage, ob ich den Platzverbrauch pro Knoten zahlen will. Ich sollte mir langsam mal Gedanken machen wie oft sich da was am Parent ändern wird :-]

Wie gesagt kannst du da ja noch ein bisschen sparen, mit einer
Ordnung auf den Knoten: dann speichert immer nur der kleinere,
welche größeren von ihm aus erreichbar sind. Aber du sagtest ja,
eine totale Ordnung sei nicht möglich; heißt das, dass das
Verfahren "Versuche, eine totale Ordnung zu definieren, was genau
dann scheitert, wenn ein Zyklus existiert" nicht anwendbar ist,
oder, dass du überhaupt keine totale Ordnung definieren kannst?
Letzteres würde mich nämlich wundern, du könntest doch zumindest
den Zeitpunkt der Erzeugung heranziehen (oder werden die Objekte
verteilt erzeugt?).

Aber du sagtest ja,
eine totale Ordnung sei nicht möglich; heißt das, dass das
Verfahren "Versuche, eine totale Ordnung zu definieren, was genau
dann scheitert, wenn ein Zyklus existiert" nicht anwendbar ist,
oder, dass du überhaupt keine totale Ordnung definieren kannst?
Letzteres würde mich nämlich wundern, du könntest doch zumindest
den Zeitpunkt der Erzeugung heranziehen (oder werden die Objekte
verteilt erzeugt?).

Ich könnte Objekten eine ID mitgeben, ja. Das wollte ich eigentlich nur für den Fall der Fehlerentdeckung vermeiden :-)

Ich könnte Objekten eine ID mitgeben, ja. Das wollte ich eigentlich nur für den Fall der Fehlerentdeckung vermeiden :-)

Achso, wegen den Kanonen und den Spatzen, verstehe [img]http://www.fb18.de/gfx/28.gif[/img]

Habs mal ausgerechnet, der Vorteil wäre: höchstens (n^2-n)/2
Einträge statt bis zu n^2.

Ich vermute mal ich könnte bei der Änderung des Graphen einfach ne normale Zyklendetektion mit visited-list machen. Die Graphen sollten ja nicht all zu groß werden. Ich hatte es irgendwie verpeilt, dass ich das bei der Modifikation machen kann, statt nur beim Zugriff. *grübel*

Danke an alle :-)