Python如何保持键顺序？
因为Python3.6字典保持插入/键顺序。
我和一位同事就如何实现这个问题进行了争论。他说，这一定是通过使用列表或其他集合来保持密钥顺序来实现的。我怀疑可能还有更微妙的事情在起作用。
我做了以下比较：
# Python 3.4.3
d = {1: 2, 2:3, 3:4}
od = OrderedDict(d)
print(sys.getsizeof(d)) # 288
print(sys.getsizeof(od)) # 1304# Python 3.6.3
d = {1: 2, 2:3, 3:4}
print(sys.getsizeof(d)) # 240OderedDict的大小是巨大的，我绝对可以在这个任务的后台使用一个列表来看到它。然而，普通词典的大小并没有发生任何变化，所以我对普通词典也使用列表来保持插入顺序这一事实表示怀疑。
那么，更新的python版本中的规则条到底是如何保持键顺序的？
回答 3
Stack Overflow用户
发布于 2021-08-09 13:40:08
我在来源上找到了一条评论
保持插入顺序 这对组合桌来说很简单。由于dk_entries主要是附加的，所以只需迭代dk_entries就可以得到插入顺序。
layout:
+---------------+
| dk_refcnt |
| dk_log2_size |
| dk_kind |
| dk_usable |
| dk_nentries |
+---------------+
| dk_indices |
| |
+---------------+
| dk_entries |
| |
+---------------+dk_entries是PyDictKeyEntry的数组。它的大小是USABLE_FRACTION(dk_size)。DK_ENTRIES(dk)可以用来获取指向条目的指针。
因此，它似乎维护了一个数组。为了获得更多的信息，还需要做更多的挖掘工作，但这是一个起点。
Stack Overflow用户
发布于 2021-08-09 13:34:05
严格地说，这是一个实现细节。Python只指定dict确实记住键顺序，而不是它是如何执行的。
Python3.6没有保证键顺序；这是dict类型在CPython中的实验性重新实现。当(如预期的)该实验被认为是成功的时候，Python本身就需要在Python3.7中保存密钥顺序。
在CPython中，修改dict类型本身的C实现。我不确定具体的方法(您可以查看细节这里)，但是在内存中保留一个额外的列表可能比在OrderedDict级别执行等效的操作更有效，这正是OrderedDict所做的。它甚至不是保存键的Python list：它是一个纯Python链接列表，因此内存需求如此之大并不令人惊讶。
Stack Overflow用户
发布于 2021-08-09 13:32:54
来自python3.8源代码(参见self.__map)
class _Link(object):
__slots__ = 'prev', 'next', 'key', '__weakref__'
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).
# The sentinel is in self.__hardroot with a weakref proxy in self.__root.
# The prev links are weakref proxies (to prevent circular references).
# Individual links are kept alive by the hard reference in self.__map.
# Those hard references disappear when a key is deleted from an OrderedDict.
def __init__(self, other=(), /, **kwds):
'''Initialize an ordered dictionary. The signature is the same as
regular dictionaries. Keyword argument order is preserved.
'''
try:
self.__root
except AttributeError:
self.__hardroot = _Link()
self.__root = root = _proxy(self.__hardroot)
root.prev = root.next = root
self.__map = {}
self.__update(other, **kwds)https://stackoverflow.com/questions/68712851
复制相似问题
腾讯云开发者
