set.pop() 是确定性的吗? [英] Is set.pop() deterministic?

问题描述

我知道python集合的元素没有顺序.调用 pop 方法返回任意元素；我没问题.

I understand that the elements of a python set are not ordered. Calling the pop method returns an arbitrary element; I'm fine with that.

我想知道的是，当集合具有相同的历史时，pop 是否总是返回相同的元素.当然，在 python 的一个版本中，我不介意 python 的不同版本/实现是否做自己的事情.特别是，我问的是 python 2.7.在这种情况下，这是一个实现而不是 api 的问题.

What I'm wondering is whether or not pop will ALWAYS return the same element when the set has the same history. Within one version of python of course, I don't mind if different versions/implementations of python do their own thing. In particular, I'm asking about python 2.7. It's a matter of implementation more than of api in this case.

我在游戏的程序化地牢生成器中经常使用集合，并且我希望结果对于给定的种子是确定性的.

I'm using sets a lot in a procedural dungeon generator for a game, and I'd like the outcome to be deterministic for a given seed.

推荐答案

一般的答案是否.@Christophe 和 @Marcin (un) 帮助指向的 python 源表明元素是按照它们出现在哈希表中的顺序弹出.因此，弹出顺序(可能是迭代顺序) 是确定性的，但仅适用于固定 哈希值.根据__hash__，顺便提一下，这也直接涉及到您的问题:

The answer in general is no. The python source that @Christophe and @Marcin (un)helpfully point to shows that elements are popped in the order they appear in the hash table. So, pop order (and presumably iteration order) is deterministic, but only for fixed hash values. That's the case for numbers but not for strings, according to the Note in the documentation of __hash__, which incidentally also touches on your question directly:

注意默认情况下，str、bytes 和 datetime 对象的 hash() 值是用不可预测的随机值加盐"的.尽管它们在单个 Python 进程中保持不变，但它们在 Python 的重复调用之间是不可预测的.

Note by default the hash() values of str, bytes and datetime objects are "salted" with an unpredictable random value. Although they remain constant within an individual Python process, they are not predictable between repeated invocations of Python.

[ ... ]

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

Changing hash values affects the iteration order of dicts, sets and other mappings. Python has never made guarantees about this ordering (and it typically varies between 32-bit and 64-bit builds).

正如@Marcin 指出的那样，我引用的链接不适用于 Python 2.哈希随机化成为 Python 3.3 的默认设置. Python 2.7 没有故意非- 默认情况下确定性字符串散列.

As @Marcin points out, the link I quoted does not apply to Python 2. Hash randomization became the default with Python 3.3. Python 2.7 does not have intentionally non-deterministic string hashing by default.

一般来说，对于散列不是其值的可重复函数的任何对象(例如，如果散列基于内存地址)，这是一个问题.但相反，如果您为集合中的对象定义自己的 __hash__ 方法，则可以预期它们将以可重现的顺序返回.(前提是设置的历史记录和平台保持固定).

In general, this is a problem for any object whose hash is not a repeatable function of its value (e.g., if the hash is based on memory address). But conversely, if you define your own __hash__ method for the objects in your sets, you can expect that they will be returned in a reproducible order. (Provided the set's history and the platform are kept fixed).

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