python - 与列表相比，哪些性能具有 cPython 集？

Question

我刚刚为 cPython 列表找到了这些性能说明：

python列表所需的时间......

• ...获取或设置单个项目：O(1)
• ... 将一个项目添加到列表中：最差 O(n^2)，但通常为 O(1)
• ...插入一个项目：O（n），其中n是插入后的元素数
• ...删除一个项目：O(n)

现在我想知道 cPython 集的相同性能特征。另外，我想对列表/集合的迭代有多快。我对大型列表/集合特别感兴趣。

Answer 1

AFAIK，Python“规范”没有为列表、字典或集合的实现强加特定的数据结构，因此不能“正式”回答。如果您只关心 CPython（参考实现），那么我们可以引入一些非官方的复杂性。您可能希望重新制定您的问题以针对特定的 Python 实现。

无论如何，你提到的复杂性不可能是正确的。假设一个动态调整大小的数组实现，附加一个项目是摊销的O(1)：通常你只是简单地复制新值，在最坏的情况下，你需要重新分配，复制所有n项目，加上新的。接下来，插入具有完全相同的最坏情况，因此它具有相同的复杂性上限，但在最好的情况下，它只移动k项目，其中k是超过您插入位置的项目数。