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 非常快地完成。 是这样的吗？
I thought about the following question about computer's architecture. Suppose I do in 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()
which takes log n, plus, if I correctly understand it, a memory copy operation for x[index:]. Now I read recently that the bottleneck is usually in the communication between processor and the memory so the memory copy could be done by RAM quite fast. Is it how that works?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
Python 是一种语言。 存在多种实现，并且它们可能对列表有不同的实现。 因此，如果不查看实际实现的代码，您就无法确定列表是如何实现的以及它们在某些情况下的行为方式。
我敢打赌，对列表中对象的引用存储在连续的内存中（当然不是作为链接列表......）。 如果确实如此，那么使用 x.insert 插入将导致插入元素后面的所有元素被移动。 这可以通过硬件有效地完成，但复杂性仍然是O(n)。
对于小列表，
bisect操作可能比x.insert花费更多时间，即使前者是 O(log n)，而后者是O(n)。 然而，对于长列表，我大胆猜测 x.insert 是瓶颈。 在这种情况下，您必须考虑使用不同的数据结构。Python is a language. Multiple implementations exist, and they may have different implementations for lists. So, without looking at the code of an actual implementation, you cannot know for sure how lists are implemented and how they behave under certain circumstances.
My bet would be that the references to the objects in a list are stored in contiguous memory (certainly not as a linked list...). If that is indeed so, then insertion using
x.insertwill cause all elements behind the inserted element to be moved. This may be done efficiently by the hardware, but the complexity would still be O(n).For small lists the
bisectoperation may take more time thanx.insert, even though the former is O(log n) while the latter is O(n). For long lists, however, I'd hazard a guess thatx.insertis the bottleneck. In such cases you must consider using a different data structure.如果您需要具有更好插入性能的列表，请使用 blist 模块。
Use the blist module if you need a list with better insert performance.
CPython 列表是连续的数组。 O(log n) 二等分和 O(n) 插入中哪一个主导您的性能配置文件取决于列表的大小以及 O() 内的常数因子。 特别是，根据列表中对象的类型，bisect 调用的比较函数可能会很昂贵。
如果您需要保存潜在的大型可变排序序列，那么 Python 列表类型底层的线性数组并不是一个好的选择。 根据您的要求，堆、树或跳表可能合适。
CPython lists are contiguous arrays. Which one of the O(log n) bisect and O(n) insert dominates your performance profile depends on the size of your list and also the constant factors inside the O(). Particularly, the comparison function invoked by bisect can be something expensive depending on the type of objects in the list.
If you need to hold potentially large mutable sorted sequences then the linear array underlying Pythons list type isn't a good choice. Depending on your requirements heaps, trees or skip-lists might be appropriate.