Python有有序集吗?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (10)
  • 关注 (0)
  • 查看 (1383)

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

提问于
用户回答回答于

有一个有序集的方法,这是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
用户回答回答于

出于许多目的,简单地调用排序就足够了。例如

>>> 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。

用户回答回答于

官方库中没有OrderedSet。 我做了所有数据结构的详尽的cheatsheet供你参考。

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']}
用户回答回答于

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

用户回答回答于

如果你已经在你的代码中使用pandas,它的Index对象的行为非常类似于有序集,如这篇文章.

用户回答回答于

setlist作为collections-extended完全实现了这两个SequenceSet

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

Documentation: http://collections-extended.lenzm.net/en/latest/

PyPI: https://pypi.python.org/pypi/collections-extended

用户回答回答于

如果使用有序集来维护排序顺序,请考虑使用PyPI中的排序集实现。分类容器模块提供了一个SortedSet只是为了这个目的。

从PyPI安装PIP很容易:

pip install sortedcontainers

注意如果你不能pip install,只需对sortedlist.py和sortedset.py文件从开源存储库获取

一旦安装,你可以简单地:

from sortedcontainers import SortedSet
help(SortedSet)

排序容器模块还维护performance有几种不同的实现。

对于询问Python的包数据类型的评论,还有一个sortedlist数据类型,可以用来有效地实现一个包。

用户回答回答于

我可以给你一个比命令集更好的方法:pure-Python,2/-compatibleIndexedSettype这不仅是一个有序集,而且还支持索引(与列表一样)。

pip install boltons(或副本)setutils.py),将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,但这也意味着如果有什么问题,你可以打扰我.)

用户回答回答于

PyPI上的实现

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

据我所知,目前的情况如下:

两个实现都基于ActiveState教程在这里的其他答案中也提到了这一点。我已经检查了这两种情况,并确定了以下内容

关键差异:

  • 有序集(1.1版)
    • 优点:O(1)用于索引查找(例如:my_set[5])
    • 劣势:remove(item)未执行
  • Oset(0.1.3版)
    • 优势:O(1)代表remove(item)
    • 缺点:显然O(N)是按索引查找的

这两种实现都有O(1)foradd(item)__contains__(item)(二)item in my_set)。

不幸的是,这两个实现都没有类似于set1.union(set2)>你必须使用基于操作符的表单,如set1 | set2相反。见关于SET对象的Python文档有关集合操作方法及其基于运算符的等效项的完整列表。

我第一次使用定购,直到我用remove(item)这是第一次用NotImplementedError由于我迄今从未使用过索引查找,因此我同时切换到Oset。

用户回答回答于

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

字典的键是独一无二的。因此,如果忽略有序字典中的值(例如,通过赋值)None),则基本上有一个有序集。

Python 3.1collections.OrderedDict下面是OrderedSet的示例实现。(请注意,只需要定义或重写几个方法:collections.OrderedDictcollections.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__)

扫码关注云+社区

领取腾讯云代金券