有序集 5.2.3

有序集是一个包含多个有序集合实现的包。

OrderlySet

这个实现除集合差操作外，在所有集合操作中保持顺序。因此，它比其他实现能够更快地执行集合差操作。但仍比Python内置的集合慢2倍。

StableSet

StableSet是一个可变集合，它记住其插入顺序。功能：快速O(1)插入、删除、迭代和成员资格测试。但索引查找慢O(N)。

StableSetEq

与StableSet相同，但项目顺序对于相等性比较不重要。

OrderedSet

OrderedSet是一个混合了列表和集合的可变数据结构。它记住其插入顺序，因此每个条目都有一个可查找的索引。功能：O(1)索引查找、插入、迭代和成员资格测试。但删除慢O(N)。

SortedSet

SortedSet基本上是集合，但在打印、转换为字符串或迭代时，按字母顺序返回项目。

安装

pip install orderly-set

用法示例

有序集的创建和使用就像一个集合

>>> from orderly_set import OrderedSet

>>> letters = OrderedSet('abracadabra')

>>> letters
OrderedSet(['a', 'b', 'r', 'c', 'd'])

>>> 'r' in letters
True

在有序集中查找条目的索引或通过索引查找条目是高效的。为了帮助这种用法情况，.add()方法返回添加项的索引，无论它是否已在集合中。

>>> letters.index('r')
2

>>> letters[2]
'r'

>>> letters.add('r')
2

>>> letters.add('x')
5

有序集实现了像集合一样的并集（|）、交集（&）和差集（-）运算符。

>>> letters |= OrderedSet('shazam')

>>> letters
OrderedSet(['a', 'b', 'r', 'c', 'd', 'x', 's', 'h', 'z', 'm'])

>>> letters & set('aeiou')
OrderedSet(['a'])

>>> letters -= 'abcd'

>>> letters
OrderedSet(['r', 'x', 's', 'h', 'z', 'm'])

已扩展 __getitem__() 和 index() 方法，使其可以接受任何可迭代对象（除了字符串），并返回一个列表，以执行类似 NumPy 的“复杂索引”。

>>> letters = OrderedSet('abracadabra')

>>> letters[[0, 2, 3]]
['a', 'r', 'c']

>>> letters.index(['a', 'r', 'c'])
[0, 2, 3]

OrderedSet 实现了 __getstate__ 和 __setstate__ 方法，因此可以被序列化，并实现了 collections.MutableSet 和 collections.Sequence 抽象基类。

OrderedSet 可以用作通用集合类型，类似于 typing 模块中的集合，如 List、Dict 和 Set。例如，您可以注释一个变量具有类型 OrderedSet[str] 或 OrderedSet[Tuple[int, str]]。

作者

请检查 作者 文件。

比较

-- initialize a set --
Using Python dict time: 4.13
set time: 2.98
ordered_set.OrderedSet time: 15.77
orderly_set.OrderedSet time: 15.25
StableSet time: 4.78
OrderlySet time: 4.38
SortedSet time: 3.09

-- update a set --
Using Python dict: 6.77
set time: 2.46
ordered_set.OrderedSet time: 10.17
orderly_set.OrderedSet time: 10.06
StableSet time: 7.16
OrderlySet time: 6.77
SortedSet time: 2.46

-- update a set and get item --
ordered_set.OrderedSet time: 29.98
orderly_set.OrderedSet time: 29.57
StableSet time: 14.31
OrderlySet time: 14.23
SortedSet time: 9.03

-- set symmetric difference (xor) --
set time: 5.368663903005654
ordered_set.OrderedSet time: 39.25
orderly_set.OrderedSet time: 80.31
StableSet time: 42.81
OrderlySet time: 11.44
SortedSet time: 3.87

-- set difference (-) --
set time: 3.7398674299911363
ordered_set.OrderedSet time: 22.39
orderly_set.OrderedSet time: 38.00
StableSet time: 22.30
OrderlySet time: 8.92
SortedSet time: 3.03

尽管从基准测试中可以看到，但在 DeepDiff 中，OrderedSet 的性能优于 SortedSet。

StableSet是一个可变集合，它记住其插入顺序。功能：快速O(1)插入、删除、迭代和成员资格测试。但索引查找慢O(N)。

OrderedSet是一个混合了列表和集合的可变数据结构。它记住其插入顺序，因此每个条目都有一个可查找的索引。功能：O(1)索引查找、插入、迭代和成员资格测试。但删除慢O(N)。

它们都具有类似的接口，但在实现和性能方面有所不同。

OrderedSet 的原始实现是由 Raymond Hettiger 在 ActiveState Recipes 上发布的一个 食谱，在 MIT 许可下发布。

Hettiger 的实现将内容保存在一个由字典引用的双向链表中。因此，通过索引查找项目是 O(N) 操作，而删除是 O(1)。

这个版本的 OrderedSet 为了高效的查找做了不同的权衡。其内容是标准的 Python 列表，而不是双向链表。这提供了 O(1) 的索引查找，但删除是 O(N)，以及迭代速度略微更快。