Python有一个有序字典。那么有序集呢?
当前回答
正如其他答案所提到的,对于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]
我在一个小库中添加了这些代码和一些测试,所以任何人都可以安装它。
其他回答
ParallelRegression包提供了一个setList()有序集类,它比基于ActiveState配方的选项更具有方法完整性。它支持列表中可用的所有方法,以及集合中可用的大部分方法。
PyPI上的实现
虽然其他人指出Python中还没有插入顺序保留集的内置实现,但我觉得这个问题缺少一个答案,它说明了在PyPI上可以找到什么。
这些是套餐:
有序集(基于Python) orderedset(基于Cython) collections-extended 波顿(在iterutils下。IndexedSet面向) Oset(最后更新于2012年)
其中一些实现是基于Raymond Hettinger发布到ActiveState的配方,在这里的其他回答中也提到了这个配方。
一些差异
有序集(版本1.1) 优点:O(1)用于索引查找(例如my_set[5]) Oset(版本0.1.3) 优点:O(1)用于移除(物品) 缺点:显然O(n)用于索引查找
这两个实现都有O(1)用于add(item)和__contains__(item) (my_set中的项目)。
正如其他答案所提到的,对于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]
我在一个小库中添加了这些代码和一些测试,所以任何人都可以安装它。
对于许多目的来说,简单地调用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的建议。
我可以为您提供一个比OrderedSet更好的方法:boltons有一个纯python、2/3兼容的IndexedSet类型,它不仅是一个有序集,而且还支持索引(与列表一样)。
简单的pip install boltons(或复制setutils.py到你的代码库中),导入IndexedSet和:
>>> from boltons.setutils import 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是我写的,但这也意味着如果有任何问题,您可以找我麻烦。:)
推荐文章
- 证书验证失败:无法获得本地颁发者证书
- 当使用pip3安装包时,“Python中的ssl模块不可用”
- 无法切换Python与pyenv
- Python if not == vs if !=
- 如何从scikit-learn决策树中提取决策规则?
- 为什么在Mac OS X v10.9 (Mavericks)的终端中apt-get功能不起作用?
- 将旋转的xtick标签与各自的xtick对齐
- 为什么元组可以包含可变项?
- 如何合并字典的字典?
- 如何创建类属性?
- 不区分大小写的“in”
- 在Python中获取迭代器中的元素个数
- 解析日期字符串并更改格式
- 使用try和。Python中的if
- 如何在Python中获得所有直接子目录