Ein verschachteltes Dictionary in Python managen (bzw. leeren)

Wir sichern Konfigurationen. Gehen wir für jetzt davon aus, dass wir mit Shops arbeiten und Preise für verschiedene Produkte pro Shop sichern möchten. Wir müssen aber einige Dinge berücksichtigen¹:

• Wir haben mehrere Länder zu beachten.
• Jedes Land hat verschiedene Standorte.
• Pro Standort haben wir viele Artikel.
• Den Artikel könnten wir noch in verschiedenen Größen haben.
• Schlussendlich habe ich pro Größe einen Preis.

Gehen wir davon aus, dass wir das alles in einem Dictionary sichern. Wenn die Daten nicht zu groß sind, klappt das gut - und wir können alles zusammen leicht in einem verschachtelten Dictionary sichern, zum Beispiel so:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

prices = {
    "AT": {
        "Graz": {
            "shoe": {
                "size-42": 99.99
            }
        }
    },
    "DE": { ... }
}

Das geht so auch wunderbar. Alle Preise werden per Kafka abgerufen, und jeder Downstream Consumer kann alle Preise live aktualisieren.

Aber dann kommt eine Lösch-Anfrage - zum Beispiel ist der Schuh in Größe 42 in Graz ab sofort nicht mehr verfügbar. Im Falle des obigen Dictionaries wollen wir dann alles bis inklusive AT aus dem Dictionary löschen, da darin jetzt alles leer ist.

Die Challenge

Die Lösung ist eigentlich simpel: Entferne die Größe, dann teste ob der Schuh noch verfügbare Größen hat. Wenn nicht, entferne den Schuh, dann teste ob Graz noch verfügbare Artikel hat. Und so weiter. Eine lange Liste an if Statements.

Nun habe ich aber nicht Mathematik und Algorithmentheorie studiert, um eine lange Liste an if Statements zu schreiben! Stattdessen denke ich lieber wesentlich länger darüber nach, wie ich das Problem in einem allgemeineren Fall lösen könnte - das englische Wort “over-engineering” fällt mir dazu ein. Dafür kann meine Lösung mit beliebig vielen verschachtelten Ebenen umgehen - was bei vielen if-Statements nicht ganz so elegant ausschaut.

Meine Lösung

Also ein anderer Weg. Das Problem ist offensichtlich rekursiv; ich habe allerdings einen semi-rekursiven Weg gewählt.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

keys = ["AT", "Graz", "shoe", "size-42"]
prices = ...

def delete_attribute(keys, prices)

    children = [prices]

    for key in keys[:-1]:
        if key not in children[-1]:
            # Falls einer der Keys nicht existiert,
            # kann ich direkt aufhören und
            # muss nichts löschen!
            return
        children.append(children[-1][key])

    # Jetzt lösche ich den gewünschten Schlüssel
    children[-1].pop(keys[-1], None)

    for key in reversed(keys[:-1]):
        if not children.pop(-1):
            children[-1].pop(key)
        else:
            # Dictionary ist nicht leer,
            # nicht löschen. Auch keine Parents
            # löschen!
            return

delete_attributes(keys, prices)

Beachte dass ich die relevanten Keys in einer sortierten Liste bekomme. Das ist wesentlich, damit auch der Rest funktioniert.

Ich habe das ganze Ding in eine Funktion gepackt - dadurch kann ich sehr einfach an jeder Stelle stoppen, ohne mir darum weiter Gedanken zu machen. Was passiert also:

• Ich erzeuge eine children Liste, in die ich das gesamte prices Element hineinlege.
• Jetzt laufe ich über jeden Teil des Keys, außer den letzten, in “Vorwärts”-Reihenfolge. Für jeden Teil des Keys wird ein weiteres, kleineres Objekt in die children Liste gelegt, mit dem entsprechenden Directory.
  • Falls mein Key nicht existiert, muss ich nichts löschen und kann direkt aufhören. Wenn wir zum Beispiel eine Lösch-Anfrage für Socken der Größe 43 in Graz bekommen, stellen wir fest dass wir sowieso keine Socken in Graz lagernd haben, und daher nichts tun müssen. In der for Schleife bedeutet das: Wenn key == "socks", gibt der Check key not in children[-1] ist wahr, und wir hören auf.
• Der relevante State ist hier offensichtlich das children Objekt. Wenn das erste for Loop durch ist, schaut das folgendermaßen aus:

  1 2 3 4 5 6

  [ {'AT': {'Graz': {'shoe': {'size-42': 99.99}}}}, # This is `prices` {'Graz': {'shoe': {'size-42': 99.99}}}, # prices["AT"] {'shoe': {'size-42': 99.99}}, # prices["AT"]["Graz"] {'size-42': 99.99} # prices["AT"]["Graz"]["shoe"] ]

  Beachte dass jedes Element eine Referenz auf einen Teil des prices Objekts ist. Dictionaries werden in Python per Referenz übergeben (sofern sie nicht explizit kopiert werden). Das hat zwei wichtige Vorteile:
  • Wenn ich ein Element in children bearbeite, ist diese Veränderung auch in prices sichtbar.
  • children benötigt fast keinen weiteren Speicherplatz, da wir nur ein paar Referenzen sichern. Nicht dass wir in Python über Effizienz sprechen sollten…
• Im letzten Element von children ist es jetzt denkbar einfach, den Schuh in Größe 42 zu entfernen.
• Und dann kommt ein zweites for Loop, das für das Aufräumen verantwortlich ist. Diesmal laufen wir durch die gleichen Keys wie vorher, allerdings in verkehrter Reihenfolge. Für jeden Key werfen wir zuerst das letzte Element aus children heraus. Das gibt genau das Dictionary für gerade diesen Key zurück.
  Diese Kombination aus herausnehmen und checken passiert kombiniert in Zeile 20. Zwei Fälle können eintreten:
  • Dieses Dictionary ist nicht leer. In diesem Fall können wir es nicht löschen, und sind an der Stelle fertig.
  • Falls das Dictionary leer ist, entfernen wir es aus dem Parent-Dictionary, das praktischerweise jetzt das letzte Dictionary in children ist.
    An dieser Stelle benötigen wir nicht einmal ein .pop(..., None), da wir ja wissen, dass dieser Key existiert!

Fazit

Das ist eine völlig zerdachte Version von einer ganzen Menge “if” Statements. Aber es hat einen wesentlichen Vorteil: Dieser Algorithmus in dieser Form kann für beliebige Tiefen von Arrays genutzt werden, und zwar mit linearem Zeit- und Speicheraufwand.