我想到了有关计算机的体系结构以下问题。 假设我在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（）内。 特别是，通过对开调用的比较功能可以根据对象的列表类型的东西贵。
如果你需要持有大量的潜在可变排序的序列则线性阵列下面的蟒蛇列表类型是不是一个好的选择。 根据您的要求堆，树或跳跃列表可能是适当的。
