执行列表（…）。插入（…）

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

如果需要具有更好插入性能的列表，请使用blist module。

Answer 2

Python是一种语言。Multiple implementations exist，而且它们可能对列表有不同的实现。因此，如果不查看实际实现的代码，就无法确定列表是如何实现的，以及它们在某些情况下的行为。

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

对于小列表，bisect操作可能需要比x.insert更多的时间，即使前者是O（log n），而后者是O（n）。然而，对于长列表，我会冒险猜测x.insert是瓶颈。在这种情况下，必须考虑使用不同的数据结构。

Answer 3

CPython列表是连续数组。O（log n）等分和O（n）插入中的哪一个控制性能配置文件取决于列表的大小以及O（）中的常量因子。特别是，根据列表中对象的类型，由bisect调用的比较函数可能非常昂贵。

如果需要保存潜在的大型可变排序序列，那么Pythons列表类型下面的线性数组不是一个好的选择。根据您的需求，堆、树或跳过列表可能是合适的。