Python有一个有序集吗？

Question

Python有一个有序的字典.订购套装怎么样？

Answer 1

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

OrderedSet([1, 2, 3])

这是一个MutableSet,因此签名.union与set 的签名不匹配,但由于它包含__or__类似的东西可以很容易地添加:

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

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

Answer 2

有序集在功能上是有序字典的特例.

字典的键是唯一的.因此,如果忽略有序字典中的值(例如通过分配它们None),则基本上具有有序集.

对于Python 3.1的存在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__)

Answer 3

答案是否定的,但您可以使用collections.OrderedDict(在Python标准库中)只使用键(和值为None)来实现相同的目的.

以下是如何使用dict有序集来过滤掉重复项目同时保留顺序的示例:

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

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

Answer 4

我可以比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,但这也意味着如果有任何问题你可以告诉我.:)

Answer 5

关于PyPI的实现

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

据我所知,目前有:

• 有序集
• OSET

两种实现都基于Raymond Hettinger发布给ActiveState的配方,这也在其他答案中提到.我已经检查了两个并确定了以下内容

关键差异:

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

两种实现都有O(1)for add(item)和__contains__(item)(item in my_set).

遗憾的是,这两种实现都没有基于方法的集合操作,例如set1.union(set2)- >您必须使用基于运算符的表单set1 | set2.有关set操作方法及其基于运算符的等效项的完整列表,请参阅Set Objects上的Python文档.

我第一次使用有序集,直到我remove(item)第一次用它来崩溃我的脚本NotImplementedError.因为到目前为止我从未使用过索引查找,所以我同时切换到了oset.

如果您了解PyPI的其他实现,请在评论中告诉我.

Answer 6

如果您使用有序集来维护排序顺序,请考虑使用PyPI中的排序集实现.该sortedcontainers模块提供了一个SortedSet的只是这个目的.一些好处:纯Python,快速实施,100%单元测试覆盖,数小时的压力测试.

使用pip从PyPI轻松安装:

pip install sortedcontainers

请注意,如果您不能pip install,只需从开源存储库中下载 sortedlist.py和sortedset.py文件.

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

from sortedcontainers import SortedSet
help(SortedSet)

sortedcontainers模块还与几个替代实现保持性能比较.

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

Answer 7

如果您已在代码中使用pandas,则其Index对象的行为非常类似于有序集,如本文所示.

Answer 8

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']
}

Answer 9

正如其他答案所提到的，对于 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它。

Answer 10

有点晚了比赛,但我已经写了一类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

Answer 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)   

需要注意的是不变性和必须像字典一样构建集合，但它很简单并且仅使用内置函数。