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

有什么理由不使用OrderedDict?

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

有什么理由不使用OrderedDict?

OrderedDict
是的子类
dict
,并且需要更多内存来跟踪键的添加顺序。这不是小事。该实现
dict
在幕后增加了第二个,所有键的双向链接列表(这是记住顺序的部分),以及一堆weakref代理。它并没有慢
很多 ,但至少比使用plain的内存多了一倍
dict

但是,如果合适,请使用它!这就是为什么它在那里:-)

这个怎么运作

基本dict只是将键映射到值的普通dict-根本不是“有序的”。

<key, value>
添加一对后,
key
会附加到列表中。列表是记住订单的部分。

但是,如果这是Python列表,则 删除 密钥将花费

O(n)
两倍的时间:
O(n)
在列表中找到密钥的
O(n)
时间,以及从列表中删除密钥的时间。

因此,它是一个双向链接列表。这使得删除键的

O(1)
时间为常数()。但是我们仍然需要找到属于该键的双向链接列表节点。为了节省操作
O(1)
时间,第二个-
隐藏的dict将键映射到双向链接列表中的节点。

因此,添加新

<key,value>
对需要将对添加到基本字典,创建一个新的双向链接列表节点来保存密钥,将该新节点附加到双向链接列表中,并将密钥映射到隐藏字典中的该新节点。工作量是原来的两倍多,但
O(1)
总体上还是(预期的情况)。

同样,删除存在的密钥也要花两倍的

O(1)
时间,但总的来说是预期的时间:使用隐藏的字典来查找密钥的双向链接列表节点,从列表中删除该节点,然后从两个字典中删除密钥。

等等,这非常有效。



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

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

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