抽象

持久性数据结构定义为 修改数据时保留以前版本的数据。 这种数据结构实际上是不可变的，因为对 它们不会就地更新结构，而是始终屈服 新的更新结构（有关详细信息，请参见 [0]。

此 PEP 建议添加一个新的完全持久且不可变的映射 类型调用到模块。frozenmapcollections

的大部分 的参考实现已经 在 CPython 中用于实现模块。frozenmapcontextvars

理由

Python 有两种不可变的集合类型：和 。这些类型可用于表示不可变列表 和套装。但是，表示不可变映射的方法尚未实现 存在，并且此 PEP 建议实现 不可变映射。tuplefrozensetfrozenmap

建议的类型：frozenmap

• 实现协议，collections.abc.Mapping

• 支持酸洗，以及

• 提供用于高效创建“修改”版本的 API。

以下用例说明了为什么不可变映射是 合意：

• 不可变映射是可散列的，允许它们使用 作为字典键或设置元素。

  此可散列属性允许修饰的函数接受不可变映射 参数。与不可变映射不同，将 plAIn 传递给此类函数会导致错误。@functools.lru_cache()dict

• 不可变映射可以保持复杂状态。由于不可变映射 可以通过引用复制，状态的事务性突变可以 有效实施。

• 不可变映射可用于安全地跨 线程和异步任务边界。不变性使它 更容易推理线程和异步任务

最后，CPython 已经包含了 C 代码的主要部分 实现是必需的。已经 C 代码 存在来实现该模块（参见 PEP 567 更多细节。通过公共集合类型公开此 C 代码 大大增加代码的用户数量。这导致 通过发现错误和提高性能来提高代码质量 如果没有收藏品，这将是非常具有挑战性的 因为大多数程序都间接使用该模块。frozenmapcontextvarsfrozenmapcontextvars

规范

一个新的公共不可变类型被添加到模块中。frozenmapcollections

建设

frozenmap实现类似构造的 API：dict

• frozenmap()创建一个新的空不可变映射;

• frozenmap(**kwargs)从 创建一个映射，例如**kwargsfrozenmap(x=10, y=0, z=-1)

• frozenmap(collection)从传递的对象创建映射。传递的对象可以是：collectioncollection

• n Cdict

• 另一个frozenmap

• 具有预期返回的方法的对象 一系列键/值元组，或者items()

• 键/值元组的可迭代。

数据访问

frozenmap实现协议。 因此，getter、成员资格检查和迭代的工作方式相同 他们会以这样的方式：collection.abc.Mappingdict

m = frozenmap(foo='bar')assert m['foo'] == 'bar'assert m.get('foo') == 'bar'assert 'foo' in massert 'baz' not in massert m.get('baz', 'missing') == 'missing'assert m == massert m != frozenmap()  # m is not equal to an empty frozenmapassert len(m) == 1# etc.

突变

frozenmap实例是不可变的。也就是说，这是可能的 以有效地生成不可变实例的突变副本。

突变操作的复杂度为 O（log N），并且由于 结构共享的使用（有关详细信息，请阅读 [6]。frozenmap

frozenmap.including（键，值）

该方法使用新的键/值对创建一个新副本：frozenmap

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

frozenmap.excluding（键）

该方法生成一个副本，该副本没有 包括已删除的密钥：frozenmap

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

frozenmap.union（mapping=None， **kw）

该方法生成 的副本，并添加或修改 创建的副本的多个键/值。签名 该方法与构造函数的签名匹配：frozenmapfrozenmap

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

调用添加/替换 N 键的方法效率更高 比调用该方法 N 次。union()including()

frozenmap.mutating（）

该方法允许使用 应用了多项修改。这种方法特别有用 当有问题的 frozenmap 包含数千个键/值对时 并且需要在性能关键型中更新其中的许多内容 部分。frozenmap

该方法返回一个可变的 dict-like 对象的副本：的实例。frozenmap.mutating()frozenmapcollections.FrozenMapCopy

对象：FrozenMapCopy

• 是实例数据的写入时复制视图 它们是从以下位置创建的;frozenmap

• 是可变的，尽管它们上的任何突变都不会影响创建它们的实例;frozenmap

• 可以传递给构造函数;创建一个 来自对象的 frozenmap 是 O（1） 操作;frozenmapFrozenMapCopy

• get/set 操作具有 O（log N） 复杂度;创建 它们是 O（1） 运算;

• 有一种方法可以防止任何 数据的进一步访问/变更;FrozenMapCopy.close()

• 可以用作上下文管理器。

下面的示例说明了如何与 上下文管理器：mutating()

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.

迭 代

由于实现了标准协议，因此支持所有预期的迭代方法：frozenmapcollections.abc.Mapping

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

与 不同，迭代 in 不会保留 广告订单。frozenmapdict

散列法

frozenmap实例可以像对象一样可散列：tuple

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

打字

可以对 frozenmaps 使用标准类型符号：

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

实现

建议的不可变类型使用哈希数组映射 Trie （HAMT） 数据结构。函数式编程语言， 像 Clojure 一样，使用 HAMT 来有效地实现不可变的哈希表， 向量和集合。frozenmap

哈姆特

HAMT的密钥设计合约是在给定密钥的哈希值时保证可预测值。对于一对键和值， 键的哈希可用于确定值在哈希映射树中的位置。

使用 HAMT 实现的不可变映射具有 O（log N） 性能 for 和 操作。这种效率是可能的 因为突变操作只影响树的一个分支， 使重用未突变的分支成为可能，因此， 避免复制未修改的数据。set()get()

在中阅读有关 HAMT 的更多信息。CPython 实现  有一个 对算法的描述也相当详细。

性能

图 1.基准测试代码可以在这里找到：。

上图表明：

• frozenmap使用接近 O（1） 性能的 HAMT 显示器实现 适用于所有基准字典大小。

• dict.copy()使用时效率降低 100-200 个项目。

图2.基准测试代码可以在这里找到。

图 2 比较了 HAMT 与基于 HAMT 的查找成本 不可变映射。HAMT 查找时间比 Python 字典慢 ~30% 平均查找。自遍历以来，存在此性能差异 浅树的效率低于平面连续数组中的查找。dict

此外，引用：“[使用HAMT]意味着在实践中 在持久性哈希数组中插入、删除和查找时 对于大多数 应用 它们实际上是恒定时间，因为它需要 大量的条目，使任何操作都花费更多 比十几步。

设计注意事项

为什么是“frozenmap”而不是“frozenMap”

小写的“frozenmap”与内置以及 .frozensetcollections.defaultdict

为什么是“frozenmap”而不是“frozendict”

“Dict”在 Python 中具有非常具体的含义：

• dict 是 with 的具体实现 O（1） get 和 set 运算（具有 O（log N） 复杂度）;abc.MutableMappingfrozenmap

• Python 字典保留插入顺序。

提案没有提到这些 性能。相反，具有 set/get 的 O（log N） 成本 操作，并且它只实现协议。frozenmapfrozenmapabc.Mapping

实现

所建议类型的完整实现是 可在 中查阅。该软件包包括 C 和纯 Python 类型的实现。frozenmap

另请参阅 HAMT 集合实现作为 CPython 项目树在这里：。

确认

我感谢卡罗尔·威林、卢卡斯·兰加、拉里·黑斯廷斯和 Guido van Rossum 的反馈、想法、编辑和讨论 围绕这个 PEP。

版权

本文档被置于公共领域或位于 CC0-1.0-通用许可证，以更宽松的许可证为准。

The End