colisiones recuento en un diccionario de Python

Question

mi primera vez publicar aquí, así que espero haber hecho mi pregunta en el tipo derecho de paso,

Después de añadir un elemento a un diccionario de Python, es posible conseguir a Python ¿Te dicen si agregar ese elemento causó una colisión? (¿Y cuántas ubicaciones exploró la estrategia de resolución de colisiones antes de encontrar un lugar para colocar el elemento?)

Mi problema es: estoy usando diccionarios como parte de un proyecto más grande, y después de un perfil extenso, descubrí que el más lento parte del código trata con una matriz de distancia dispersa implementada usando diccionarios.

Las claves que estoy usando son ID de objetos de Python, que son enteros únicos, por lo que sé que todos los hash a diferentes valores. Pero ponerlos en un diccionario aún podría causar colisiones en principio. No creo que las colisiones en el diccionario sean lo que ralentiza mi programa, pero quiero eliminarlas de mis consultas.

Así, por ejemplo, dada la siguiente diccionario:

d = {} 
for i in xrange(15000): 
    d[random.randint(15000000, 18000000)] = 0 

puede usted conseguir Python que le diga cuántas colisiones que sucedió cuando se crea?

Mi código real está enredado con la aplicación, pero el código anterior hace un diccionario que se ve muy similar a los que estoy usando.

Repetir: no creo que las colisiones sean lo que está ralentizando mi código, solo quiero eliminar la posibilidad al mostrar que mis diccionarios no tienen muchas colisiones.

Gracias por su ayuda.

Editar: Algunos código para implementar la solución de @Winston Ewert:

n = 1500 
global collision_count 
collision_count = 0 

class Foo(): 

    def __eq__(self, other): 
     global collision_count 
     collision_count += 1 
     return id(self) == id(other) 

    def __hash__(self): 
     #return id(self) # @John Machin: yes, I know! 
     return 1 

objects = [Foo() for i in xrange(n)] 

d = {} 
for o in objects: 
    d[o] = 1 

print collision_count 

Tenga en cuenta que cuando se define __eq__ en una clase, Python le da una TypeError: unhashable instance si no también define una función __hash__.

No funciona como esperaba. Si tiene la función __hash__return 1, entonces se producen muchas colisiones, como se esperaba (1125560 colisiones para n = 1500 en mi sistema). Pero con return id(self), hay 0 colisiones.

¿Alguien sabe por qué esto dice 0 colisiones?

Editar: Pude haber descubierto esto.

¿Es porque __eq__ solo se llama si los valores de dos objetos son los mismos, no su "versión crujiente" (como dijo @John Machin)?

Answer 1

Respuesta corta:

No se puede simular el uso de identificadores de los objetos como claves de diccionario mediante el uso de números enteros aleatorios como claves dict. Tienen diferentes funciones hash.

Suceden las colisiones. "Tener cosas únicas significa que no hay colisiones" es incorrecto para varios valores de "cosa".

No debe preocuparse por las colisiones.

Respuesta larga:

Algunas explicaciones, derivados de reading the source code:

A dict se implementa como una tabla de 2 ** entradas i, donde i es un entero.

Los dicts no tienen más de 2/3 de capacidad. En consecuencia, para las teclas 15000, debo ser de 15 a 2 ** i es 32768.

cuando o es una instancia de una clase arbitraria que no define __hash__(), No es cierto que la almohadilla (o) == ID (o). Como es probable que la dirección tenga ceros en los 3 o 4 bits de orden inferior, el hash se construye girando la dirección en 4 bits; ver la source file Objects/object.c, la función _Py_HashPointer

Sería un problema si había un montón de ceros en los bits de orden bajo, porque para acceder a una tabla de tamaño 2 ** i (por ejemplo 32768), el valor hash (a menudo mucho más grande que eso) debe crujirse para ajustarse, y esto se hace de manera muy simple y rápida tomando los bits de orden bajo i (por ejemplo, 15) del valor hash.

Consecuentemente colisiones son inevitables.

Sin embargo, esto no es motivo de pánico. Los bits restantes del valor hash se tienen en cuenta en el cálculo de dónde estará la próxima sonda. La probabilidad de que se necesite una 3ª sonda de etc. debería ser bastante pequeña, especialmente dado que la dict nunca está más de 2/3 llena. El costo de múltiples sondas se mitiga con el costo económico de calcular la ranura para la primera y posteriores sondas.

El siguiente código es un experimento simple que ilustra la mayor parte de la discusión anterior.Supone accesos aleatorios del dict después de que ha alcanzado su tamaño máximo. Con Python2.7.1, muestra alrededor de 2000 colisiones para 15000 objetos (13.3%).

En cualquier caso, la conclusión es que realmente debe desviar su atención a otra parte. Las colisiones no son su problema a menos que haya logrado alguna forma extremadamente anormal de obtener memoria para sus objetos. Debería ver cómo está usando los dictados, p. use k in d o intente/excepto, no d.has_key(k). Considere un dict al que se accede como d[(x, y)] en lugar de dos niveles a los que se accede como d[x][y]. Si necesita ayuda con eso, haga una pregunta separada.

actualización después de probar en Python 2.6:

Rotación de la dirección no se introdujo hasta Python 2.7; ver this bug report para una discusión completa y puntos de referencia. Las conclusiones básicas son en mi humilde opinión aún válidas, y pueden ser aumentadas por "Actualizar si puedes".

>>> n = 15000 
>>> i = 0 
>>> while 2 ** i/1.5 < n: 
... i += 1 
... 
>>> print i, 2 ** i, int(2 ** i/1.5) 
15 32768 21845 
>>> probe_mask = 2 ** i - 1 
>>> print hex(probe_mask) 
0x7fff 
>>> class Foo(object): 
...  pass 
... 
>>> olist = [Foo() for j in xrange(n)] 
>>> hashes = [hash(o) for o in olist] 
>>> print len(set(hashes)) 
15000 
>>> probes = [h & probe_mask for h in hashes] 
>>> print len(set(probes)) 
12997 
>>> 

Answer 2

Si las llaves están garantizados a ser enteros únicos, y desde Python usa hash() en las teclas, entonces debería estar garantizada para no tener ningún colisiones.

Answer 3

Esta idea no funciona, consulte la discusión en la pregunta.

Un vistazo rápido a la implementación C de python muestra que el código para resolver colisiones no calcula ni almacena el número de colisiones.

Sin embargo, invocará PyObject_RichCompareBool en las claves para comprobar si coinciden. Esto significa que se invocará __eq__ en la tecla para cada colisión.

Así:

reemplazar sus llaves con objetos que definen __eq__ y incrementar un contador cuando se le llama. Esto será más lento debido a la sobrecarga involucrada en saltar a python para la comparación. Sin embargo, debería darle una idea de la cantidad de colisiones que están sucediendo.

Asegúrese de utilizar diferentes objetos como la clave, de lo contrario, python tomará un atajo porque un objeto siempre es igual a sí mismo. Además, asegúrese de que el hash de los objetos tenga el mismo valor que las claves originales.