Verzeichnisstruktur abbilden

[anogayales]

Hallo allerseits,

nachdem ich jetzt weiß wie ich über ein Dictionary beliebiger Tiefe scannen kann http://www.python-forum.de/viewtopic.php?f=1&t=26453, kommt hier jetzt die Anwendung.

Ich bekomme Daten in der Form von

Code: Alles auswählen

Directory = namedtuple('Dir', ['id', 'name', 'parentid'])

sprich, jedes Verzeichnis hat eine ID und eine ParentID. Von dem Ausgehend bau ich mir eine Verzeichnisstruktur auf.

Das Problem ist nun, dass ich keine Annahme über die Reihenfolge der Daten machen kann. Es kann also vorkommen, dass ein Verzeichnis auftaucht, für den es noch keinen Parent gibt.

Das ganze hab ich mit random.shuffel gelöst. Ich handel mir aber mit der Lösung ein nicht-deterministisches verhalten ein: Das Programm könnte beliebig lang rumrattern.

Bisher sieht das ganze so aus:

Code: Alles auswählen

        from random import shuffle
        while unsorted_dirs:
            shuffle(unsorted_dirs)
            no_parent = unsorted_dirs.pop()
            found = False
            scan = iter_deep(folder_hierarchy)
            for pair in scan:
                dir, contents = pair
                if dir.id == no_parent.parentid:
                    contents[no_parent] = {}
                    found = True
                    break
            if not found:
                # Parent not found in folder hierarchy, adding to list
                unsorted_dirs.append(no_parent)
                found = False

Kleine Anmerkung: Directories mit parentid 0 sind im Hauptverzeichnis. Die habe ich vorher schon in die Verzeichnisstruktur hinzugefügt.

Vollständigkeits halber: iter_deep is so definiert:

Code: Alles auswählen

def iter_deep(input):
    for key, value in input.iteritems():
        if isinstance(value, dict):
            yield key, value
            for i in iter_deep(value):
                yield i
        else:
            yield key, value

Geht das vielleicht auch ohne die Directory Klasse, oder vielleicht ganz anders?

Grüße,
anogayales

[BlackJack]

@anogayales: Ich würde statt eines Tupels ein veränderbares `Directory` erstellen — also ganz normal als Klasse. Die kannst Du dann erstellen und in ein Dictionary stecken, das ID auf `Directory`-Exemplar abbildet.@anogayales: Ich würde statt eines Tupels ein veränderbares `Directory` erstellen — also ganz normal als Klasse. Die kannst Du dann erstellen und in ein Dictionary stecken, das ID auf `Directory`-Exemplar abbildet. Und dann kannst Du doch ganz einfach einmal da durchgehen und die entsprechenden Objekte mit Verweisen verbinden. Und dann kannst Du doch ganz einfach einmal da durchgehen und die entsprechenden Objekte mit Verweisen verbinden.

[anogayales]

Ich glaub mit deinem Post stimmt was nicht

Ich will halt das am Ende ein Dictionary rauskommt, dass ähnlich einer Verzeichnisstruktur ist. Eigentlich hatte ich gar nicht vor dafür eine extra Klasse zu erstellen.

Ja, was mach ich denn, falls es das Parent Objekt noch nicht gibt? So ganz versteh ich das nicht was du mir da sagen willst . Den ohne Parent kann ich ja auch keinen Verweis von Parent auf Kind erstellen.

Grüße,
anogayales

[BlackJack]

@anogayales: Du erstellst erst *alle* Objekte/Dictionaries, und dann verbindest Du die, die zusammengehören. Dann gibt es auch nicht das Problem das es ein Objekt/Dictionary noch nicht gibt.

[anogayales]

Danke, manchmal sieht man den Wald für lauter Bäumen nicht mehr

Das ganze hab ich jetzt über zwei Schleifen gelöst, sprich Quadratische Laufzeit.

Code: Alles auswählen

        for first_dir in flat:
            for second_dir in flat:
                if first_dir.id == second_dir.parentid:
                    first_dir.children[second_dir.id] = second_dir
 

Mein Directory sieht übrigens so aus:

Code: Alles auswählen

class Directory(object):

    def __init__(self, id, name, parent_id):
        self.id = id
        self.name = name
        self.parentid = parent_id
        self.children = {}

Geht das irgendwie besser, vielleicht hab ich mal wieder ein bisschen zu kompliziert gedacht?

Grüße,
anogayales

[BlackJack]

@anogayales: Klar geht das besser. Schrob ich doch schon: in einem ersten Durchlauf alle Objekte erzeugen und in ein Dictionary ID→Objekt stecken und im zweiten Durchlauf dann jedes Objekt verbinden. Lineare statt quadratische Laufzeit.

Code: Alles auswählen

        id2directory = dict((d.id, d) for d in flat)
        for directory in flat:
            id2directory[directory.parentid].children[directory.id] = directory

[anogayales]

Vielen Dank!

Zuerst schien mir deine Lösung offensichtlich falsch, da sie sich ja nur im Toplevel bewegt. Aber nach genauem hingucken verbindet man ja nur auf der Toplevel Ebene alles und das wirkt sich ja dank veränderbaren Objekten auf die anderen Objekte aus.


Grüße,
anogayales