代码如下, 其中初始化时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)
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 前插入节点,建议楼主自己在纸上画一下。 |
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; |
3
Nisenasdf OP @Contextualist 今天补了下双向链表和哨兵的相关知识,大体上能理解为什么能这样做了。然而还是有几点不清楚。
1. 为什么要采用这种结构来保存有序性,这样做的用意是什么,为什么不采用简单的 list 来做呢? 2. 这种用 list 实现双向链表的做法妥当吗?实际上,在每一个 list 的三个元素中,前两个(prev, next)保存的什么,指针? 这样用 list 来实现双向链表会数据冗余吗? 谢谢啦! 我现在还不是能理解透彻,望指教! |
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/參照 |