Python相当于java.util.SortedSet？

Question

有人知道Python是否具有与Java的SortedSet接口等效的东西吗？

继续我正在寻找的东西:假设我有一个类型的对象foo,我知道如何比较两个类型的对象,foo看看foo1是"大于"还是"小于" foo2.我想要一种foo在列表中存储许多类型对象的方法L,这样每当我遍历列表时L,我按照我定义的比较方法按顺序获取对象.

我想我sort()每次修改它都可以使用字典或列表,但这是最好的方法吗？

Answer 1

您可以使用insort从bisect模块到一个已排序列表中插入有效的新元素:

from bisect import insort

items = [1,5,7,9]
insort(items, 3)
insort(items, 10)

print items # -> [1, 3, 5, 7, 9, 10]

请注意,这并不直接对应SortedSet,因为它使用了一个列表.如果多次插入同一项目,则列表中将包含重复项.

实际上,它是插入的O(n) - 在向量中插入需要在插入点之后移动元素.然而,它仍然是用于查找的O(log(n)),并且排序的迭代只是O(n)(对于dict而言是vs(n*log(n)). (14认同)
不 - 只会覆盖到最后.插入中间位置时,总体分配无效:您仍然需要将一个空间的平均N/2项复制完全独立于必须为新元素分配空间. (14认同)
最后有人建议使用O(log n)实现.;) (3认同)

Answer 2

看看BTrees.看起来你需要其中一个.据我所知,你需要的结构将支持相对便宜的元素插入存储结构和廉价的排序操作(甚至缺乏它).BTrees提供.

我有ZODB.BTrees的经验,他们可以扩展到成千上万的元素.