-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
enrico franchi ha scritto:
> On Fri, May 2, 2008 at 8:46 PM, Pietro Battiston <[EMAIL PROTECTED]> wrote:
>
>> Ora, la mia coscienza sporca mi suggerisce che forse quando ho
>> sovrascritto __hash__ ho fatto più di quanto dovrebbe fare uno che di
>> internal Python non ne sa abbastanza, e che le hash di tutti gli
>> oggetti che conosco sono (solitamente) univoche. Ma...
>
> Non è questione di internals. E' questione di algoritmi. Devi definire
> una funzione (quasi) univoca sugli oggetti che a te interessano.
> La proprietà è che se hash(x) == hash(y) per te x e y devono essere
> uguali e che possibilmente se devono essere diversi non abbiano lo
> stesso hash (che vuole dire "è estremamente poco probabile che...").
OK, allora i miei scrupoli erano ingiustificati e stavo effettivamente
agendo "legalmente". Quindi?!
>> "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?!
>
> Dice chiaramente: due valori con lo stesso valore hanno anche lo stesso
hash,
> due valori con diverso hash potrebbero avere lo stesso valore (o anche
> no). E' frequente: per esempio se crei una classe "vuota" tutte le sue
> istanze avranno lo stesso hash (se la prova non mi inganna).
In realtà qualche osservazione empirica mi fa pensare che in caso di
__hash__ non definita, hash(x) = id(x). Comunque ho afferrato il concetto.
>> Qualcunque schiarimento è graditissimo, scusate la chilometricità
>> della mail.
>
> Io tutt'ora non ho capito quale sia il tuo problema.
Il mio problema è quello che avevo scritto all'inizio:
In [6]: [v for v in penta.v][0] in penta.v
Out[6]: False
Il primo elemento di penta.v è, evidentemente, in penta.v. Perché
risponde False?!?
Daniele, che ringrazio e di cui condenso la risposta in una sola email
per praticità di lettura, ha risposto:
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?!
>> (N.B: la funzione __hash__ di "vertex" l'ho ridefinita io)
>
> Come hai definito l'hash? Questa è l'informazione più importante.
Per com'è fatta, non chiarirebbe granché. Eccovi quindi tutta la
classe, tanto è piccolina:
class vertex(set):
valid = True
def __init__(self, *args):
set.__init__(self,*args)
self.ID = new_ID()
def __hash__(self):
return self.ID
def delete(self):
'''
Doesn't really delete a vertex: it
marks it as deletable.
'''
self.clear()
self.ID = 0
self.valid = False
def __repr__(self):
return "(vertex %d - edges %s)" % (self.ID,
list.__repr__([e.ID for e in self]))
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.
N.B: ho ridefinito __hash__ proprio perché "set objects are unhashable"
>
>> 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.
>
Lo immaginavo. Ma la performance in questo caso non mi preoccupa,
perché gli elementi con hash=0 (e quindi uguale tra di loro) nei miei
programmini sono pochi e hanno vita breve.
> 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:
In [8]: iter(penta.v).next() in penta.v
Out[8]: False
Eppure tutto il resto mi sembra chiaro; ad esempio (si veda In [9], In
[10], In [11b]):
In [11]: id([v for v in penta.v][0])
Out[11]: 11234192
In [12]: hash([v for v in penta.v][0])
Out[12]: 0
In [9]: oggetto = penta.v.pop()
In [10]: penta.v.add(oggetto)
In [11b]: oggetto in penta.v
Out[11b]: True
In [12]: id(oggetto)
Out[12]: 11234192
In [13]: hash(oggetto)
Out[13]: 0
ovvero "pop" mi ha restituito proprio l'elemento che appariva per
primo nell'iterazione. Solo che con pop non c'è nessuna (immagino)
iterazione. E il valore di hash rimane comunque lo stesso che vedevo
prima.
Ma c'è di peggio:
In [7]: [v for v in penta.v][0] in penta.v
Out[7]: False
In [8]: penta.v.add(penta.v.pop())
In [9]: for indice in range(len(penta.v)):
...: print ([v for v in penta.v][indice] in penta.v)
...:
...:
True
True
True
True
True
True
True
True
True
True
Ovvero il solo atto di "poppare" un elemento e rimetterlo
immediatamente nell'insieme cambia qualcosa ed elimina il mio problema!
Ogni schiarimento è sempre più gradito. Per chi non ha niente di
meglio da fare, il codice completo per testare il problema è qui:
http://poisson.phc.unipi.it/~battiston/poly.py
e la sequenza completa di comandi che uso per verificare il problema è
qui:
http://poisson.phc.unipi.it/~battiston/poly.txt
Intanto grazie.
Pietro
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
iD8DBQFIHWrfcZVtR82bmAYRAlPcAJ9s61pD66Es0s0+pI+p9c5H0NIsiwCg4Zex
vF+ZSdxYBnAgVqlxIvKeB+I=
=ipnQ
-----END PGP SIGNATURE-----
_______________________________________________
Python mailing list
Python@lists.python.it
http://lists.python.it/mailman/listinfo/python
