前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Python 有序字典的实现

Python 有序字典的实现

作者头像
岂不美哉Frost
发布2019-11-29 21:36:35
1.3K0
发布2019-11-29 21:36:35
举报
文章被收录于专栏:Frost's BlogFrost's Blog

最近在看 requests 源码的时候看到作者使用了 urllib3 中自己实现的OrderedDict类,收获颇多。自己实现一个数据结构往往是最需要算法和优化的地方,各种语法糖黑科技,相当的 Pythonic,看这种代码实在是一种享受。如果要我自己实现的话,自己会想到用一个有序存储的对象(如列表)去 hack 内部的实现,但这样有几个缺点:

  1. 列表的插入、删除操作性能不如字典,复杂度是 O(N) 量级的。
  2. 自定义类需要继承于dict,没有利用继承的方法特性。

来看看大神是怎么实现的吧。

__init__方法

Python

代码语言:javascript
复制
class OrderedDict(dict):
    def __init__(self, *args, **kwds):
        if len(args) > 1:
            raise TypeError('expected at most 1 arguments, got %d' % len(args))
        try:
            self.__root
        except AttributeError:
            self.__root = root = []                     # sentinel node
            root[:] = [root, root, None]
            self.__map = {}
        self.__update(*args, **kwds)

在上一篇文章中说到一些关于列表的坑,说到不要用a=b=[]这样的语句来初始化,其实也不全然,我们来看 7-8 行做了什么。第 7 行使self.__rootroot同时指向一个空列表,相关于给self.__root起了一个短别名,关键是第 8 行:

Python

代码语言:javascript
复制
>>> root[:] = [root, root, None]
>>> root
[[...], [...], None]

什么鬼?没见过[...]这种的啊,我来看看

Python

代码语言:javascript
复制
>>> root[0]
[[...], [...], None]
>>> root[0] is root
True

What? 自己是自己的元素?简直是从前有座山山上有座庙啊,子子孙孙无穷尽啊。到底发生了什么事?Python 中万物皆指针,而root[:]=...的赋值是不改变指针指向的地址而是改变指向地址的内容。右边第一个和第二个元素是指向自己的指针,这样就构造了一个我中有我的列表。

再看命名,明白了,这是一个双向链表!列表的前两个元素分别指向上一个结点和下一个结点,第三个元素是结点的值。只用两行就初始化了一个链表,学到了。另外还初始化了一个字典,暂时不知道有什么用。

__setitem__方法

Python

代码语言:javascript
复制
def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
    'od.__setitem__(i, y) <==> od[i]=y'
    # Setting a new item creates a new link which goes at the end of the linked
    # list, and the inherited dictionary is updated with the new key/value pair.
    if key not in self:
        root = self.__root
        last = root[0]
        last[1] = root[0] = self.__map[key] = [last, root, key]
    dict_setitem(self, key, value)

关键的部分到了,这个魔法方法加了第三个参数来方便子类扩展。函数体部分,画一个图就明白了。

!

  1. root的上一个结点就是末结点,保存为last
  2. 创建一个新结点,它的上结点和下结点分别设为lastroot,结点的值为字典的键。
  3. last的下结点和root的上结点指向该结点。
  4. 将结点加入__map并加入字典。

这样创建就结点就变成了新的末结点了。从此也可看出,root是一个守护结点,本身并不存储值,但会简化算法。__map 是结点的哈希表,避免了从头开始寻找所需的结点。

__delitem__方法

Python

代码语言:javascript
复制
def __delitem__(self, key, dict_delitem=dict.__delitem__):
    'od.__delitem__(y) <==> del od[y]'
    # Deleting an existing item uses self.__map to find the link which is
    # then removed by updating the links in the predecessor and successor nodes.
    dict_delitem(self, key)
    link_prev, link_next, key = self.__map.pop(key)
    link_prev[1] = link_next
    link_next[0] = link_prev

删除结点时,从哈希表中弹出该结点,然后将它的上结点和下结点相连,并从字典中删除。

实现了这三个方法,剩下的就好办了,__iter__只需从头开始遍历链表并取出键值就可以了。

总结

实现有序字典的关键在于选取一个合适的数据结构来存储顺序信息,这里作者使用了双向链表,然后把结点哈希。这样进行插入、删除操作的时间复杂度为 O(1) ,与dict类型一致,代价就是 O(2n) 的空间复杂度。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2016-07-07T,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • __init__方法
  • __setitem__方法
  • __delitem__方法
  • 总结
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档