¿Por qué el orden en diccionarios y conjuntos es arbitrario?

No entiendo cómo el bucle sobre un diccionario o conjunto en Python se realiza mediante un orden "arbitrario".

Quiero decir, es un lenguaje de programación por lo que todo en el lenguaje debe estar determinado al 100%, ¿correcto? Python debe tener algún tipo de algoritmo que decida qué parte del diccionario o conjunto se elige, la primera, la segunda, etc.

¿Qué me estoy perdiendo?

Mar 18 '13 21:03

Esto es más una respuesta al conjunto Python 3.41 A antes de que se cerrara como duplicado.

Los demás tienen razón: no te fíes del orden. Ni siquiera finjas que existe uno.

Dicho esto, hay una cosa en la que puedes confiar:

list(myset) == list(myset)

Es decir, el orden es estable .

Comprender por qué se percibe un orden requiere comprender algunas cosas:

• Que Python usa conjuntos de hash ,

• Cómo se almacena el conjunto de hash de CPython en la memoria y

• Cómo se procesan los números

Desde la parte superior:

Un conjunto de hash es un método para almacenar datos aleatorios con tiempos de búsqueda realmente rápidos.

Tiene una matriz de respaldo:

# A C array; items may be NULL,
# a pointer to an object, or a
# special dummy object
_ _ 4 _ _ 2 _ _ 6

Ignoraremos el objeto ficticio especial, que existe sólo para hacer que las eliminaciones sean más fáciles de manejar, porque no eliminaremos de estos conjuntos.

Para realizar una búsqueda realmente rápida, se hace algo de magia para calcular un hash a partir de un objeto. La única regla es que dos objetos iguales tienen el mismo hash. (Pero si dos objetos tienen el mismo hash, pueden ser desiguales).

Luego creas un índice tomando el módulo por la longitud de la matriz:

hash(4) % len(storage) = index 2

Esto hace que el acceso a los elementos sea realmente rápido.

Los hashes son sólo la mayor parte de la historia, ya que hash(n) % len(storage)y hash(m) % len(storage)pueden dar como resultado el mismo número. En ese caso, varias estrategias diferentes pueden intentar resolver el conflicto. CPython utiliza "sondeo lineal" 9 veces antes de realizar un sondeo pseudoaleatorio, por lo que buscará a la derecha de la ranura hasta en 9 lugares antes de buscar en otra parte.

Los conjuntos de hash de CPython se almacenan así:

• Un conjunto de hash no puede estar lleno en más del 60 % ( nota: este factor de carga era anteriormente del 66 % y se redujo en Python 3.7). Si hay 20 elementos y la matriz de respaldo tiene 30 elementos de largo, el tamaño del almacén de respaldo cambiará para ser más grande. Esto se debe a que se producen colisiones con mayor frecuencia con tiendas de respaldo pequeñas y las colisiones ralentizan todo.

• When the backing store becomes too full, it will be automatically resized to increase the ratio of unused space (a higher ratio of unused space means it's faster to find a slot when handling a hash collision). For small sets, storage will be quadrupled in size, and for large sets (>50,000) it will be doubled in size (source).

So when you create an array the backing store is length 8. Once it is 4 full and you add an element, it will contain 5 elements. 5 > ³⁄₅·8 so this triggers a resize, and the backing store quadruples to size 32.

>>> import sys
>>> s = set()
>>> for i in range(10):
...     print(len(s), sys.getsizeof(s))
...     s.add(i)
... 
0 216
1 216
2 216
3 216
4 216
5 728
6 728
7 728
8 728
9 728

Finally, hash(n) just returns n for integers (except for hash(-1) which returns -2 because the value -1 is reserved for another usage).

So, let's look at the first one:

v_set = {88,11,1,33,21,3,7,55,37,8}

len(v_set) is 10, so the backing store is at least 15(+1) after all items have been added. The relevant power of 2 is 32. So the backing store is:

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

We have

hash(88) % 32 = 24
hash(11) % 32 = 11
hash(1)  % 32 = 1
hash(33) % 32 = 1
hash(21) % 32 = 21
hash(3)  % 32 = 3
hash(7)  % 32 = 7
hash(55) % 32 = 23
hash(37) % 32 = 5
hash(8)  % 32 = 8

so these insert as:

__  1 __  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __
   33 ← Can't also be where 1 is;
        either 1 or 33 has to move

So we would expect an order like

{[1 or 33], 3, 37, 7, 8, 11, 21, 55, 88}

with the 1 or 33 that isn't at the start somewhere else. This will use linear probing, so we will either have:

       ↓
__  1 33  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

or

       ↓
__ 33  1  3 __ 37 __  7  8 __ __ 11 __ __ __ __ __ __ __ __ __ 21 __ 55 88 __ __ __ __ __ __ __

You might expect the 33 to be the one that's displaced because the 1 was already there, but due to the resizing that happens as the set is being built, this isn't actually the case. Every time the set gets rebuilt, the items already added are effectively reordered.

Now you can see why

{7,5,11,1,4,13,55,12,2,3,6,20,9,10}

might be in order. There are 14 elements, so the backing store is at least 21+1, which means 32:

__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __

1 to 13 hash in the first 13 slots. 20 goes in slot 20.

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ __ __ __ __ __ __ __ __ __

55 goes in slot hash(55) % 32 which is 23:

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ __ __ 20 __ __ 55 __ __ __ __ __ __ __ __

If we chose 50 instead, we'd expect

__  1  2  3  4  5  6  7  8  9 10 11 12 13 __ __ __ __ 50 __ 20 __ __ __ __ __ __ __ __ __ __ __

And lo and behold:

>>> {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 20, 50}
{1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 50, 20}

pop is implemented quite simply by the looks of things: it traverses the underlying array and pops the first element, skipping over unused slots and "dummy" entries (tombstone markers from removed elements).

This is all implementation detail.

Sep 29 '2014 12:09 Veedrac