V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
Nisenasdf
V2EX  ›  Python

python collections.Ordereddict 源码中, 用来记录有序的结构,怎么理解?不是能看懂为什么这样存储。

  •  1
     
  •   Nisenasdf · 2016-11-21 21:13:38 +08:00 · 5107 次点击
    这是一个创建于 2920 天前的主题,其中的信息可能已经有所发展或是发生改变。

    代码如下, 其中初始化时root[:] = [root, root, None] 和设置值时last[1] = root[0] = self.__map[key] = [last, root, key] 这边怎么理解呢?谢谢啦

    class OrderedDict(dict):
        'Dictionary that remembers insertion order'
        # An inherited dict maps keys to values.
        # The inherited dict provides __getitem__, __len__, __contains__, and get.
        # The remaining methods are order-aware.
        # Big-O running times for all methods are the same as regular dictionaries.
    
        # The internal self.__map dict maps keys to links in a doubly linked list.
        # The circular doubly linked list starts and ends with a sentinel element.
        # The sentinel element never gets deleted (this simplifies the algorithm).
        # Each link is stored as a list of length three:  [PREV, NEXT, KEY].
    
        def __init__(*args, **kwds):
            '''Initialize an ordered dictionary.  The signature is the same as
            regular dictionaries, but keyword arguments are not recommended because
            their insertion order is arbitrary.
    
            '''
            if not args:
                raise TypeError("descriptor '__init__' of 'OrderedDict' object "
                                "needs an argument")
            self = args[0]
            args = args[1:]
            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)
    
        def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
            'od.__setitem__(i, y) <==> od[i]=y'
            # Setting a new item creates a new link 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]
            return dict_setitem(self, key, value)
    
        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 gets
            # removed by updating the links in the predecessor and successor nodes.
            dict_delitem(self, key)
            link_prev, link_next, _ = self.__map.pop(key)
            link_prev[1] = link_next                        # update link_prev[NEXT]
            link_next[0] = link_prev                        # update link_next[PREV]
    
        def __iter__(self):
            'od.__iter__() <==> iter(od)'
            # Traverse the linked list in order.
            root = self.__root
            curr = root[1]                                  # start at the first node
            while curr is not root:
                yield curr[2]                               # yield the curr[KEY]
                curr = curr[1]                              # move to next node
    
        def __reversed__(self):
            'od.__reversed__() <==> reversed(od)'
            # Traverse the linked list in reverse order.
            root = self.__root
            curr = root[0]                                  # start at the last node
            while curr is not root:
                yield curr[2]                               # yield the curr[KEY]
                curr = curr[0]                              # move to previous node
    
        def clear(self):
            'od.clear() -> None.  Remove all items from od.'
            root = self.__root
            root[:] = [root, root, None]
            self.__map.clear()
            dict.clear(self)
    
    4 条回复    2016-11-23 19:12:08 +08:00
    Contextualist
        1
    Contextualist  
       2016-11-21 22:32:22 +08:00 via iPad   ❤️ 1
    关键在于
    > # Each link is stored as a list of length three: [PREV, NEXT, KEY].
    就是说 od 的有序实际上是由一个双向链表实现的。由于 Python 里 list 是可变对象,一个节点 list 里的 PREV 和 NEXT 是对前驱和后继节点 list 的引用

    初始化那里, root 前驱和后继都指向自己,方便接下来实现环链。
    那句核心操作应该联系上文:
    last = root[0]
    last[1] = root[0] = [last, root, key] # self.__map[key] 可以稍后再看
    这句话实现了在 root 前插入节点,建议楼主自己在纸上画一下。
    zhy0216
        2
    zhy0216  
       2016-11-22 13:53:39 +08:00
    是个双向链表 [0] 和 [1] 理解成 .prev 和 .next 就可以了
    root[:] = [root, root, None] ==> root = [None, None, None]; root[0] = root; root[1] = None;
    Nisenasdf
        3
    Nisenasdf  
    OP
       2016-11-22 23:50:27 +08:00
    @Contextualist 今天补了下双向链表和哨兵的相关知识,大体上能理解为什么能这样做了。然而还是有几点不清楚。
    1. 为什么要采用这种结构来保存有序性,这样做的用意是什么,为什么不采用简单的 list 来做呢?
    2. 这种用 list 实现双向链表的做法妥当吗?实际上,在每一个 list 的三个元素中,前两个(prev, next)保存的什么,指针? 这样用 list 来实现双向链表会数据冗余吗?
    谢谢啦! 我现在还不是能理解透彻,望指教!
    Contextualist
        4
    Contextualist  
       2016-11-23 19:12:08 +08:00 via iPad
    @Nisenasdf
    我只会从静态语言的角度解释,所以下面说的不一定是对的。
    1. 这个涉及到数组 (Python 里的近似就是元素都是不可变对象的 list ,就是你所说的“简单的 list ”) 和链表这两种基本数据结构的本质用途:二者同样是序列,数组按 index 存值取值,对于**固定**的序列存取都是 O(1);双向链表按 pre 、 next 遍历,因为节点是可变对象,可以被引用 (对于 od 来说就是 self.__map[key] 的用途) ,对于**动态**的序列存取也是 O(1)。
    od 显然要维护一个动态序列,链表就是个很好的选择。你可能会想到 list 可以 del 某个元素,但这其实破坏了数组的规则 (Python 的 list 不是数组), index 都被改变了,不能根据原来的 index 来存取。那元素是可变对象的 list ([[key1], [key2], ...]) 呢?这样也可以用不受 index 影响的不变引用来 O(1) 存取。但其实 list 的 del 效率是很低的,是 O(n),因为要重新分配 index 。总之,对于动态序列,用链表就对了。

    2. 上面的问题纠结完了,这个问题就很好回答。双向链表的节点必须要 pre , next ,和值这三部分,没有任何冗余。其次,引用其实不是很占空间。再说了,牺牲了空间,换来了时间。

    题外话:关于指针和引用,请看: https://zh.m.wikipedia.org/wiki/參照
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1238 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 18:19 · PVG 02:19 · LAX 10:19 · JFK 13:19
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.