有效地按Python 3.6+中的位置访问字典项

Question

有效地按Python 3.6+中的位置访问字典项

jpp*_*jpp 26 python dictionary python-3.x python-internals

我理解字典是在Python 3.6+中排序的插入,作为3.6中的实现细节和3.7+中的官方.

鉴于它们是有序的,似乎很奇怪,没有方法可以通过插入顺序检索字典的^第i项.该唯一的解决方案可出现有O(ñ)的复杂性,无论是:

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

由于从list具有O(1)复杂度的项目中获取项目,是否有办法通过字典实现相同的复杂性？无论是定期dict还是collections.OrderedDict工作.

如果不可能,是否存在阻止这种方法的结构性原因,或者这只是一个尚未考虑/实施的特征？

Answer 1

Tim*_*ers 36

因为OrderedDict它本身就是O(n)因为订单记录在链表中.

对于内置字典,有一个向量(一个连续的数组)而不是一个链表,但最后几乎是相同的东西:向量包含一些"假人",特殊的内部值表示"没有键已经存储在这里"或"一把钥匙曾经存放在这里,但不再是".这使得例如非常便宜地删除密钥(仅用虚拟值覆盖密钥).

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

@ juanpa.arrivillaga,它更复杂 - 什么不是？;-)在封面下有"分裂"和"非分裂"的词组等.对于常规的旧词典("非分裂"),删除键_also_将相应的值槽设置为NULL,所以同样的事情; 您必须一次跳过一个NULL值.请参阅dictobject.c的`dictiter_iternextkey()`中的循环.迭代"键"_actually_迭代值,这些值按插入顺序排列,但可以在任意位置包含NULL.一旦找到非NULL值,它就会包含一个指向该键的指针. (6认同)
你链接的POC完全是另一回事:更节省空间的dict实现.它根本不保留插入顺序.实际上,它"与最后一个条目交换以避免留下'洞'"可以将最后一个条目移动到任何位置.当前的实现既节省空间又保持顺序,但是在删除时不留任何漏洞,而保留顺序则需要在删除一个条目之后物理移动每个条目.相反,它只是用NULL覆盖已删除的值(留下"一个洞"). (2认同)

归档时间：	7 年，5 月前
查看次数：	2567 次
最近记录：	7 年前