栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

Python

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Python

它们是插入顺序[1]。从Python 3.6开始,对于Python的CPython实现,词典会记住插入项目的顺序。这在Python 3.6中被视为实现细节;你需要使用

OrderedDict
,如果你想多数民众赞成插入排序保证不同的Python的其它实现(与其他有序行为[1] )。

从Python 3.7开始,它不再是实现细节,而是成为一种语言功能。从GvR的

py​​thon-dev
消息中:

做到这一点。裁定“裁定保留插入顺序”。谢谢!

这只是意味着你可以依靠它。如果其他Python实现希望成为Python 3.7的一致实现,则还必须提供插入顺序字典。

在保留元素顺序的同时,Python 3.6字典实现如何比旧的实现更好的性能[2]?

本质上,通过保留两个数组。

  • 第一个数组,按插入顺序

    dk_entries
    保存字典的条目(类型PyDictKeyEntry)。保留顺序是通过仅附加数组来实现的,在该数组中始终在末尾插入新项(插入顺序)。

  • 第二个

    dk_indices
    保留
    dk_entries
    数组的索引(即,指示中相应条目位置的值dk_entries)。该数组充当哈希表。对键进行哈希处理时,它会导致存储在其中的索引之一,dk_indices并通过indexing获取相应的条目
    dk_entries
    。由于只有索引被保留,此数组的类型取决于字典的整体大小(范围从类型int8_t(1字节)到int32_t/ int64_t(4/ 8字节)上32/ 64位构建)

在以前的实现中,必须分配类型PyDictKeyEntry和大小的稀疏数组dk_size。不幸的是,由于性能原因,该数组不允许

2/3 * dk_size
满载,这也导致了很多空白。(并且空白区域仍具有大小!)。PyDictKeyEntry

现在不是这种情况,因为仅存储了必需的条目(已插入的条目),并且保留了一个稀疏类型的数组intX_t(X取决于dict的大小)

2/3 * dk_size
。空格从类型更改
PyDictKeyEntry为intX_t

显然,创建一个类型

PyDictKeyEntry
稀疏的数组比存储ints 的稀疏数组需要更多的内存。

如果有兴趣,可以在

Python-Dev
上查看有关此功能的完整对话,这是一本好书。

在Raymond Hettinger提出的原始建议中,可以看到使用的数据结构的可视化效果,该可视化体现了该思想的要旨。

例如,字典:

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

当前存储为[keyhash,key,value]:

entries = [['--', '--', '--'],[-8522787127447073495, 'barry', 'green'],['--', '--', '--'],['--', '--', '--'],['--', '--', '--'],[-9092791511155847987, 'timmy', 'red'],['--', '--', '--'],[-6480567542315338377, 'guido', 'blue']]

相反,数据应按以下方式组织:

indices =  [None, 1, None, None, None, 0, None, 2]entries =  [[-9092791511155847987, 'timmy', 'red'], [-8522787127447073495, 'barry', 'green'], [-6480567542315338377, 'guido', 'blue']]

正如你现在可以从视觉上看到的那样,在原始建议中,很多空间实际上是空的,以减少冲突并加快查找速度。使用新方法,可以通过将稀疏移动到真正需要的索引中来减少所需的内存。



转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/369151.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号