list(...).insert(...) 的性能如何
我在想一个关于计算机架构的问题。假设我在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很快完成。这是怎么回事呢？
3 个回答
7
CPython中的列表是连续的数组。你使用的O(log n)的二分查找和O(n)的插入操作哪个更影响你的性能，主要取决于你的列表大小，以及O()里面的常数因素。特别是，二分查找使用的比较函数可能会很耗时，这取决于列表中对象的类型。
如果你需要保存可能很大的可变有序序列，那么Python的列表类型（底层是线性数组）就不是一个好的选择。根据你的需求，堆、树或者跳表可能更合适。
12
如果你需要一个插入数据时性能更好的列表，可以使用blist模块。
17
Python是一种编程语言。有很多不同的实现方式，而这些实现可能在列表的处理上有所不同。所以，如果不查看具体的代码，你就无法确切知道列表是怎么实现的，以及在某些情况下它们会表现得怎样。
我猜列表中的对象引用是存储在连续的内存空间里的（肯定不是像链表那样分散存储）。如果真是这样的话，当你使用x.insert插入一个元素时，插入位置后面的所有元素都需要移动。虽然硬件可能会高效地完成这个操作，但它的复杂度仍然是O(n)，也就是说，随着元素数量的增加，所需的时间会线性增长。
对于小列表来说，bisect操作可能会比x.insert花费更多的时间，尽管前者的复杂度是O(log n)，而后者是O(n)。不过，对于长列表，我猜x.insert会成为性能瓶颈。在这种情况下，你可能需要考虑使用其他的数据结构。