'ordine' di set Python non ordinati




python-internals (4)

Domanda da parte di un noob (me):

Capisco che gli insiemi in Python non siano ordinati, ma sono curioso riguardo all'ordine in cui sono visualizzati, in quanto sembra coerente. Sembrano essere fuori ordine allo stesso modo ogni volta:

>>> set_1 = set([5, 2, 7, 2, 1, 88])
>>> set_2 = set([5, 2, 7, 2, 1, 88])
>>> set_1
set([88, 1, 2, 5, 7])
>>> set_2
set([88, 1, 2, 5, 7])

... e un altro esempio:

>>> set_3 = set('abracadabra')
>>> set_4 = set('abracadabra')
>>> set_3
set(['a', 'r', 'b', 'c', 'd'])
>>>> set_4
set(['a', 'r', 'b', 'c', 'd'])

Sono solo curioso del perché questo sarebbe. Qualsiasi aiuto?


Dovresti guardare questo video (anche se è specifico per CPython 1 e sui dizionari - ma presumo che si applichi anche agli insiemi).

Fondamentalmente, Python blocca gli elementi e prende gli ultimi N bit (dove N è determinato dalla dimensione del set) e usa quei bit come indici di array per posizionare l'oggetto in memoria. Gli oggetti vengono quindi restituiti nell'ordine in cui esistono in memoria. Ovviamente, l'immagine diventa un po 'più complicata quando è necessario risolvere le collisioni tra gli hash, ma questo è il senso.

Si noti inoltre che l'ordine in cui vengono stampati è determinato dall'ordine in cui vengono inseriti (a causa di collisioni). Quindi, se riordini la lista che passi a set_2 , potresti ottenere un ordine diverso se ci sono set_2 chiavi.

Per esempio:

list1 = [8,16,24]
set(list1)        #set([8, 16, 24])
list2 = [24,16,8]
set(list2)        #set([24, 16, 8])

Nota il fatto che l'ordine è conservato in questi set è "coincidenza" e ha a che fare con la risoluzione delle collisioni (di cui non so nulla). Il punto è che gli ultimi 3 bit di hash(8) , hash(16) e hash(24) sono gli stessi. Poiché sono uguali, la risoluzione collisione prende il sopravvento e mette gli elementi in posizioni di memoria "di backup" invece della prima (migliore) scelta e quindi se 8 occupa una posizione o 16 è determinato da quale è arrivato prima alla festa e ha preso la "miglior posto".

Se ripetiamo l'esempio con 1 , 2 e 3 , otterrete un ordine coerente indipendentemente dall'ordine che hanno nella lista di input:

list1 = [1,2,3]
set(list1)      # set([1, 2, 3])
list2 = [3,2,1]
set(list2)      # set([1, 2, 3])

poiché gli ultimi 3 bit di hash(1) , hash(2) e hash(3) sono unici.

1 Nota L'implementazione qui descritta si applica a CPython dict e set . Penso che la descrizione generale sia valida per tutte le versioni moderne di CPython fino a 3.6. Tuttavia, a partire da CPython3.6, vi è un ulteriore dettaglio di implementazione che in realtà conserva l'ordine di inserimento per l'iterazione per dict . Sembra che il set non abbia ancora questa proprietà. La struttura dei dati è descritta da questo post sul blog da Pypy Folks (che ha iniziato a usarlo prima della gente di CPython). L'idea originale (almeno per l'ecosistema python) è archiviata sulla mailing list python-dev .


La ragione di questo comportamento è che Python usa le tabelle hash per l'implementazione del dizionario: https://en.wikipedia.org/wiki/Hash_table#Open_addressing

La posizione della chiave è definita dal suo indirizzo di memoria. Se sai che Python riutilizza la memoria per alcuni oggetti:

>>> a = 'Hello world'
>>> id(a)
140058096568768
>>> a = 'Hello world'
>>> id(a)
140058096568480

Puoi vedere quell'oggetto ha un indirizzo diverso ogni volta che è init.

Ma per i numeri interi piccoli non è cambiato:

>>> a = 1
>>> id(a)
40060856
>>> a = 1
>>> id(a)
40060856

Anche se creiamo il secondo oggetto con un nome diverso, sarebbe lo stesso:

>>> b = 1
>>> id(b)
40060856

Questo approccio consente di salvare la memoria che l'interprete Python consuma.


I set sono basati su una tabella hash. L'hash di un valore deve essere coerente, quindi l'ordine sarà anche - a meno che due elementi non siano associati allo stesso codice, nel qual caso l'ordine di inserimento cambierà l'ordine di output.


I set Python AFAIK sono implementati usando una tabella hash . L'ordine in cui appaiono gli oggetti dipende dalla funzione di hash utilizzata. All'interno della stessa esecuzione del programma, la funzione di hash probabilmente non cambia, quindi ottieni lo stesso ordine.

Ma non ci sono garanzie che userà sempre la stessa funzione, e l'ordine cambierà attraverso le esecuzioni - o all'interno della stessa esecuzione se si inseriscono molti elementi e la tabella hash deve essere ridimensionata.





python-internals