set.pop()是确定性的吗？

Question

set.pop()是确定性的吗？

pythonset

27

我知道python set的元素是无序的。调用pop方法会返回任意一个元素；这一点我没问题。

我想知道的是，在同样的历史记录下，pop是否总是返回相同的元素。当然，我不介意不同版本/实现的Python做出自己的事情。特别是，我询问的是Python 2.7。在这种情况下，这更多是一种实现方式而不是API的问题。

我在一个过程化地图生成器中经常使用set，并且希望给定种子时结果是确定性的。

- Niriel

1

相关链接：https://dev59.com/o2865IYBdhLWcg3wLbar 和 http://svn.python.org/view/python/trunk/Objects/setobject.c?view=markup - ChristopheD

2

为什么不测试一下/查看源代码呢？ - Marcin

@delnan，“特别是，我在问关于Python 2.7的问题。这更多是实现的问题，而不是API的问题。”因此，无需像您建议的那样测试多个版本或未来版本。您似乎想象了可移植性和永恒的要求。 - Marcin

1

啊，Marcin，对不起，我没注意到。这有点本能反应，很多类似的评论实际上都有我错误指责你的那种缺陷（“C89中是否存在未定义行为？”——“只需尝试在您的计算机上使用您选择的标志和编译器版本即可确定它是否有效”）。 - user395760

2

如果您具有完全相同的对象集，并且可以保证使用相同的哈希函数，则是的，set.pop()以及list(set())可以是确定性的。 - Joel Cornett

Karl放在这个问题上的赏金是错的。他想要一个规范的答案。规范的答案已经给出：在使用set.pop()时假设非确定性。如果你想知道从集合中删除元素的确定性方法，那么请提出另一个问题。这个问题已经有答案了。 - Mike Williamson

5个回答

6

在内部，我认为情况类似于dict。顺序由哈希算法确定，在某些情况下，将产生相同的结果。但是您不应该依赖于此，因为一旦元素数量变大，集合将遇到冲突（即它的内部哈希），这最终会导致不同的排序。

简而言之：不，set.pop()不是确定性的。不要假设任何顺序，因为API明确说明：

一个集合对象是一个无序的集合

- miku

4

文档没有指定必须是确定的，因此您应该假设它不是。

- Ignacio Vazquez-Abrams

4

考虑到这个问题似乎是关于特定版本的，没有必要做任何假设——可以检查源代码并测试其行为。 - Marcin

2

如果您想强制确定性，可以尝试类似以下的方法：

value = min(my_set)
my_set.remove(value)

- Karl Knechtel

2

请注意，只有在min()函数没有歧义的情况下，才能确定此内容。可能存在一个奇怪的集合，其中有不同的值，其中有两个或更多个值都小于所有其他值（并且这两个值都小于另一个值）。这种情况在实际应用中不常见，但是确实可能存在。 - ch3ka

3

更好的例子是一些无法排序但仅能进行相等比较的值。定义 __lt__ 使得 x < y 和 y < x 同时成立，虽然是合法的写法，但实际上是错误的。 - Karl Knechtel

3

当集合无法排序时（例如，一个包含复数的集合），您的解决方案将因为TypeError而失败。但是请考虑以下代码：class epsilon(float): def __lt__(self, other): return True if 0 < other - ch3ka

-1

如果你真的是针对特定版本的Python，那么你可以查看源代码，并测试其行为（但要进行充分的测试-考虑负载因素等）。

如果您想要可移植性，或者发现set的执行不符合要求，请使用有序字典（这里有一个：http://code.activestate.com/recipes/576693/；还有很多其他的，找到一个你喜欢的），并将其适应为一个集合。

更新：这里有一个有序集合：http://packages.python.org/Brownie/api/datastructures.html#brownie.datastructures.OrderedSet

- Marcin

OrderedDict 在 2.7 和 3.1+ 的标准库中（http://docs.python.org/library/collections.html#collections.OrderedDict，http://docs.python.org/dev/library/collections.html#collections.OrderedDict）。 - miku

@miku 鉴于它是用C实现的，正如你回复的同一句话所指定的那样，它无法被便携地适应。 - Marcin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- alexis · Accepted Answer

一般来说，不行。@Christophe和@Marcin所指向的Python源代码显示，元素会按照哈希表中出现的顺序被弹出。因此，弹出的顺序（可能也是迭代顺序）是确定性的，但仅适用于固定的哈希值。这适用于数字，但根据__hash__文档中的Note，对于字符串则不是这样，顺带一提直接涉及到了你的问题：

请注意，默认情况下，str、bytes 和 datetime 对象的 hash() 值会“撒盐”，并加上一个不可预测的随机值。虽然在单个 Python 进程内它们保持不变，但在重复调用 Python 时它们是不可预测的。

[...]

更改哈希值会影响字典、集合和其他映射的迭代顺序。Python从来没有对此排序作出过任何保证（通常在32位和64位版本之间有所不同）。

编辑：正如@Marcin所指出的，我引用的链接不适用于Python 2。哈希随机化成为Python 3.3的默认设置。 Python 2.7默认情况下没有不确定性的字符串哈希。

一般来说，对于任何哈希值不是其值的可重复函数的对象（例如，如果哈希基于内存地址），这都是一个问题。但相反地，如果为集合中的对象定义自己的__hash__方法，则可以期望它们以可重复的顺序返回。（前提是集合的历史和平台保持不变）。