Python 3.6+高效访问字典项的位置

Question

我知道字典在Python 3.6+中是按插入顺序排序的，这是在3.6中作为实现细节，在3.7+中正式成为规范。

既然它们是有序的，那么似乎没有任何方法可以通过插入顺序检索字典的第i个项目。可用的唯一解决方案似乎具有O(n)的复杂度，要么：

1.通过O(n)的过程将其转换为列表，然后使用list.__getitem__。 2.在循环中枚举字典项，并在达到所需索引时返回该值。同样，时间复杂度为O(n)。

由于从列表获取项目具有O(1)的复杂度，是否有办法使用字典实现相同的复杂度？使用常规dict或collections.OrderedDict都可以。

如果不可能，是否有结构上的原因阻止了这种方法，还是这只是一个尚未考虑/实施的功能？

- jpp

---

它被实现为链表。否则，删除元素将是不可能的。 - o11c

我可以想到一个不太常见的原因。它使得JSON行更加稳定，而无需封装列表和单独的字典。除此之外，我并没有真正理解这种热潮。 - roganjosh

@o11c，好的，显然我对此有些理解上的差距。但我可以看出（也许）你的意思，也许你需要具有O（n）位置访问来保持列表的O（1）删除与O（n）不同。 - jpp

根据 https://dev59.com/6VkS5IYBdhLWcg3wXFg9#39980744 ，只有一个按插入顺序排列的条目数组 dk_entries。没有链接列表。删除的条目将被替换为虚拟条目，并且在添加新条目时，可能会调整数组的大小（删除虚拟条目）。 - Michael Butscher

@o11c 它 不是 作为链表实现的。 - juanpa.arrivillaga

我认为他们只是不想将基本上是映射的东西添加类似于序列的行为。换句话说：你不应该像使用列表一样使用字典，但它确实维护顺序。 - juanpa.arrivillaga

Answer 1

对于有序字典OrderedDict，其本质上为O(n)的，因为顺序记录在链接列表中。

对于内置字典dict，使用了一个向量（连续数组）而不是链接列表，但最终结果基本相同：向量包含一些“哑值”（特殊的内部值），表示“这里尚未存储任何键”或“曾经在此处存储过键，但现在已经删除”。这使得删除键非常便宜（只需将键覆盖为哑值）。

但是，如果没有添加辅助数据结构，就无法跳过这些哑值，必须逐个遍历它们。因为Python使用一种开放地址形式进行碰撞解决，并将负载系数保持在2/3以下，因此向量的至少三分之一的条目为哑值。可以在O(1)时间内访问the_vector[i]，但实际上与第i个非哑值的条目没有可预测的关系。

- Tim Peters

---

根据我对>3.6实现的理解，有两个向量，其中稀疏索引数组是开放寻址发生的地方，但实际条目向量只是按顺序排列的条目数组，没有虚拟条目，对吗？ - juanpa.arrivillaga

@juanpa.arrivillaga，这更加复杂了 - 这有什么不一样呢？;-) 在底层有“分裂”和“非分裂”字典等等。 对于一个普通的旧字典（“非分裂”），删除键也将相应的值槽设置为NULL，因此同样的事情； 您必须逐个跳过NULL值。 请参见dictobject.c中的dictiter_iternextkey()循环。 迭代“键”实际上迭代值，这些值按照插入顺序进行排序，但可以在任意位置包含NULL。 一旦找到非NULL值，它就包含指向键的指针。 - Tim Peters

啊，我明白了。只是为了确认我理解你的意思，当你删除一个键时，实际上它被设置为 null 在条目向量中。这与此处的 POC 实现不同（http://code.activestate.com/recipes/578375/），在该实现中，值仅从向量弹出（在 __delitem__ 中的列表 self.entries 中）？我想你的动机不是为了避免删除而产生 O(N) 惩罚？ - juanpa.arrivillaga

你链接的 POC 是完全针对其他东西的：一种更节省空间的字典实现。它根本不保留插入顺序。事实上，它的“与最后一个条目交换以避免留下‘洞’”可以将最后一个条目移动到任何位置。当前的实现既节省空间又保持顺序，但是在删除时不留下空洞并保持顺序需要物理移动删除后面的每个条目。相反，它只是用 NULL 覆盖已删除的值（留下“洞”）。 - Tim Peters

Answer 2

根据@TimPeters' answer，有结构性的原因使你不能在O（1）时间内按位置访问字典项。

如果您正在寻找按键或位置进行O（1）查找的替代方案，则值得考虑其他选择。有第三方库，如NumPy / Pandas，提供此类功能，特别是对于不需要指针的数字数组，效率高。

使用Pandas，您可以构建具有唯一标签的“类似字典”的系列，可通过“标签”或位置进行O（1）查找。您牺牲的是删除标签时的性能，这会产生O（n）成本，就像列表一样。

import pandas as pd

s = pd.Series(list(range(n)))

# O(n) item deletion
del s[i]
s.drop(i)
s.pop(i)

# O(1) lookup by label
s.loc[i]
s.at[i]
s.get(i)
s[i]

# O(1) lookup by position
s.iloc[i]
s.iat[i]

pd.Series绝不是dict的替代品。例如，重复的键不会被防止，并且如果系列主要用作映射，则会导致问题。然而，在数据存储在连续的内存块中时，就像上面的示例一样，您可能会看到显着的性能提升。

另请参见：

1. NumPy相对于常规Python列表的优势是什么？
2. pandas中非唯一索引的性能影响是什么？
3. Pandas DataFrame搜索是线性时间还是常数时间？

- jpp

---

不错。我在想，哪种最简单的数据结构能够满足 OP 的要求。 - Eric Duminil

@EricDuminil，确实如此。当考虑到替代dict时，人们并不总是会想到“Pandas系列！”，但如果满足某些条件，那么它肯定是可行的。语法通常也是相似的，例如s[i]，s.get(i)，del s[i]，s.keys()，s.items()。 - jpp