[Python] Dubbi su hash e set

[Pietro Battiston]

Daniele Varrazzo ha scritto:
> 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.
>   

... ma ti garantisco che è in effetti era proprio come dici tu!


>> 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!)
>   

Mi ero risposto che se un set fosse stato hashabile avrebbe potuto
contenere anche se stesso, per cui le funzioni __hash__ e soprattutto
__repr__ ed __eq__ avrebbero avuto seri problemi. In realtà poi mi sono
accorto che forzando una funzione __hash__ stupida su liste e set,
l'interprete maneggia in modo egregio la ricorsività "infinita".

> Secondo me tu metti un oggetto nel set, poi ne chiami delete(). Riesci a 
> vedere che succede?

Sì. E il bello è che come funziona una hash table lo sapevo. Solo che mi
illudevo che questo meccanismo fosse un modo per fare una prima ricerca,
seguita, in caso di fallimento, da una eventuale ricerca in tempo O(n).
Cosa che invece - ma ci ho pensato solo a posteriori - non avrebbe senso
perché ogni "in" che restituisca False prenderebbe O(n) tempo.

>> 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è.

Già.

> 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!)
>   

... per giunta nel mio caso ci restava inconsistente, perché c'era un
altro elemento simile; però tanto bastava a darmi la risposta che mi
faceva felice...

> 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.
>   

In realtà poi al mio codice bastava una modifica minima: evitare che
"delete" azzeri self.ID: gli oggetti rimangono non immutabili ma il
valore di hash è dato dalla loro "parte immutabile".

> Tutto chiaro?
>   

Ora sì, grazie mille!

Pietro