python的"设置"稳定吗？

Question

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

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

当我反复调用相同的python程序(不是随机的,不依赖于输入)时,我会得到相同的排序吗？

基本问题是,如果python set迭代顺序仅取决于用于实现集合的算法,还取决于执行上下文？

Answer 1

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

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

除非你非常肯定你有相同的设置,并且在两次迭代之间没有触及它,所以最好不要依赖它保持不变.对你说的函数进行看似无关紧要的更改会产生非常难以发现的错误.

Answer 2

A setorfrozenset本质上是一个无序集合。在内部，集合基于哈希表，键的顺序取决于插入顺序和hash算法。在 CPython（又名标准 Python）中，小于机器字大小（32 位或 64 位）的整数散列到它们自己，但文本字符串、bytes字符串和datetime对象散列到随机变化的整数；您可以通过设置PYTHONHASHSEED环境变量来控制它。

从__hash__文档：

笔记

默认情况下，该__hash__()值str，bytes并且datetime 对象是“咸”不可预测的随机值。尽管它们在单个 Python 进程中保持不变，但它们在 Python 的重复调用之间是不可预测的。

这旨在提供保护，防止由精心选择的输入引起的拒绝服务，这些输入利用了 dict 插入的最坏情况性能，O(n^2) 复杂度。有关详细信息，请参阅 http://www.ocert.org/advisories/ocert-2011-003.html。

更改哈希值会影响字典、集合和其他映射的迭代顺序。Python 从未对此排序做出保证（并且它通常在 32 位和 64 位版本之间变化）。

另见 PYTHONHASHSEED。

散列其他类的对象的结果取决于该类的__hash__方法的细节。

所有这一切的结果是，您可以有两个包含相同字符串的集合，但是当您将它们转换为列表时，它们可以比较不相等。或者他们可能不会。;) 下面是一些演示这一点的代码。在某些运行中，它只会循环，不打印任何内容，但在其他运行中，它会快速找到使用与原始顺序不同的集合。

from random import seed, shuffle

seed(42)

data = list('abcdefgh')
a = frozenset(data)
la = list(a)
print(''.join(la), a)

while True:
    shuffle(data)
    lb = list(frozenset(data))
    if lb != la:
        print(''.join(data), ''.join(lb))
        break    

典型输出

dachbgef frozenset({'d', 'a', 'c', 'h', 'b', 'g', 'e', 'f'})
deghcfab dahcbgef