Curiosidad sobre __hash__()

[Chema Cortes]

El Monday 09 February 2009 17:06:44 Francesc Alted escribió:

> Ya veo.  Sin embargo, no entiendo porqué se dice que dividiendo por 8 la
> distribución de hashes es más homegénea (dividir por una constante no
> veo que afecte a la distribución de una función).

Tienes toda la razón. Más que homogénea debería haber dicho más "compacta", ya 
que los hashes se concentrarían todos en un rango del dominio.


> Y lo de evitar las 
> colisiones, tampoco lo veo claro, ya que al dividir id() por una
> cantidad fija lo máximo que puedes conseguir es hacer que aumenten
> (aunque si es verdad que todas la direcciones de memoria son múltiplos
> de 8, en ese caso la división por esa cantidad no afectaría al número
> de colisiones).

También tienes aquí razón. Las colisiones van a ser las mismas. Tal vez se 
debería pensar en algún algoritmo mejor para distribuir los hashes por todo 
el dominio.


> De hecho, mis experimentos me dicen que parece que no hay mejora
> aparente con la división por 8:

Yo también he hecho mis experimentos. Se supone que el hash es para mejorar la 
velocidad de accesos arbitrarios, así que mi experimento intenta incorporar 
algo de aleatoriedad. Para recorrer secuencialmente todo el diccionario, como 
haces en tu código, tal vez no se aprecie ninguna mejora.


In [7]: from random import choice

In [8]: class A(object):
   ...:         def __hash__(self):  #__hash__ compacto
   ...:                 return id(self) >> 3
   ...:

In [9]: class B(object):  
   ....:     def __hash__(self):  #__hash__ como entero largo sin signo
   ....:         return id(self)
   ....:
   ....:

In [10]: class C(object):  #__hash__ por defecto (entero 32bit con signo)
   ...:          pass
   ...:

In [11]: N = 1000000

In [12]: dA = dict((A(),i) for i in xrange(N))

In [13]: dB = dict((B(),i) for i in xrange(N))

In [14]: dC = dict((C(),i) for i in xrange(N))

In [15]: %time l = [dA[choice(dA.keys())] for i in xrange(1000)]
CPU times: user 122.01 s, sys: 6.07 s, total: 128.08 s
Wall time: 134.27 s

In [16]: %time l = [dB[choice(dB.keys())] for i in xrange(1000)]
CPU times: user 151.80 s, sys: 5.85 s, total: 157.65 s
Wall time: 171.92 s

In [17]: %time l = [dC[choice(dC.keys())] for i in xrange(1000)]
CPU times: user 150.35 s, sys: 5.20 s, total: 155.55 s
Wall time: 160.03 s


En el bugs.python.org se hablaba de ganancias del 10%. Yo estoy consiguiendo 
del orden del 18% (y sin optimizar en C).

> O sea, que de manera consistente, la hash sin dividir parece que saca
> más rendimiento (un 15%) que la dividida por 8.  No sé, lo mismo el
> rendimiento depende de la plataforma (o no he hecho bien los cálculos).

Estoy convencido que la plataforma tiene bastante influencia. He probado con 
tu mismo código (corrigiendo el primer caso con >>3 , y añadiendo el caso del 
__hash__ por defecto) y los tiempos que me salen son, respectivamente, 2.081, 
2.302 y 1.20. Me sale a la inversa que a tí.

PD: Pruebas hechas en un AMD Sempron 3000+, 64/32bits



PD2 [OT]: Por coincidencias de la vida, estaba leyendo estos días un artículo 
del "Communications of ACM" de enero del 2009 titulado "The Long Road To 64 
Bits", donde se repasa la lenta y compleja transición que ha sufrido el 
tamaño del direccionamiento de los procesadores. ¡Cuánta historia 
olvidada...! <http://mags.acm.org/communications/200901/?pg=46>
------------ próxima parte ------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part.
URL: <http://mail.python.org/pipermail/python-es/attachments/20090210/042d02d2/attachment.pgp>
------------ próxima parte ------------
_______________________________________________
Lista de correo Python-es 
http://listas.aditel.org/listinfo/python-es
FAQ: http://listas.aditel.org/faqpyes