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


当前回答

在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

其他回答

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

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

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

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

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

对于许多目的来说,简单地调用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的建议。