Verfahrgeschwindigkeit und Modifizieren einer baumartigen Liste der dict Struktur

Question

ich eine Struktur haben, die wie folgt aussieht:

[ {'id': 4, 'children': None}, 
    {'id': 2, 'children': 
    [ {'id': 1, 'children': 
     [ {'id': 6, 'children': None}, 
      {'id': 5, 'children': None} ] 
     }, 
     {'id': 7, 'children': 
     [ {'id': 3, 'children': None} ] 
     } 
    ] 
    } 
] 

Ich habe auch eine Liste der ausgewählten IDs, [4, 5, 6, 7]. Ich möchte die Liste durchqueren und für jedes Objekt in der Liste einen selected Schlüssel mit einem Wert von 1 hinzufügen, wenn dieser ausgewählt ist, und 0, wenn dies nicht der Fall ist.

Zur Zeit mache ich das rekursiv mit dieser Funktion:

def mark_selected(tree, selected): 
    for obj in tree: 
     obj['selected'] = 1 if obj['id'] in selected else 0 
     if obj['children'] is not None: 
      obj['children'] = mark_selected(obj['children'], selected) 
    return tree 

Dies scheint gut zu funktionieren, aber ich frage mich, ob es eine kluge Art und Weise war, dies zu tun, möglicherweise Liste Verständnis oder Generatoren.

Kann jemand eine elegantere Lösung dafür finden?

Answer 1

Rekursion ist perfekt elegant. List-Comprehensions gelten nicht, da Sie die Struktur an Ort und Stelle ändern, anstatt eine neue Sequenz zu erzeugen. Was Generatoren betrifft, könnten Sie einen DFS- oder BFS-Traverser schreiben.

def dfs(nodes): 
    if nodes is not None: 
     for node in nodes: 
      yield node 
      for child in dfs(node['children']): 
       yield child 

for node in dfs(tree): 
    if node['id'] in selected: 
     node['selected'] = true 

Wenn die Liste des IDs groß zu wählen, wäre es mehr performant sei es mit dem IDs als Schlüssel zu einem dict zu konvertieren, die Lookup beschleunigen wird (die node['id'] in selected).

selected = dict(zip(selected, selected)) 

Answer 2

Da Sie durch Modifizieren des Eingangsobjekts arbeiten, und da Objekte Referenzsemantik in Python haben, brauchen Sie keinen Wert oder verwenden Sie den Rückgabewert in dem rekursiven Schritt zurückzukehren. Wenn Sie die 'None'-Einträge für Kinder durch' [] 'ersetzen können (besser noch Tupel anstelle von Listen verwenden), dann können Sie die Logik vereinfachen - Sie brauchen keinen Basisfall, weil Sie zu einem "leeren Baum" zurückkehren können, und es wird nur die for-Schleife für alle Null-Elemente laufen lassen, dh nichts tun - was Sie wollen.

Und FFS, warum verwenden Sie nicht Pythons eingebauten booleschen Typ?

def mark_selected(tree, selected): 
    for obj in tree: 
     obj['selected'] = obj['id'] in selected 
     mark_selected(obj['children'], selected) 

(Oh, und tun Sie sogar die Kinder in einer bestimmten Reihenfolge zu halten, müssen eine Liste von dicts, die alle ein ‚id‘ Schlüssel enthalten sind unnatürlich,? Es mehr Sinn macht, eine dict zu haben, wo die Schlüssel sind die IDs, und die Werte sind dicts ohne die 'ID'.)

Answer 3

Ich mag Verschlüssen für rekursive Funktionen verwenden, für dieses Beispiel ist es nicht sehr wichtig, aber Sie können die Notwendigkeit speichern übergeben 'ausgewählt 'im rekursiven Aufruf. In komplexeren Beispielen können Sie in der containing-Funktion einen guten Teil des Status für die Rekursion beibehalten.

def mark_selected(tree, selected): 
    def recur(tree): 
     for obj in tree: 
       obj['selected'] = 1 if obj['id'] in selected else 0 
       if obj['children'] is not None: 
        recur(obj['children']) 
    recur(tree)