python - Python中集合的pop（）的时间复杂度是多少？

Question

我知道 pop 列表的最后一个元素需要 O(1)。读完这篇文章后

在 Python 中从列表中弹出元素的时间复杂度是多少？

我注意到，如果我们从列表中弹出任意数字需要 O(n)，因为所有指针都需要向上移动一个位置。

但是对于集合，没有顺序也没有索引。所以我不确定集合中是否还有指针？

如果不是，set 的 pop() 会是 O(1) 吗？

谢谢。

标签： python

Answer 1

在现代 CPython 实现中，pop需要分摊的常量时间（我将进一步解释）。在 Python 2 上，它通常是相同的，但在某些情况下性能会严重下降。

Pythonset基于哈希表，pop必须在表中找到一个被占用的条目才能删除并返回。如果它每次都从表的开头进行搜索，这将花费与空前导条目的数量成正比的时间，并且每次pop.

为了避免这种情况，标准的 CPython 实现尝试记住最后一个popped 条目的位置，以加快pops 的序列。CPython 3.5+ 在 set 内存布局中有一个专门的finger成员来存储这个位置，但是早期版本滥用第一个哈希表条目的哈希字段来存储这个索引。

在任何 Python 版本中，使用一系列pop操作从集合中删除所有元素所花费的时间与底层哈希表的大小成正比，这通常在原始元素数量的一个小的常数因子内（除非你已经删除了一堆元素）。如果插入的元素落在哈希表索引 0 中，则混合插入pop会严重干扰 Python 2，从而破坏搜索手指。这在 Python 3 上不是什么大问题。