Python的平分线如何工作？

Question

我读过Python的列表是使用指针实现的。然后我看到这个模块http://docs.python.org/2/library/bisect.html高效地插入一个排序列表。它如何有效地做到这一点？如果列表是使用指针而不是通过连续数组实现的，那么如何有效地搜索插入点？如果列表是通过一个连续的数组来支持的，那么当插入一个元素时就不得不进行元素移位。那么这个bisect如何有效地工作呢？

Answer 1

我相信列表中的元素是指向的，但“列表”实际上是一个连续的数组（在C中）。他们被称为列表，但他们不是链接列表。

实际上，在排序列表中查找元素非常好 - 它是O（logn）。但插入不是很好 - 它是O（n）。

如果你需要一个logn数据结构，最好使用一个树木或红黑树。

Answer 2

这是有效的搜索，而不是实际的插入。快速搜索使得整个操作“增加一个值并保持所有值的顺序”比较快，例如，再次附加然后再排序：O(n)而不是O(n log n)。