我想到了以下有关计算机体系结构的问题。假设我用 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 非常快地完成。它是这样工作的吗？
Python是一种语言。存在多种实现，它们可能对列表有不同的实现。因此，如果不查看实际实现的代码，您无法确定列表是如何实现的以及它们在某些情况下的行为方式。
我敢打赌，对列表中对象的引用存储在连续的内存中（当然不是链表......）。如果确实如此，那么插入使用x.insert将导致被插入元素后面的所有元素都被移动。这可以通过硬件有效地完成，但复杂度仍然是O(n)。
对于小列表，bisect操作可能需要比 更多的时间x.insert，即使前者是O(log n)而后者是O(n)。然而，对于长列表，我会冒险猜测这x.insert是瓶颈。在这种情况下，您必须考虑使用不同的数据结构。
如果您需要具有更好插入性能的列表，请使用blist 模块。
CPython 列表是连续的数组。O(log n) 对分和 O(n) 插入中的哪一个支配您的性能配置文件取决于列表的大小以及 O() 中的常数因子。特别是，由 bisect 调用的比较函数可能会很昂贵，具体取决于列表中对象的类型。
如果您需要保存可能较大的可变排序序列，那么 Python 列表类型底层的线性数组不是一个好的选择。根据您的要求，堆、树或跳过列表可能是合适的。