[Python] Dubbi su hash e set

[Daniele Varrazzo]

Pietro Battiston ha scritto:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Ho un comando (o piuttosto il suo output) che minaccia la mia sanità
> mentale:
> 
> In [6]: [v for v in penta.v][0] in  penta.v
> Out[6]: False
> 
> , dove:
> 
> In [7]: type(penta.v)
> Out[7]: <type 'set'>
> 
> Chiedo se un elemento di un insieme sta nella lista degli elementi di
> quell'insieme e la risposta è "False"?!? Evidentemente c'è qualcosa di
> grosso che mi sfugge del tipo "set", ma cosa?!

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.

> (N.B: la funzione __hash__  di "vertex" l'ho ridefinita io)

Come hai definito l'hash? Questa è l'informazione più importante.

>     hash(object) -> integer
>    
>     Return a hash value for the object.  Two objects with the same
> value have
>     the same hash value.  The reverse is not necessarily true, but likely.
> 
> 
> "not necessarily true" non significa che dovrebbe alla fine fregarsene
> se in un insieme due elementi distinti (e peraltro identici in tutto
> tranne l'allocazione di memoria) hanno la stessa hash?!

Quante più collisioni ci sono, tanto più l'accesso alla mappa smetterà di 
essere o(1) e diventerà o(n). Se tutti gli oggetti hanno lo stesso hash, 
cercare in un dizionario che ha tali oggetti per chiave è come cercare per 
uguaglianza in una lista non ordinata.

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

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