[Python] Dubbi su hash e set

Dom 4 Maggio 2008 09:50:57 CEST

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

enrico franchi ha scritto:
> On Fri, May 2, 2008 at 8:46 PM, Pietro Battiston <toobaz a email.it> 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-----