列表的性能(...).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是瓶颈.在这种情况下,您必须考虑使用不同的数据结构.

Answer 2

如果需要具有更好插入性能的列表,请使用blist模块.

Answer 3

CPython列表是连续的数组.O(log n)bisect和O(n)插入中的哪一个主导您的性能配置文件取决于列表的大小以及O()内的常量因子.特别是,bisect调用的比较函数可能是昂贵的,取决于列表中对象的类型.

如果你需要保存可能很大的可变排序序列,那么基于Pythons列表类型的线性数组就不是一个好选择.根据您的要求,堆​​,树或跳过列表可能是合适的.