Curiosidad sobre __hash__()

[Francesc Alted]

A Tuesday 10 February 2009, Jesus Cea escrigué:
> 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.

Si, tiene sentido.

> 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.

Correcto.  En creación de diccionarios yo incluso llego a ver mejoras de 
hasta un 20% (ver mensaje mío anterior), lo cual es muy significativo, 
en efecto.

>
> 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".

Ya, esto ya lo corregí en mis últimos experimentos.

-- 
Francesc Alted
------------ próxima parte ------------
_______________________________________________
Lista de correo Python-es 
http://listas.aditel.org/listinfo/python-es
FAQ: http://listas.aditel.org/faqpyes