Python有有序集吗?

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

539050 次浏览
小开
最佳答案

有一个有序集合(可能是新链接)的配方，从Python 2文档引用。它运行在Py2.6或更高版本和3.0或更高版本上，无需任何修改。该接口几乎与普通的set完全相同，除了初始化应该使用一个列表。

OrderedSet([1, 2, 3])

这是一个可变集，所以.union的签名与set的签名不匹配，但由于它包括__or__，可以很容易地添加类似的东西:

@staticmethod
def union(*sets):
union = OrderedSet()
union.union(*sets)
return union


def union(self, *sets):
for set in sets:
self |= set
小开

更新:这个答案在Python 3.7已经过时了。请参阅上面的联合研究中心的的回答以获得更好的解决方案。出于历史原因，我将保留这个答案。

有序集在功能上是有序字典的一种特殊情况。

字典的键是唯一的。因此，如果忽略有序字典中的值(例如将它们赋值为None)，那么本质上就是有序集。

在Python 3．1和2.7中有collections.OrderedDict。下面是OrderedSet的一个示例实现。(注意，只有少数方法需要定义或重写:collections.OrderedDict和collections.MutableSet做了繁重的工作。)

import collections


class OrderedSet(collections.OrderedDict, collections.MutableSet):


def update(self, *args, **kwargs):
if kwargs:
raise TypeError("update() takes no keyword arguments")


for s in args:
for e in s:
self.add(e)


def add(self, elem):
self[elem] = None


def discard(self, elem):
self.pop(elem, None)


def __le__(self, other):
return all(e in other for e in self)


def __lt__(self, other):
return self <= other and self != other


def __ge__(self, other):
return all(e in self for e in other)


def __gt__(self, other):
return self >= other and self != other


def __repr__(self):
return 'OrderedSet([%s])' % (', '.join(map(repr, self.keys())))


def __str__(self):
return '{%s}' % (', '.join(map(repr, self.keys())))
    

difference = property(lambda self: self.__sub__)
difference_update = property(lambda self: self.__isub__)
intersection = property(lambda self: self.__and__)
intersection_update = property(lambda self: self.__iand__)
issubset = property(lambda self: self.__le__)
issuperset = property(lambda self: self.__ge__)
symmetric_difference = property(lambda self: self.__xor__)
symmetric_difference_update = property(lambda self: self.__ixor__)
union = property(lambda self: self.__or__)
小开

对于许多目的来说，简单地调用sorted就足够了。例如

>>> s = set([0, 1, 2, 99, 4, 40, 3, 20, 24, 100, 60])
>>> sorted(s)
[0, 1, 2, 3, 4, 20, 24, 40, 60, 99, 100]

如果你要重复使用它，调用排序函数会产生开销，所以你可能想要保存结果列表，只要你完成了对集合的更改。如果您需要维护唯一的元素并进行排序，我同意从具有任意值(如None)的集合中使用OrderedDict的建议。

小开

PyPI上的实现

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

这些是套餐:

其中一些实现是基于食谱由Raymond Hettinger发布到ActiveState的，在这里的其他答案中也提到过。

一些差异

  • 有序集(版本1.1)
  • 优点:O(1)用于索引查找(例如my_set[5])
  • Oset(版本0.1.3)
  • 优势:O(1) remove(item)
  • 缺点:显然O(n)用于索引查找

两个实现都有O(1)用于add(item)和__contains__(item) (item in my_set)。

小开

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

使用pip从PyPI安装很容易:

pip install sortedcontainers

注意，如果您不能pip install，只需从开源库中下拉sortedlist.py和sortedset.py文件。

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

from sortedcontainers import SortedSet
help(SortedSet)

sortedcontainers模块还使用几个可选实现维护性能比较。

对于询问Python的包数据类型的注释，可以使用SortedList数据类型来有效地实现包。

小开

虽然有点晚了，但我已经编写了一个类setlist，作为collections-extended的一部分，它完全实现了Sequence和Set

>>> from collections_extended import setlist
>>> sl = setlist('abracadabra')
>>> sl
setlist(('a', 'b', 'r', 'c', 'd'))
>>> sl[3]
'c'
>>> sl[-1]
'd'
>>> 'r' in sl  # testing for inclusion is fast
True
>>> sl.index('d')  # so is finding the index of an element
4
>>> sl.insert(1, 'd')  # inserting an element already in raises a ValueError
ValueError
>>> sl.index('d')
4

