是python的“集合"吗?稳定的?
问题描述
在回答另一个 SO 问题时出现了问题(那里).
The question arose when answering to another SO question (there).
当我对一个 python 集进行多次迭代(在调用之间不更改它)时，我可以假设它总是以相同的顺序返回元素吗?如果不是，改变订单的理由是什么?它是确定性的还是随机的?还是定义了实现?
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?
当我重复调用同一个 python 程序时(不是随机的，不依赖于输入)，我会得到相同的集合排序吗?
And when I call the same python program repeatedly (not random, not input dependent), will I get the same ordering for sets?
潜在的问题是，python 集合迭代顺序是否仅取决于用于实现集合的算法，还是还取决于执行上下文?
The underlying question is if python set iteration order only depends on the algorithm used to implement sets, or also on the execution context?
解决方案
集合的稳定性没有正式的保证.然而，在 CPython 实现中，只要不改变集合，项目将以相同的顺序生成.集合被实现为开放寻址哈希表(带有主探针)，因此插入或删除项目可以完全改变顺序(特别是当触发调整大小时，它会重新组织项目在内存中的布局方式.)您还可以有两个相同的集合，但是以不同的顺序生成项目，例如:
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.
相关文章