[Python] Dubbi su hash e set

[Daniele Varrazzo]

Pietro Battiston ha scritto:

> Daniele Varrazzo ha scritto:
>> Gli oggetti nel tuo insieme dovrebbero essere immutabili. Se cambi un
> oggetto,
>> e come conseguenza del cambiamento il suo hash cambia, hai
> tranqillamente una
>> situazione come quella indicata.
> 
> In effetti i miei oggetti non sono immutabili. Ma non capisco come
> questo primo elemento di penta.v potrebbe essere modificato dalla sola
> operazione di estrazione da un insieme che lo contiene. E se anche per
> assurdo fosse possibile, il seguente output:
> 
> In [12]: hash([v for v in penta.v][0])
> Out[12]: 0
> 
> In [14]: map(hash, penta.v)
> Out[14]: [0, 5, 8, 11, 14, 17, 22, 25, 28, 0]
> 
> 
> mi conferma che non c'è stato proprio nessun cambiamento, perlomeno
> nel valore di hash. Anche se mi rendo conto che se un cambiamento c'è,
> potrebbe essere avvenuto in entrambi i casi nel momento di iterare
> sull'insieme. Ma di nuovo: cosa potrebbe mai cambiare?!

Probabilmente il "primo" (quello corrispondente a list(penta)[0]) elemento 
dell'insieme è stato messo nell'insieme prima di essere cancellato (quando il 
suo hash era != 0). Non ho potuto controllare il codice perché la url di 
"poly.txt" che hai allegato in fondo al messaggio è rotta.

> new_ID() è un generatore che restituisce i numeri naturali in ordine.
> Quindi ogni istanza della classe ha un valore di hash diverso, tranne
> quelle su cui è stato chiamato "delete", che restituiscono 0.

Forse non ti è chiaro come funziona un dizionario e perchè i set (o le liste) 
non siano hashabili (un motivo c'è, non è un limite arbitrario!)

Un dict (un set è uguale, puoi vederlo come un dict in cui le chiavi e i 
valori sono uguali) è una struttura di dati divisa in "secchi" (bin). 
L'inserimento di un oggetto in un dict consiste in:

- scegliere il bin - e questo si fa leggendo l'hash della chiave.
- inserire l'oggetto nel bin (potrebbe non essere il solo: diciamo
   che ogni bin è una lista)

La ricerca di una chiave consiste invece in:

- scegliere il bin come sopra - estraendo l'hash della chiave
- cercare in tutti gli oggetti nel bin quello che ha la chiave uguale.
   Se lo trovi, hai trovato l'oggetto

Secondo me tu metti un oggetto nel set, poi ne chiami delete(). Riesci a 
vedere che succede? Lo stesso oggetto ha cambiato hash (si vede perché è 0: 
vuol dire che ne hai chiamato delete()), il che vuol dire che, inserito nel 
dict, sarebbe finito in un secchio diverso. Per questo la ricerca fallisce: 
quando testi "elemento in insieme" dove hash(elemento) == 0 ma hash(elemento) 
era != 0 quando ce l'avevi messo, cerchi probabilmente l'elemento nel bin 
sbagliato. E non lo trovi.

>> Già che ci sono: c'è un modo più semplice/furbo di:
>>
>> elemento = [v for v in insieme][0]
>> oppure:
>> elemento = insieme.pop(); insieme.add(elemento)
>>
>> per ottenere un qualsiasi elemento di un insieme dato tenendolo
>> nell'insieme?
> 
> Ad esempio iter(insieme).next()
> 
> Grazie mille... adesso almeno ho comando più semplice su cui impazzire:

LOL :)

Quello che fai con iter(insieme) (o gli altri modi diversi di iterare sul 
dict) non è una ricerca per chiave, ma una navigazione in tutto il contenuto, 
operazione che non consiste nella lettura dell'hash e che funziona anche nel 
tuo set, che è in uno stato inconsistente. Ma nel momento in cui usi 
l'operatore "in" stai facendo una ricerca per chave: se l'hash è cambiato, e 
con esso il bin, l'oggetto non viene trovato nel dict.

> Ma c'è di peggio:
> ...
> 
> Ovvero il solo atto di "poppare" un elemento e rimetterlo
> immediatamente nell'insieme cambia qualcosa ed elimina il mio problema!

Forse ora ti è chiaro perchè. pop() non usa le chiavi, ma tira fuori il primo 
che gli capita (come iter()). L'oggetto viene rimosso dal set. Quando fai 
add(), l'hash dell'oggetto viene ricalcolato e il bin viene aggiornato: il 
dict è tornato in stato consistente (ma può sempre tornare inconsistente!)

Insomma, se vuoi usare oggetti come chiavi, non c'è nessun'altra possibilità 
se non quella di avere chiavi immutabili. Per questo set e list non possono 
esserlo ma tuple si. Nota anche che esiste frozenset che è un insieme 
immutabile e pensato appositamente per essere hashabile.

La magia dell'accesso o(1) dei dict e dei set è condizionata dal fatto che 
deve essere possibile calcolare un hash sulle chiavi, e che questo hash sia 
immutabile. Nota che anche il "valore" delle chiavi (quello che tu usi per 
comparare con uguaglianza, quando dici o1 == o2) deve essere altrettanto 
immutabile. Altre proprietà delle chiavi possono cambiare, ma non quelle che 
usi per implementare __hash__() ed __eq__(). Se queste condizioni non si 
applicano ai tuoi oggetti, devi mettere gli oggetti in una lista ed 
accontentarti di una ricerca o(n) su di essi.

Ti sembra un limite arbitrario? diciamo che tu sei furbo, non conosci gli hash 
ma le tue chiavi sono ordinabili. Allora implementi una bella ricerca per 
bisezione su una lista ordinata. Perchè la ricerca funzioni deve valere la 
proprietà L[0] <= L[1] <=... L[n-1]. Puoi fare questa cosa con tutti gli 
oggetti che implementano __le__() e quello che ci guadagni è un invidiabile 
accesso o(log(n)). Ma c'è un'altro vincolo sottinteso: non ti deve essere 
possibile fare "f(L[i])" se f(o) cambia qualcosa all'oggetto o per cui la sua 
relazione di ordine cambia. Se lo fai, la proprietà di ordinamento che la 
ricerca per bisezione assume non è più valida, ed ovviamente darà risultati 
sbagliati. La tua ricerca continuerà a funzionare se invece fai

     o = L.pop(i)
     f(o)
     L.insert(o) # inserimento ordinato

perchè in questo caso l'oggetto viene spostato in una posizione consistente 
col suo nuovo valore.

Tutto chiaro?

-- 
Daniele Varrazzo - Develer S.r.l.
http://www.develer.com