Curiosidad sobre __hash__()

[lasizoillo]

El día 9 de febrero de 2009 17:06, Francesc Alted
<faltet en pytables.org> escribió:
> A Monday 09 February 2009, Chema Cortes escrigué:
>> El 2009/2/6 Chema Cortes <pych3m4 en gmail.com> escribió:
>> > Pues me temo que ya está reportado:
>> >  http://bugs.python.org/issue5169
>> >
>> > De todos modos, si Jesús Cea puede echarle un vistazo y ve que no
>> > se puede hacer nada, lo cerramos. Yo también intentaré revisarlo.
>>
>> Por si no habéis seguido el bug, finalmente ha quedado "invalidado"
>> (no fue considerado trascendente).
>>
>> Técnicamente: La función id() devuelve la dirección de memoria del
>> objeto como un "entero largo sin signo" ("uintptr_t", en terminología
>> C). La función hash devuelve, por defecto, este id() como un "entero
>> largo *con* signo", con lo que direcciones de memoria por encima de
>> los 2GB darán hashes negativos, en cuyo caso deja de ser válida la
>> identidad id(a)==hash(a).
>>
>> Lo interesante de la cuestión es que se ha sugerido otra manera de
>> calcula el hash. El direccionamiento de memoria se ajusta a
>> direcciones múltiplo del tamaño del bus de direcciones (en 64/32bit
>> todas las direcciones de memoria son múltiplo de 8), lo que hace que
>> la función hash se esté limitando a la octava parte de los valores
>> posibles con 32 bits. Se ha sugerido que hash devuelva la dirección
>> de memoria divido por 8 (hash(a)==id(a)>>3), con lo que la
>> distribución de hashes sería más homogénea y evitaría mejor las
>> colisiones (con una mejora de velocidad en el acceso a diccionarios
>> significativa).
>
> 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).  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).
>
> De hecho, mis experimentos me dicen que parece que no hay mejora
> aparente con la división por 8:
>
> In [49]: class A(object):
>     def __hash__(self):
>        return id(self) >> 8

Debería ser >> 3

>
> In [52]: class B(object):
>     def __hash__(self):
>        return id(self)
>

Si le pones " >> 0 " compruebas una misma implementación y compruebas
el tema de las colisiones.

Tampoco vas a ver gran diferencia entre uno y otro.

> In [67]: N = 1000000  # pruebas con diccionarios de 1 millón de entradas
>
> In [68]: dA = dict((A(),i) for i in xrange(N))
>
> In [69]: dB = dict((B(),i) for i in xrange(N))
>
> In [70]: t1 = time(); l = [dA[i] for i in dA.iterkeys()]; print
> round(time()-t1, 3)
> 0.847
>
> In [71]: t1 = time(); l = [dB[i] for i in dB.iterkeys()]; print
> round(time()-t1, 3)
> 0.721
>
> In [72]: t1 = time(); l = [dA[i] for i in dA.iterkeys()]; print
> round(time()-t1, 3)
> 0.828
>
> In [73]: t1 = time(); l = [dB[i] for i in dB.iterkeys()]; print
> round(time()-t1, 3)
> 0.72
>
> 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).
>

Despues de hacer las correcciones propuestas (a parte de repetir
varias veces el test) no veo nada apreciable empiricamente tampoco :-(

> Saludos,
>
> --
> Francesc Alted
> _______________________________________________
> Lista de correo Python-es
> http://listas.aditel.org/listinfo/python-es
> FAQ: http://listas.aditel.org/faqpyes
>
_______________________________________________
Lista de correo Python-es 
http://listas.aditel.org/listinfo/python-es
FAQ: http://listas.aditel.org/faqpyes