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
_______________________________________________
Python mailing list
Python@lists.python.it
http://lists.python.it/mailman/listinfo/python
