list（…）.insert（…）的性能

Question

我考虑了以下有关计算机体系结构的问题。假设我在Python中做

from bisect import bisect
index = bisect(x, a)      # O(log n)  (also, shouldn't it be a standard list function?)
x.insert(index, a)        # O(1) + memcpy()

这需要log n，再加上，如果我理解正确，内存复制操作x[index:]。现在我最近读到，瓶颈通常是处理器与内存之间的通信，因此可以通过RAM快速完成内存复制。它是如何工作的？

Answer 1

Python是一种语言。存在多种实现，并且它们可能具有列表的不同实现。因此，如果不查看实际实现的代码，就无法确定列表的实现方式以及它们在某些情况下的行为。

我敢打赌，列表中对象的引用存储在连续内存中（肯定不是链接列表…）。如果确实如此，则使用插入x.insert将导致移动所插入元素后面的所有元素。这可以通过硬件有效地完成，但是复杂度仍然是O（n）。

对于小列表，该bisect操作可能需要花费更多时间x.insert，即使前者是O（log n）而后者是O（n）。但是，对于长列表，我可能会猜测x.insert是瓶颈。在这种情况下，您必须考虑使用其他数据结构。