ich habe das Problem das ich eine Menge von Objekten die von einander Abhängig sind in die richtige Reihenfolge bringen möchte.
Habe den Anwendungsfall mal auf ein kleines Testskript beschränkt und dabei eine erste Prototyp-Lösung gefunden. Bin aber der Meinung das es bessere Wege geben muss.
Für meinen Anwendungsfall reicht die Laufzeit aber effizient ist sie trotzdem nicht.
Vielleicht hat ja einer von euch eine pfiffige Idee wie man die Objekte schneller sortieren kann, so dass die Abhängigkeiten klar eingehalten werden.
Das Ziel: Eine zufällige Liste von Objekten soll so sortiert werden, dass beim iterieren ein Objekt erst zurückgegeben wird bevor man ein Objekt bekommt welches auf dieses referenziert.
Hier mein Testcode:
Code: Alles auswählen
class Obj:
def __init__(self, key, dependencies):
self.key = key
self.dependencies = dependencies
def __repr__(self):
return "%s%s" % (self.key, self.dependencies)
def sort_by_dependency(objects):
dsorted = []
for obj in objects:
if not obj.dependencies:
dsorted.insert(0, obj)
else:
pos = len(dsorted)
for i, saved_obj in enumerate(dsorted):
if obj.key in saved_obj.dependencies:
pos = i
break
dsorted.insert(pos, obj)
return dsorted
def is_dependency_clean(objects):
keys = [o.key for o in objects]
for i, obj in enumerate(objects):
for dep in obj.dependencies:
if dep not in keys[:i]:
print "couldn't resolve dependency %s" % dep
return False
return True
if __name__ == "__main__":
def test():
dsorted = sort_by_dependency(objects)
print is_dependency_clean(dsorted), dsorted
objects = [
Obj("a", ["d"]),
Obj("c", ["k", "b"]),
Obj("k", []),
Obj("d", []),
Obj("f", ["k"]),
Obj("b", ["a"]),
]
# objects valid
test()
# make objects invalid ("a" couldn't be dependent from "c")
objects[0].dependencies.append("c")
test()
