在python 3.6+中按位置高效访问字典项

对于一个 OrderedDict 它固有地 O(n) 因为排序记录在 linked list .

对于内置dict,有一个向量(一个连续数组)而不是一个链表,但最后基本上是一样的:向量包含一些“假人”,特殊的内部值意味着“还没有在这里存储密钥”或“以前在这里存储但现在不再存储的密钥”。这使得,例如,删除一个键非常便宜(只需用一个虚拟值覆盖该键)。

但是,如果不在上面添加辅助数据结构,就没有办法跳过这些假人,而不逐个跳过它们。因为python使用开放寻址的形式来解决冲突,并且将负载系数保持在2/3以下,至少是向量项的三分之一。 是 傻瓜。 the_vector[i] 可以在中访问 O(1) 时间,但与第i个非虚拟条目没有可预测的关系。

按照 @TimPeters' answer ,在O(1)时间中,有结构原因无法按位置访问字典项。

如果您正在寻找O(1)按键查找,则值得考虑其他选项。 或 位置。有第三方库,如numpy/pandas,提供此类功能、高效 尤其地 对于不需要指针的数值数组。

使用pandas,您可以构建一个“类似字典”的系列,其唯一标签提供O(1)按“标签”或位置查找。你牺牲的是删除标签时的性能,这会导致( n )成本,很像 list .

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. What are the advantages of NumPy over regular Python lists? .
2. What is the performance impact of non-unique indexes in pandas?
3. Pandas DataFrame search is linear time or constant time?