En python, ¿es set.pop() determinista?

Question

Entiendo que los elementos de un conjunto de pitones no están ordenados. Llamar al método pop devuelve un elemento arbitrario; Estoy bien con eso.

Lo que me pregunto es si pop devolverá SIEMPRE el mismo elemento cuando el conjunto tenga el mismo historial. Dentro de una versión de python, por supuesto, no me importa si las diferentes versiones/implementaciones de python hacen lo suyo. En particular, estoy preguntando sobre Python 2.7. Es una cuestión de implementación más que de api en este caso.

Uso mucho los conjuntos en un generador de mazmorra de procedimiento para un juego, y me gustaría que el resultado sea determinista para una semilla determinada.

Answer 1

La respuesta en general es no. La fuente python que @Christophe y @Marcin (un) señalan útilmente muestra que los elementos aparecen en el orden en que aparecen en la tabla hash. Por lo tanto, orden pop (y presumiblemente orden de iteración) es determinista, pero solo para valores de hash fijos. Ese es el caso de los números, pero no para cuerdas, de acuerdo con el Nota en la documentación de __hash__, que por cierto también se refiere a su pregunta directamente:

Nota por defecto el de hash() los valores de los objetos str, bytes y datetime están "salados" con un valor aleatorio impredecible. Aunque permanecen constantes dentro de un proceso de Python individual, no son predecibles entre invocaciones repetidas de Python.

[...]

Cambio de valores hash afecta al orden de iteración de dicts, juegos y otras asignaciones. Python nunca ha hecho garantías sobre este orden (y generalmente varía entre compilaciones de 32 bits y de 64 bits).

Editar: Como @Marcin señala, el enlace que he citado no se aplica a Python 2. Hash aleatorización became the default with Python 3.3. Python 2.7 no tiene cadena hash intencionadamente no determinista por defecto.

En general, este es un problema para cualquier objeto cuyo hash no es una función repetible de su valor (por ejemplo, si el hash se basa en la dirección de memoria). Pero a la inversa, si define su propio método __hash__ para los objetos en sus conjuntos, puede esperar que se devuelvan en un orden reproducible. (Siempre que el historial y la plataforma del conjunto se mantengan fijos).

Answer 2

The documentation no especifica que debe ser determinista, por lo tanto, debe suponer que no lo es.

Answer 3

Internamente, creo que la situación es similar a dict. El orden está determinado por un algoritmo hash, que en algunas situaciones arrojarán los mismos resultados. Pero no deberías depender de eso, ya que una vez que la cantidad de elementos aumenta, el conjunto se encontrará con colisiones (es decir, hashing interno), lo que finalmente conducirá a un orden diferente.

En resumen: No, set.pop() no es determinista. No asuma cualquier orden, ya que la API establece explícitamente, que

un objeto de conjunto es una colección desordenada

• Docs: http://docs.python.org/library/stdtypes.html#set-types-set-frozenset
• Fuente: http://svn.python.org/view/python/trunk/Objects/setobject.c?view=markup

Answer 4

Si quiere forzar el determinismo, podría intentar algo como

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

Answer 5

Si realmente se dirigen a una versión particular de pitón, a continuación, se puede ver en la fuente, y poner a prueba su comportamiento (pero probar así - tener en cuenta los factores de carga y similares).

Si quieren portabilidad, o si se encuentra set no funcione como es necesario, utilice un ordereddict (aquí está uno: http://code.activestate.com/recipes/576693/; hay un montón de otros, por lo que encontrar uno que te gusta el aspecto de), y adaptarlo como una conjunto.

Actualización: aquí hay un conjunto ordenado: http://packages.python.org/Brownie/api/datastructures.html#brownie.datastructures.OrderedSet