GitHub: # EYZ0

文档:# EYZ0

PyPI: # EYZ0

小开

如果您已经在代码中使用了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
小开

我可以为您提供一个比OrderedSet更好的方法:boltons具有一个纯python, 2/3兼容的IndexedSet类型，它不仅是一个有序集，而且还支持索引(与列表一样)。

简单地pip install boltons(或复制setutils.py到你的代码库)，导入IndexedSet和:

>>> from boltons.setutils import IndexedSet
>>> x = IndexedSet(list(range(4)) + list(range(8)))
>>> x
IndexedSet([0, 1, 2, 3, 4, 5, 6, 7])
>>> x - set(range(2))
IndexedSet([2, 3, 4, 5, 6, 7])
>>> x[-1]
7
>>> fcr = IndexedSet('freecreditreport.com')
>>> ''.join(fcr[:fcr.index('.')])
'frecditpo'

一切都是唯一的，并保持有序。完全披露:我写了IndexedSet，但这也意味着如果有什么问题你可以找我。：）

小开

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

小开
官方库中没有OrderedSet。 我为所有数据结构做了一个详尽的备忘单，供您参考 
DataStructure = {
'Collections': {
'Map': [
('dict', 'OrderDict', 'defaultdict'),
('chainmap', 'types.MappingProxyType')
],
'Set': [('set', 'frozenset'), {'multiset': 'collection.Counter'}]
},
'Sequence': {
'Basic': ['list', 'tuple', 'iterator']
},
'Algorithm': {
'Priority': ['heapq', 'queue.PriorityQueue'],
'Queue': ['queue.Queue', 'multiprocessing.Queue'],
'Stack': ['collection.deque', 'queue.LifeQueue']
},
'text_sequence': ['str', 'byte', 'bytearray']
}
小开

所以我也有一个小列表，我显然有可能引入非唯一的值。

我搜索是否存在某种唯一列表，但随后意识到在添加元素之前测试元素是否存在就可以了。

if(not new_element in my_list):
my_list.append(new_element)

我不知道这种简单的方法是否需要注意，但它解决了我的问题。

小开

答案是否定的，但是出于同样的目的，你可以使用Python标准库中的collections.OrderedDict，其中只有键(值为None)。

更新:从Python 3.7(和CPython 3.6)开始，标准的dict是保证维持秩序，比OrderedDict性能更好。(但是，为了向后兼容性，特别是可读性，您可能希望继续使用OrderedDict。)

下面是一个示例，说明如何使用dict作为有序集，在保留顺序的同时过滤掉重复项，从而模拟有序集。使用dict类方法fromkeys()创建字典，然后简单地要求返回keys()。

>>> keywords = ['foo', 'bar', 'bar', 'foo', 'baz', 'foo']


>>> list(dict.fromkeys(keywords))
['foo', 'bar', 'baz']
小开

正如其他答案所提到的，对于python 3.7+，字典是按定义排序的。而不是子类化OrderedDict，我们可以子类化abc.collections.MutableSet或typing.MutableSet，使用字典的键来存储我们的值。

import itertools
import typing


T = typing.TypeVar("T")


class OrderedSet(typing.MutableSet[T]):
"""A set that preserves insertion order by internally using a dict."""


def __init__(self, iterable: typing.Iterator[T]):
self._d = dict.fromkeys(iterable)


def add(self, x: T) -> None:
self._d[x] = None


def discard(self, x: T) -> None:
self._d.pop(x, None)


def __contains__(self, x: object) -> bool:
return self._d.__contains__(x)


def __len__(self) -> int:
return self._d.__len__()


def __iter__(self) -> typing.Iterator[T]:
return self._d.__iter__()


def __str__(self):
return f"\{\{{', '.join(str(i) for i in self)}}}"


def __repr__(self):
return f"<OrderedSet {self}>"

然后:

x = OrderedSet([1, 2, -1, "bar"])
x.add(0)
assert list(x) == [1, 2, -1, "bar", 0]

我在一个小库中添加了这段代码和一些测试，所以任何人都可以pip install它。

小开

正如其他人所说，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)

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

小开

有一个种子库做这个:

pip install ordered-set

然后你可以使用它:

from ordered_set import OrderedSet

提交答案