Python有一个有序字典。那么有序集呢?


当前回答

正如其他人所说,OrderedDict在功能方面是有序集的超集,但如果你需要一个与API交互的集,并且不需要它是可变的,OrderedDict.keys()实际上是一个实现abc.collections.Set:

import random
from collections import OrderedDict, abc

a = list(range(0, 100))
random.shuffle(a)

# True
a == list(OrderedDict((i, 0) for i in a).keys())

# True
isinstance(OrderedDict().keys(), abc.Set)   

注意事项是不可变性,必须像字典一样构建集合,但它很简单,只使用内置。

其他回答

如果您正在使用有序集来维护有序的顺序,请考虑使用来自PyPI的有序集实现。sortedcontainers模块为此提供了一个SortedSet。一些好处:纯python,像c一样快的实现,100%的单元测试覆盖率,数小时的压力测试。

使用pip从PyPI安装很容易:

pip install sortedcontainers

注意,如果不能pip安装,只需从开源存储库中拉出sortedlist.py和sortedset.py文件。

安装完成后,您可以简单地:

from sortedcontainers import SortedSet
help(SortedSet)

sortedcontainers模块还维护了与几个备选实现的性能比较。

对于询问Python的包数据类型的注释,还有一种SortedList数据类型可用于有效地实现包。

有一个pip库是这样做的:

pip install ordered-set

然后你可以使用它:

from ordered_set import OrderedSet

如果您已经在代码中使用了pandas,那么它的Index对象的行为就非常像一个有序集,如本文所示。

文章中的例子:

indA = pd.Index([1, 3, 5, 7, 9])
indB = pd.Index([2, 3, 5, 7, 11])

indA & indB  # intersection
indA | indB  # union
indA - indB  # difference
indA ^ indB  # symmetric difference

ParallelRegression包提供了一个setList()有序集类,它比基于ActiveState配方的选项更具有方法完整性。它支持列表中可用的所有方法,以及集合中可用的大部分方法。

PyPI上的实现

虽然其他人指出Python中还没有插入顺序保留集的内置实现,但我觉得这个问题缺少一个答案,它说明了在PyPI上可以找到什么。

这些是套餐:

有序集(基于Python) orderedset(基于Cython) collections-extended 波顿(在iterutils下。IndexedSet面向) Oset(最后更新于2012年)

其中一些实现是基于Raymond Hettinger发布到ActiveState的配方,在这里的其他回答中也提到了这个配方。

一些差异

有序集(版本1.1) 优点:O(1)用于索引查找(例如my_set[5]) Oset(版本0.1.3) 优点:O(1)用于移除(物品) 缺点:显然O(n)用于索引查找

这两个实现都有O(1)用于add(item)和__contains__(item) (my_set中的项目)。