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


当前回答

如果您正在使用有序集来维护有序的顺序,请考虑使用来自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数据类型可用于有效地实现包。

其他回答

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

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

虽然有点晚了,但我已经编写了一个类setlist作为集合扩展的一部分,它完全实现了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/

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

答案是否定的,但是您可以使用集合。OrderedDict来自Python标准库,其中只有键(值为None),用于相同的目的。

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

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

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

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

正如其他答案所提到的,对于python 3.7+,字典是按定义排序的。我们可以继承abc.collections.MutableSet或typing,而不是继承OrderedDict。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]

我在一个小库中添加了这些代码和一些测试,所以任何人都可以安装它。

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

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

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

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