有效地按 Python 3.6+ 中的位置访问字典项 [英] Accessing dictionary items by position in Python 3.6+ efficiently

问题描述

我知道字典是插入在 Python 3.6+ 中排序，作为 3.6 中的实现细节和 3.7+ 中的正式实现细节.

I understand dictionaries are insertion ordered in Python 3.6+, as an implementation detail in 3.6 and official in 3.7+.

鉴于它们是有序的，似乎没有方法可以按插入顺序检索字典的 i^th 项.唯一可用的解决方案似乎具有 O(n) 复杂度，要么:

Given they are ordered, it seems strange that no methods exist to retrieve the i^th item of a dictionary by insertion order. The only solutions available appear to have O(n) complexity, either:

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

1. Convert to a list via an O(n) process and then use list.__getitem__.
2. enumerate dictionary items in a loop and return the value when the desired index is reached. Again, with O(n) time complexity.

由于从 list 获取一个项目的复杂度为 O(1)，有没有办法用字典实现相同的复杂度?使用常规 dict 或 collections.OrderedDict 都可以.

Since getting an item from a list has O(1) complexity, is there a way to achieve the same complexity with dictionaries? Either with regular dict or collections.OrderedDict would work.

如果不可能，是否存在阻止这种方法的结构性原因，或者这只是尚未考虑/实施的功能?

If it's not possible, is there a structural reason preventing such a method, or is this just a feature which has not yet been considered / implemented?

推荐答案

对于 OrderedDict 它本质上是 O(n) 因为排序记录在 链表.

For an OrderedDict it's inherently O(n) because the ordering is recorded in a linked list.

对于内置字典，有一个向量(一个连续的数组)而不是一个链表，但最后几乎是一样的:向量包含一些傻瓜"，特殊的内部值意味着没有密钥已存储在这里"或密钥曾经存储在这里但不再存储".这使得，例如，删除一个键非常便宜(只需用一个虚拟值覆盖键).

For the builtin dict, there's a vector (a contiguous array) rather than a linked list, but pretty much the same thing in the end: the vector contains a few kind of "dummies", special internal values that mean "no key has been stored here yet" or "a key used to be stored here but no longer". That makes, e.g., deleting a key extremely cheap (just overwrite the key with a dummy value).

但是如果不在其上添加辅助数据结构，就无法跳过虚拟对象而不一次一个地跳过它们.因为 Python 使用一种开放寻址形式来解决冲突，并且将负载因子保持在 2/3 以下，所以至少有三分之一的向量条目是虚拟的.the_vector[i] 可以在 O(1) 时间内访问，但实际上与第 i 个非虚拟条目没有可预测的关系.

But without adding auxiliary data structures on top of that, there's no way to skip over the dummies without marching over them one at a time. Because Python uses a form of open addressing for collision resolution, and keeps the load factor under 2/3, at least a third of the vector's entries are dummies. the_vector[i] can be accessed in O(1) time, but really has no predictable relation to the i'th non-dummy entry.

这篇关于有效地按 Python 3.6+ 中的位置访问字典项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！