列表（...）的性能。插入（...） [英] Performance of list(...).insert(...)

问题描述

我想到了有关计算机的体系结构以下问​​题。假设我在Python做

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()

这需要日志N ，再加上，如果我理解正确，为内存拷贝操作X [指数：] 。现在，我看最近，瓶颈通常是在处理器和内存之间的通信使内存拷贝的可能的被RAM比较快的完成。它是如何工作的？

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?

推荐答案

Python是一种语言。 多种实现的存在，并且它们的可能的有列出了不同的实现。所以，不看实际实现的code，你可以不知道如何肯定列表的实施，他们在某些情况下的行为方式。

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.

我的选择将是在一个列表中的对象的引用存储在连续的存储器（当然不是一个链表...）。如果确实是这样，那么插入使用 x.insert 将导致插入的元素之后的所有元素被移动。这可以有效地由硬件来完成，但复杂性仍然是为O（n）的

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.insert will 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).

有关小型列出了开张操作可能需要更多的时间比 x.insert ，尽管前者是 O（log n）的的而后者是的 O（N）的。对于长的列表，但是，我会大胆地猜测 x.insert 是瓶颈。在这种情况下，必须考虑使用不同的数据结构。

For small lists the bisect operation may take more time than x.insert, even though the former is O(log n) while the latter is O(n). For long lists, however, I'd hazard a guess that x.insert is the bottleneck. In such cases you must consider using a different data structure.

这篇关于列表（...）的性能。插入（...）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！