是python的“set"吗?稳定的? [英] Is python's "set" stable?

问题描述

在回答另一个 SO 问题时出现了这个问题(那里).

当我在一个 python 集合上迭代几次(在调用之间不改变它)时，我可以假设它总是以相同的顺序返回元素吗?如果不是，更改订单的理由是什么?它是确定性的还是随机的?还是定义了实现?

当我重复调用同一个 python 程序时(不是随机的，不依赖于输入)，我会得到相同的集合顺序吗?

潜在的问题是，python 集合迭代顺序是否仅取决于用于实现集合的算法，还是还取决于执行上下文?

解决方案

没有关于集合稳定性的正式保证.但是，在 CPython 实现中，只要没有更改集合，项目就会以相同的顺序生成.集合被实现为开放寻址哈希表(带有主探针)，因此插入或删除项目可以完全改变顺序(特别是当触发调整大小时，它会重新组织项目在内存中的布局.)您还可以有两个相同的集合，但它们以不同的顺序生成项目，例如:

<预><代码>>>>s1 = {-1, -2}>>>s2 = {-2, -1}>>>s1 == s2真的>>>列表(s1)，列表(s2)([-1, -2], [-2, -1])

除非你非常确定你有相同的集合并且在两次迭代之间没有任何东西触及它，否则最好不要依赖它保持不变.例如，对您在中间调用的函数进行看似无关的更改可能会导致很难找到错误.

The question arose when answering to another SO question (there).

When I iterate several times over a python set (without changing it between calls), can I assume it will always return elements in the same order? And if not, what is the rationale of changing the order ? Is it deterministic, or random? Or implementation defined?

And when I call the same python program repeatedly (not random, not input dependent), will I get the same ordering for sets?

The underlying question is if python set iteration order only depends on the algorithm used to implement sets, or also on the execution context?

解决方案

There's no formal guarantee about the stability of sets. However, in the CPython implementation, as long as nothing changes the set, the items will be produced in the same order. Sets are implemented as open-addressing hashtables (with a prime probe), so inserting or removing items can completely change the order (in particular, when that triggers a resize, which reorganizes how the items are laid out in memory.) You can also have two identical sets that nonetheless produce the items in different order, for example:

>>> s1 = {-1, -2}
>>> s2 = {-2, -1}
>>> s1 == s2
True
>>> list(s1), list(s2)
([-1, -2], [-2, -1])

Unless you're very certain you have the same set and nothing touched it inbetween the two iterations, it's best not to rely on it staying the same. Making seemingly irrelevant changes to, say, functions you call inbetween could produce very hard to find bugs.

这篇关于是python的“set"吗?稳定的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！