Python 3.7+中查找字典中第一个元素的时间复杂度

Question

自 Python 3.7 起，字典根据插入顺序保留顺序。

似乎可以使用 next(iter(my_dict)) 来获取字典中的第一项？

我的问题是这个操作的时间复杂度是多少？

我能把 next(iter(my_dict)) 视为常数时间(O(1)) 操作吗？或者有什么更好的方法在常数时间内检索字典中的第一项？

我之所以问这个问题是因为我希望在编码面试中使用它，其中对解决方案的时间复杂度有重要强调，而不是它以毫秒为单位运行得有多快。

- Somya Agrawal

---

从Python 3.7开始，字典顺序不再只是实现细节。插入顺序保证是字典顺序，并成为了语言特性。参考：https://docs.python.org/3.7/library/stdtypes.html#mapping-types-dict我认为在面试中使用有序字典是一种有效的数据结构，不是吗？ - Somya Agrawal

看，这与我的问题并不相关。在算法编码面试中，通常会提出几种解决方案（并讨论权衡），因此我想使用Python 3.7+的有序字典作为我的解决方案之一。因此，我想知道如何在常数时间复杂度内获取第一个元素。这不是我将向面试官展示的唯一解决方案，因此“那是否是我的面试官正在寻找的答案”这个问题是无关紧要的。 - Somya Agrawal

这个回答解决了你的问题吗？从Python有序字典中删除键的复杂度 - pyeR_biz

Answer 1

这可能是最好的方法（实际上您现在正在获取第一个键，next(iter(d.values()))会得到您的值）。

此操作（对于至少组合表中的keys、values或items的任何迭代）迭代通过一个包含字典条目的数组：

PyDictKeyEntry *entry_ptr = &DK_ENTRIES(k)[i];
while (i < n && entry_ptr->me_value == NULL) {
    entry_ptr++;
    i++;
}

entry_ptr->me_value保存了每个对应键的值。

如果您的字典是新创建的，在第一次迭代期间，此函数将找到第一个插入的项（字典条目数组是仅追加的，因此保留顺序）。

如果您的字典已被修改（您已删除许多项），则在最坏情况下可能会导致O(N)来查找第一个（剩余项中的第一个）插入的项（其中N是原始项的总数）。这是由于字典在删除项目时不会调整大小，因此许多条目的entry_ptr->me_value为NULL。

请注意，这是特定于CPython的。我不知道其他Python实现如何实现此功能。

- Dimitris Fasarakis Hilliard