Konstruktion

frozenmap implementiert eine dict-ähnliche Konstruktions-API

• frozenmap() erstellt ein neues leeres unveränderliches Mapping;
• frozenmap(**kwargs) erstellt ein Mapping aus **kwargs, z. B. frozenmap(x=10, y=0, z=-1)
• frozenmap(collection) erstellt ein Mapping aus dem übergebenen collection-Objekt. Das übergebene collection-Objekt kann sein
  • ein dict,
  • ein weiteres frozenmap,
  • ein Objekt mit einer items()-Methode, das eine Reihe von Schlüssel/Wert-Tupeln zurückgeben soll, oder
  • ein Iterable von Schlüssel/Wert-Tupeln.

Datenzugriff

frozenmap implementiert das Protokoll collection.abc.Mapping. Daher funktionieren Getter, Mitgliedsprüfungen und Iteration genauso wie bei einem dict.

m = frozenmap(foo='bar')

assert m['foo'] == 'bar'
assert m.get('foo') == 'bar'
assert 'foo' in m

assert 'baz' not in m
assert m.get('baz', 'missing') == 'missing'

assert m == m
assert m != frozenmap()  # m is not equal to an empty frozenmap

assert len(m) == 1

# etc.

Mutation

frozenmap-Instanzen sind unveränderlich. Dennoch ist es möglich, mutierte Kopien der unveränderlichen Instanz effizient zu erzeugen.

Die Komplexität von Mutationsoperationen beträgt O(log N), und die resultierenden frozenmap-Kopien verbrauchen aufgrund der Verwendung von strukturellem Teilen oft nur sehr wenig zusätzlichen Speicher (siehe [6] für weitere Details).

m = frozenmap(foo=1)
m2 = m.including('bar', 100)

print(m)   # will print frozenmap({'foo': 1})
print(m2)  # will print frozenmap({'foo': 1, 'bar': 100})

m = frozenmap(foo=1, bar=100)

m2 = m.excluding('foo')

print(m)   # will print frozenmap({'foo': 1, 'bar': 100})
print(m2)  # will print frozenmap({'bar': 1})

m3 = m.excluding('spam')  # will throw a KeyError('spam')

m = frozenmap(foo=1)

m2 = m.union({'spam': 'ham'})
print(m2)  # will print frozenmap({'foo': 1, 'spam': 'ham'})

m3 = m.union(foo=100, y=2)
print(m3)  # will print frozenmap({'foo': 100, 'y': 2})

print(m)   # will print frozenmap({'foo': 1})

numbers = frozenmap((i, i ** 2) for i in range(1_000_000))

with numbers.mutating() as copy:
    for i in numbers:
        if not (numbers[i] % 997):
            del copy[i]

    numbers_without_997_multiples = frozenmap(copy)

    # at this point, *numbers* still has 1_000_000 key/values, and
    # *numbers_without_997_multiples* is a copy of *numbers* without
    # values that are multiples of 997.

    for i in numbers:
        if not (numbers[i] % 593):
            del copy[i]

    numbers_without_593_multiples = frozenmap(copy)

    print(copy[10])  # will print 100.

print(copy[10])  # This will throw a ValueError as *copy*
                 # has been closed when the "with" block
                 # was executed.

Iteration

Da frozenmap das Standardprotokoll collections.abc.Mapping implementiert, werden alle erwarteten Iterationsmethoden unterstützt.

assert list(m) == ['foo']
assert list(m.items()) == [('foo', 'bar')]
assert list(m.keys()) == ['foo']
assert list(m.values()) == ['bar']

Die Iteration in frozenmap bewahrt, im Gegensatz zu dict, nicht die Einfügungsreihenfolge.

Hashing

frozenmap-Instanzen können, ähnlich wie tuple-Objekte, hashable sein.

hash(frozenmap(foo='bar'))  # works
hash(frozenmap(foo=[]))     # will throw an error

Typisierung

Es ist möglich, die Standard-Typisierungsschreibweise für frozenmaps zu verwenden.

m: frozenmap[str, int] = frozenmap()

HAMT

Der Hauptvertragsbestandteil von HAMT ist die Garantie eines vorhersagbaren Werts bei gegebenem Hash eines Schlüssels. Für ein Paar aus Schlüssel und Wert kann der Hash des Schlüssels verwendet werden, um den Speicherort des Werts im Hash-Map-Baum zu bestimmen.

Unveränderliche Mappings, die mit HAMT implementiert sind, haben eine O(log N) Leistung für set()- und get()-Operationen. Diese Effizienz ist möglich, da Mutationsoperationen nur einen Zweig des Baumes beeinflussen, was die Wiederverwendung nicht mutierter Zweige und somit die Vermeidung von Kopien unveränderter Daten ermöglicht.

Lesen Sie mehr über HAMT in [5]. Die CPython-Implementierung [1] enthält ebenfalls eine recht detaillierte Beschreibung des Algorithmus.

Performance

Die obige Grafik zeigt, dass

• frozenmap, implementiert mit HAMT, eine nahezu O(1)-Leistung für alle gemessenen Dictionary-Größen aufweist.
• dict.copy() wird bei etwa 100-200 Elementen weniger effizient.

Abbildung 2 vergleicht die Lookup-Kosten von dict mit denen eines HAMT-basierten unveränderlichen Mappings. Die HAMT-Lookup-Zeit ist im Durchschnitt etwa 30 % langsamer als Python-Dict-Lookups. Dieser Leistungsunterschied besteht, da das Durchlaufen eines flachen Baumes weniger effizient ist als ein Lookup in einem flachen, kontinuierlichen Array.

Darüber hinaus, zitierend [6]: „[die Verwendung von HAMT] bedeutet, dass in der Praxis, obwohl Einfügungen, Löschungen und Lookups in einem persistenten Hash Array Mapped Trie eine rechnerische Komplexität von O(log n) haben, sie für die meisten Anwendungen effektiv konstante Zeit haben, da eine extrem große Anzahl von Einträgen erforderlich wäre, um einer Operation mehr als ein Dutzend Schritte abzuverlangen.“

Warum „frozenmap“ und nicht „FrozenMap“

Das Kleinbuchstaben-„frozenmap“ resoniert gut mit dem integrierten frozenset sowie mit Typen wie collections.defaultdict.

Warum „frozenmap“ und nicht „frozendict“

„Dict“ hat eine sehr spezifische Bedeutung in Python

• ein dict ist eine konkrete Implementierung von abc.MutableMapping mit O(1)-Get- und Set-Operationen (frozenmap hat O(log N)-Komplexität);
• Python-Dicts bewahren die Einfügungsreihenfolge.

Der vorgeschlagene frozenmap hat nicht diese genannten Eigenschaften. Stattdessen hat frozenmap Kosten von O(log N) für Set/Get-Operationen und implementiert nur das Protokoll abc.Mapping.