PEP 603 – 将冻结的地图类型添加到集合

猫勺猫勺 03-12 127 阅读 0 评论

抽象

持久性数据结构定义为 修改数据时保留以前版本的数据。 这种数据结构实际上是不可变的,因为对 它们不会就地更新结构,而是始终屈服 新的更新结构(有关详细信息,请参见 [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.png PEP 603 – 将冻结的地图类型添加到集合  Python 通用 第1张

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

上图表明:

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

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

1.png PEP 603 – 将冻结的地图类型添加到集合  Python 通用 第2张

图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 微信扫一扫

文章声明:以上内容(如有图片或视频在内)除非注明,否则均为腾龙猫勺儿原创文章,转载或复制请以超链接形式并注明出处。

本文作者:猫勺本文链接:https://www.jo6.cn/post/51.html

上一篇 下一篇

相关阅读

发表评论

访客 访客
快捷回复: 表情:
评论列表 (暂无评论,127人围观)

还没有评论,来说两句吧...

取消
微信二维码
微信二维码
支付宝二维码