Python 在某个位置插入列表的成本/复杂性是多少？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/27073596/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is the cost/ complexity of insert in list at some location?
提问by user3654650
In Python, a listhas list.insert(i, x)to "Insert an item at a given position.". In C++, there is a listas well. In C++, cost/complexity of inserting an element anywhere is O(1). Is it the same for a Python list? If not, can anything else be use to get O(1) insert time in Python?
在 Python 中，列表必须list.insert(i, x)“在给定位置插入项目”。在 C++ 中，也有一个列表。在 C++ 中，在任何地方插入元素的成本/复杂性是 O(1)。Python列表是否相同？如果没有，还有什么可以用来在 Python 中获得 O(1) 插入时间吗？
采纳答案by BrenBarn
The Python language doesn't specify the implementation of such operations, so different implementations may have different behavior. For CPython, the complexity of list.insertis O(n), as shown on this useful wiki page. I'm not aware of any list-like structure giving O(1) performance for inserting at an arbitrary index. (A dict gives O(1) insert performance in the average case, but is not ordered and does not enforce a contiguous sequence of indices.) The blistlibrary provides an optimized list type that has an O(log n) insert.
Python 语言并没有指定此类操作的实现，因此不同的实现可能会有不同的行为。对于 CPython，复杂度list.insert是 O(n)，如这个有用的 wiki 页面所示。我不知道任何类似列表的结构为在任意索引处插入提供 O(1) 性能。（字典在平均情况下提供 O(1) 插入性能，但没有排序并且不强制执行连续的索引序列。）该blist库提供了一个优化的列表类型，它具有 O(log n) 插入。
回答by Isuru Madusanka
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.
Python是一种语言。存在多种实现，它们可能对列表有不同的实现。因此，如果不查看实际实现的代码，您就无法确定列表是如何实现的以及它们在某些情况下的行为方式。
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(n)。
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.
对于小列表，平分操作可能比 x.insert 花费更多时间，即使前者是 O(log n) 而后者是 O(n)。但是，对于长列表，我会猜测 x.insert 是瓶颈。在这种情况下，您必须考虑使用不同的数据结构。
回答by Isuru Madusanka
No, it is not the same complexity. According to Python's official Time Complexitypage1, using list.insertalways has O(n)(linear) complexity.
不，它不是同样的复杂性。根据 Python 的官方时间复杂度第1页，使用list.insert始终具有O(n)（线性）复杂度。
Also, a Python list is not exactly the same as a C++ list. In fact, a Python list is more comparable to a C++ std::vectorif anything.
此外，Python 列表与 C++ 列表并不完全相同。事实上，std::vector如果有的话，Python 列表与 C++ 更具有可比性。
1Well, CPython's official page. I don't know about other implementations such as IronPython or Jython.
1好吧，CPython 的官方页面。我不知道其他实现，例如 IronPython 或 Jython。
回答by Tanveer Alam
list
列表
The Average Case assumes parameters generated uniformly at random.
平均情况假设参数是随机均匀生成的。
Internally, a list is represented as an array; the largest costs come from growing beyond the current allocation size (because everything must move), or from inserting or deleting somewhere near the beginning (because everything after that must move). If you need to add/remove at both ends, consider using a collections.deque instead.
在内部，列表表示为数组；最大的成本来自超出当前分配大小的增长（因为一切都必须移动），或者来自在开头附近的某个地方插入或删除（因为之后的所有内容都必须移动）。如果您需要在两端添加/删除，请考虑使用 collections.deque。
So inserting an element at given position will always have the time complexity of O(n)as both insertmethod and slicinghas time complexity of O(n)and O(k). Only appendwhich inserts at the end of list have O(1)time complexity. From Python Wiki
因此，在给定位置插入元素将始终具有O(n)的时间复杂度，因为插入方法和切片的时间复杂度均为O(n)和O(k)。只有在列表末尾插入的append具有O(1)时间复杂度。来自Python 维基
Lists:
Complexity
Operation | Example | Class | Notes
--------------+--------------+---------------+-------------------------------
Index | l[i] | O(1) |
Store | l[i] = 0 | O(1) |
Length | len(l) | O(1) |
Append | l.append(5) | O(1) |
Clear | l.clear() | O(1) | similar to l = []
Slice | l[a:b] | O(b-a) | l[1:5]:O(l)/l[:]:O(len(l)-0)=O(N)
Extend | l.extend(...)| O(len(...)) | depends only on len of extension
Construction | list(...) | len(...) | depends on lenghth of argument
check ==, != | l1 == l2 | O(N) |
Insert | l[a:b] = ... | O(N) |
Delete | del l[i] | O(N) |
Remove | l.remove(...)| O(N) |
Containment | x in/not in l| O(N) | searches list
Copy | l.copy() | O(N) | Same as l[:] which is O(N)
Pop | l.pop(...) | O(N) |
Pop | l.pop() | O(1) | same as l.pop(-1), popping at end
Extreme value | min(l)/max(l)| O(N) |
Reverse | l.reverse() | O(N) |
Iteration | for v in l: | O(N) |
Sort | l.sort() | O(N Log N) | key/reverse doesn't change this
Multiply | k*l | O(k N) | 5*l is O(N): len(l)*l is O(N**2)
From here
从这里
