'ordine' di set Python non ordinati




python-internals (4)

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 .

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?


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.


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.


Una cosa fondamentale che è stata suggerita dalla grande risposta di mgilson , ma non è menzionata esplicitamente in nessuna delle risposte esistenti:

Piccolo hash di interi a se stessi:

>>> [hash(x) for x in (1, 2, 3, 88)]
[1, 2, 3, 88]

Stringhe di hash a valori imprevedibili. Infatti, dal 3.3 in poi, per impostazione predefinita, sono costruiti su un seed randomizzato all'avvio . Quindi, otterrai risultati diversi per ogni nuova sessione di interprete Python, ma:

>>> [hash(x) for x in 'abcz']
[6014072853767888837,
 8680706751544317651,
 -7529624133683586553,
 -1982255696180680242]

Quindi, considera l'implementazione della tabella hash più semplice possibile: solo un array di elementi N, dove l'inserimento di un valore significa metterlo in hash(value) % N (presupponendo nessuna collisione). E puoi fare una supposizione approssimativa su quanto sarà grande N sarà un po 'più grande del numero di elementi in esso contenuti. Quando si crea un set da una sequenza di 6 elementi, N potrebbe facilmente essere, per esempio, 8.

Cosa succede quando memorizzi quei 5 numeri con N = 8? Beh, hash(1) % 8 , hash(2) % 8 , ecc. Sono solo i numeri stessi, ma hash(88) % 8 è 0. Quindi, l'array della tabella hash finisce con 88, 1, 2, NULL, NULL, 5, NULL, 7 . Quindi dovrebbe essere facile capire perché iterare il set potrebbe darti 88, 1, 2, 5, 7 .

Ovviamente Python non garantisce che riceverai questo ordine ogni volta. Un piccolo cambiamento nel modo in cui indovina il valore corretto per N potrebbe significare che 88 finisce in qualcosa di diverso (o finisce per scontrarsi con uno degli altri valori). E, in effetti, eseguendo CPython 3.7 sul mio Mac, ottengo 1, 2, 5, 7, 88 0

Nel frattempo, quando costruisci un hash da una sequenza di dimensioni 11 e inserisci inserimenti casuali in esso, cosa succede? Anche assumendo l'implementazione più semplice e assumendo che non ci siano collisioni, non hai ancora idea di quale ordine otterrai. Sarà coerente all'interno di una singola esecuzione dell'interprete Python, ma diversa la prossima volta che lo avvierai. (A meno che non imposti PYTHONHASHSEED su 0 o su un altro valore int.) Che è esattamente ciò che vedi.

Ovviamente vale la pena guardare il modo in cui i set sono effettivamente implementati piuttosto che indovinare. Ma ciò che indovinerai in base all'assunzione della più semplice implementazione della tabella hash è (escludendo le collisioni e escludendo l'espansione della tabella hash) esattamente cosa succede.





python-internals