Curiosidad sobre __hash__()

[Jesus Cea]

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

Francesc Alted wrote:
> Para ver los tiempos reales de búsqueda en el diccionario, he calculado 
> el tiempo que se usa en la 'infraestructura' (comando [15]) del 
> benchmark, que habría que restarlo de los anteriores.  Con esto, los 
> tiempos medios de búsqueda me salen:
> 
> Con hash compacto (id(self) >> 8) --> 610 ns
> Con hash normal (id(self) >> 0) --> 625 ns
> Con hash implementada en C (defecto) --> 320 ns

Veamos, si hay colisiones, el tiempo de búsqueda no se incrementa
notablemente. Supongamos un ejemplo: supongamos que tenemos un millón de
registros, y el array hash es de 2 millones. Según la distribución del
hash, tendremos más o menos colisiones.

Si no hay ninguna colisión, a la hora de realizar una búsqueda,
calculamos el hash y vamos directamente al sitio. Si hay colisiones poco
frecuentes con cadenas de, digamos, longitud 2, el coste añadido es muy
bajo; simplemente en vez de hacer una comparación, hacemos dos.

El problema es a la hora de añadir elementos porque, por ejemplo, si
python detecta que hay muchas colisiones, amplia el tamaño del array
hash, lo que hace que ocupe más memoria y tenga peor comportamiento de
caché. En particular, cuando añadimos millones de elementos, el array
hash debe crecer varias veces para acomodar nuevos registros, copiando
los valores viejos, etc. Minimizar esta operación supone un ahorro de
tiempo y memoria. Tener un "hash" mejor distribuido ayuda a ello.

Yo sí veo mejoras significativas, del orden del 6% a pesar de estar
cronometrando cosas como el propio bucle, etc. Teniendo en cuenta que
esta ganancia supone tocar una sola linea de código en el intérprete, me
parece que merece ser considerada.

Por otro lado, si haces ">>8", te aseguro que vas a tener colisiones;
estás dividiendo por 256 (varios objetos consecutivos tendrán el mismo
hash), no por 8. Para dividir por 8, haz ">>3".

- --
Jesus Cea Avion                         _/_/      _/_/_/        _/_/_/
jcea en jcea.es - http://www.jcea.es/     _/_/    _/_/  _/_/    _/_/  _/_/
jabber / xmpp:jcea en jabber.org         _/_/    _/_/          _/_/_/_/_/
.                              _/_/  _/_/    _/_/          _/_/  _/_/
"Things are not so easy"      _/_/  _/_/    _/_/  _/_/    _/_/  _/_/
"My name is Dump, Core Dump"   _/_/_/        _/_/_/      _/_/  _/_/
"El amor es poner tu felicidad en la felicidad de otro" - Leibniz
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.8 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQCVAwUBSZHYO5lgi5GaxT1NAQJBlAQAizDAk5IHGBmmUqDSXnJAj7X02i/5BktU
4P2Mu/5MLEAss2LKhFGgzrBNKsD+YC2s93Qesfw3K4mxFfWoOqa9R8MjQvU+Kd4E
RYTkw7hUjhZQhZjUsq3midpCORvxyG4sgdqPm4tlBMQG4C+rTbzWeFdy6rhJzpb1
oNAX0TmEwLw=
=h+Qt
-----END PGP SIGNATURE-----
------------ próxima parte ------------
_______________________________________________
Lista de correo Python-es 
http://listas.aditel.org/listinfo/python-es
FAQ: http://listas.aditel.org/faqpyes