像frozenset这样维护插入顺序的数据结构？

Question

3

我需要具备以下特点的类集合数据结构:

背景说明：

frozenset([3,1,2,2,3]) -> frozenset(1,2,3)

我的需求：

frozenset*([3,1,2,2,3]) -> frozenset*(3,1,2)

我原本想使用frozenset，但是无论是set还是frozenset都重新排列了元素。我猜想这是为了更快地进行重复检查？但无论如何我都不能有重新排序。

- Octavio del Ser

3

标准库中没有这样的数据结构。 - wim

1

也许只需使用元组，并确保它们在创建时没有重复的元素。 - wim

"集合和不可变集合都不会对元素进行排序。这两种数据结构没有固有的顺序。在这种情况下，任何看到的都是实现细节，大多数 - 但并非全部 - 整数仅对其自身进行哈希处理，因此似乎排序。" - juanpa.arrivillaga

无论如何，您需要集合对象的哪些特定方面？快速查找是重要的部分吗？这是主要的集合用例。听起来您似乎只关心没有重复项... - juanpa.arrivillaga

1

例如，在Python 3.7+上，您可以仅使用元组并使用函数来确保无重复项并保持顺序（如已经提到的那样），因此只需：def no_dupe(data): return tuple(dict.fromkeys(data))。 - juanpa.arrivillaga

显示剩余2条评论

2个回答

2

标准库中没有这样的实现。

- Octavio del Ser

正确，但有点可惜... - undefined

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- John Kugelman · Accepted Answer

自 Python3.7 版本开始，字典不再重新排列元素，而是保证了插入顺序。您可以使用一个字典，其中键是您的集合项，值被忽略。

>>> dict.fromkeys([3,1,2,2,3])
{3: None, 1: None, 2: None}

字典不是冻结的，因此如果这很重要，您可以先将所有项目放入字典中，然后从键中构建元组。

>>> tuple(dict.fromkeys([3,1,2,2,3]).keys())
(3, 1, 2)

这将与frozenset非常接近。主要区别在于检查元素是否在元组中需要O（n）的时间，而不是O（1）。