Python 有有序集吗？
- 2024-11-26 08:36:00
- admin 原创
- 156
问题描述：
Python 有一个有序字典。那么有序集合呢？
解决方案 1：
答案是否定的，但是从 Python 3.7 开始，您可以使用dictPython 标准库中的简单功能（仅使用键（和值None））来实现相同目的。
以下是如何使用dict有序集来过滤重复项并保持顺序的示例，从而模拟有序集。使用dict类方法fromkeys()创建一个字典，然后简单地请求返回keys()。
>>> keywords = ['foo', 'bar', 'bar', 'foo', 'baz', 'foo']
>>> list(dict.fromkeys(keywords))
['foo', 'bar', 'baz']
对于较旧版本的 Python，使用collections.OrderedDict
解决方案 2：
有一个有序集（可能的新链接）配方，可从Python 2 文档中引用。它可在 Py2.6 或更高版本和 3.0 或更高版本上运行，无需任何修改。界面几乎与普通集合完全相同，只是初始化应使用列表完成。
OrderedSet([1, 2, 3])
这是一个 MutableSet，因此的签名与.unionset 的签名不匹配，但由于它包含__or__类似的内容，因此可以轻松添加：
@staticmethod
def union(*sets):
union = OrderedSet()
union.union(*sets)
return union
def union(self, *sets):
for set in sets:
self |= set
解决方案 3：
更新：从 Python 3.7 开始，此答案已过时。请参阅上面的 jrc 答案以获得更好的解决方案。仅出于历史原因，才会在此处保留此答案。
有序集在功能上是有序词典的特例。
字典的键是唯一的。因此，如果忽略有序字典中的值（例如通过赋值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__)
解决方案 4：
PyPI 上的实现
虽然其他人已经指出 Python 中还没有内置的插入顺序保留集实现（但是），但我觉得这个问题缺少一个答案，无法说明在PyPI上可以找到什么。
有以下软件包：
有序集（基于 Python）
收藏集扩展
boltons（在setutils.IndexedSet下，基于 Python）
oset（2012 年最新更新）
其中一些实现基于Raymond Hettinger 向 ActiveState 发布的配方，该配方也在其他答案中提到。
存在一些差异
有序集（版本 1.1）
优点：通过索引查找的时间复杂度为 O(1)（例如
my_set[5]）orset（版本 0.1.3）
优点：O（1）
remove(item)缺点：通过索引查找显然是 O(n)
add(item)两种实现对于和__contains__(item)( )都是 O(1) item in my_set。
解决方案 5：
我可以为您提供一个比 OrderedSet 更好的：boltons 有一个纯 PythonIndexedSet类型，它不仅是一个有序集合，而且还支持索引（与列表一样）。
只需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，但这也意味着如果有任何问题，你可以来找我。
解决方案 6：
如果您使用有序集来保持排序顺序，请考虑使用 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数据类型，可用于有效地实现包。
解决方案 7：
正如其他答案所提到的，对于 python 3.7+，是按定义排序的。我们可以子类化或使用 的键来存储我们的值，dict而不是子类化。OrderedDict`abc.collections.MutableSettyping.MutableSetdict`
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.Iterable[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它。
解决方案 8：
如果您已经在代码中使用 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
解决方案 9：
有点晚了，但我已经写了一个类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：https ://github.com/mlenzen/collections-extended
文档：http://collections-extended.lenzm.net/en/latest/
PyPI：https://pypi.python.org/pypi/collections-extended
解决方案 10：
官方库中没有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']
}
解决方案 11：
正如其他人所说，就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)
需要注意的是其不可变性，并且必须像字典一样建立集合，但它很简单并且只使用内置函数。
解决方案 12：
ParallelRegression包提供了一个setList( )有序集合类，它比基于 ActiveState 配方的选项方法更完整。它支持列表可用的所有方法，以及集合可用的大多数（如果不是全部）方法。
解决方案 13：
有一个pip 库可以做到这一点：
pip install ordered-set
然后你就可以使用它了：
from ordered_set import OrderedSet
解决方案 14：
只需使用pd.unique-pandas即可满足您的需要！
>>> import pandas as pd
>>> pd.unique([3, 1, 4, 5, 2, 2])
array([3, 1, 4, 5, 2])
解决方案 15：
这个答案是为了完整性。如果你的代码长度set很小，并且你的代码是单线程的，那么 alist就可以正常工作，因为它是隐式排序的。
if not new_item in my_list:
my_list.append(new_item)
如果使用此方法：
要附加或删除项目，首先要检查是否存在，如上面的代码所示。
要比较相等性，请使用
set(my_list)。
检查列表中是否存在当然具有 O（n）复杂度，但对于小列表来说这可能是可以接受的，特别是如果不需要高性能的话。
解决方案 16：
对于许多目的来说，只需调用 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]
如果您要重复使用此功能，则调用 sorted 函数会产生开销，因此您可能希望保存结果列表，只要您已完成更改集合即可。如果您需要维护唯一元素并进行排序，我同意使用 OrderedDict 的建议，该建议来自具有任意值（例如 None）的集合。
