Das deutsche Python-Forum

Hallo zusammen,

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()

Schau dir mal die Datenstruktur "Baum" an.
Damit dürftest du dein Problem um einiges übersichtlicher und effizienter lösen.
http://de.wikipedia.org/wiki/Baum_%28Graphentheorie%29

Meine Idee wäre, zuerst die Liste in Sublisten einzuteilen, die Elemente gleicher Dependencies-Länge enthalten. Die Wahrscheinlichkeit, daß man Elemente verschieben muss, erhöht sich natürlich mit der Anzahl der Abhängigkeiten. Dann kann man bei der der Subliste mit den meisten Abhägigkeiten pro Element anfangen und zuerst überprüfen, ob man das Element in der gleichen Liste verschieben muss, oder ob man es um eine Liste nach vorne verrücken muss. Das wichtige bei dieser Sortierung ist ja, daß es nur auf die Abhängigkeiten ankommt - wo die Elemente am Ende landen ist relativ egal, solange eben die Abhängigkeiten eingehalten werden. Da dürfte diese Methode doch die Essenz der Sortierung (Eigene Subliste / Um eine Subliste vorrücken) enthalten. Sollte man mehrere Iterationen benötigen, um die Liste zu sortieren, hat man BubbleSort und kann dann versuchen, die Geschichte mit einem besseren Algorithmus zu lösen.

man kann auf jeden fall die objekte als graph sehen und davon ausgehend das problem mit einer einfachen tiefensuche loesen. steht z.B. im WP artikel zu Topological sorting beschrieben.

edit: der pseudocode von dort laesst sich sogar zeilenweise 1:1 uebersetzen

Code: Alles auswählen

def topological_sort(obj):
    visited = {key: False for key in obj}
    result = []

    def visit(node):
        if not visited[node]:
            visited[node] = True
            for n in obj[node]:
                visit(n)
            result.append(node)

    for key in obj:
        visit(key)

    return result

if __name__ == '__main__':
    objects = { "a": ["d"],
                "c": ["k", "b"],
                "k": [],
                "d": [],
                "f": ["k"],
                "b": ["a"],
    }

    l = topological_sort(objects)
    print(l)

Code: Alles auswählen

visited = {key: False for key in obj}

Zumindest bis Python 2.6 ergibt das einen Syntax-Error. Es müsste heißen:

Code: Alles auswählen

visited = dict((key, False) for key in obj)

MfG
HWK

HWK hat geschrieben:
Code: Alles auswählen
visited = {key: False for key in obj}
Zumindest bis Python 2.6 ergibt das einen Syntax-Error. Es müsste heißen:
Code: Alles auswählen
visited = dict((key, False) for key in obj)

Für Python 3.x ist das korrekt - "dictionary comprehension".

crs hat geschrieben:man kann auf jeden fall die objekte als graph sehen und davon ausgehend das problem mit einer einfachen tiefensuche loesen. steht z.B. im WP artikel zu Topological sorting beschrieben.

Danke für den Tipp!

Hatte parallel auch meinen Testcode mit dieser "depth-first search" erweitert, gefällt mir eigentlich ganz gut

Code: Alles auswählen

def sort_by_dependency(objects):
    obj_map = dict((o.key, o) for o in objects)
    dsorted = []

    def visit(obj):
        if not hasattr(obj, "visited"):
            obj.visited = True
            for k in obj.dependencies:
                try:
                    visit(obj_map[k])
                except KeyError:
                    raise ValueError(
                        ("object %s refers to a not existing object %s!"
                         % (obj.key, k))
                    )
            dsorted.append(obj) 

    for obj in objects:
        visit(obj)
    if len(dsorted) != len(objects):
        raise ValueError(
            "couldn't sort the objects, they might have cyclic dependencies!"
        )        
    return dsorted

Der letzte Vergleich auf Basis der Länge war quatsch, auch die Objekte mit einem "visited" Attribut zu versehen ist keine gute Idee bei mehrmaligem durchlaufen geht das ins Auge

So ist das ganze schon besser aber ich hab aktuell noch das Problem das zyklische Abhängigkeiten nicht erkannt werden.

Code: Alles auswählen

def sort_by_dependency(objects):
    obj_map = dict((o.key, o) for o in objects)
    visited = dict.fromkeys(objects)
    dsorted = []

    def visit(obj):
        if not visited[obj]:
            visited[obj] = True
            for k in obj.dependencies:
                try:
                    visit(obj_map[k])
                except KeyError:
                    raise ValueError(
                        ("Object %s refers to a not existing object %s!"
                         % (obj.key, k))
                    )
            dsorted.append(obj) 

    for obj in objects:
        visit(obj)       
    return dsorted

Hab vor einigen Jahren mal ``tsort`` aus den coreutils nachgebaut: tsort.py. Hmm, vielleicht sollte ich da ein paar Korrekturen anbringen..

Zap hat geschrieben:So ist das ganze schon besser aber ich hab aktuell noch das Problem das zyklische Abhängigkeiten nicht erkannt werden.

Bei Zykeln kannst du dein ursprüngliches Ziel nicht erreichen. Was genau soll dann passieren?

bords0 hat geschrieben:Bei Zykeln kannst du dein ursprüngliches Ziel nicht erreichen. Was genau soll dann passieren?

Dem User der diese Abhängigkeiten festgelegt hat soll der Fehler um die Ohren gehauen werden

Ich habe ja eine primitive Lösung um heraus zu finden ob alle Abhängigkeiten aufgelöst werden können. Mir persönlich reicht das, aber ich bin halt immer daran interessiert wenn jemand eine bessere Lösung hat.

Zap hat geschrieben:Dem User der diese Abhängigkeiten festgelegt hat soll der Fehler um die Ohren gehauen werden

Dann prüf halt vor dem Einfügen einer Abhängigkeit, ob sich damit ein Zyklus ergibt oder nicht.

Das deutsche Python-Forum

Verbesserungsvorschläge für das Sortieren nach Abhängigkeit

Verbesserungsvorschläge für das Sortieren nach Abhängigkeit