Complejidad del tiempo para acceder a un dict de Python

Question

Estoy escribiendo un programa simple de Python.

Mi programa parece sufrir de acceso lineal a los diccionarios, su tiempo de ejecución crece exponencialmente a pesar de que el algoritmo es cuadrática.
Uso un diccionario para memorizar valores. Eso parece ser un cuello de botella.

Los valores que estoy mezclando son tuplas de puntos. Cada punto es: (x, y), 0 < = x, y < = 50
Cada tecla en el diccionario es: Una tupla de 2-5 puntos: ((x1, y1), (x2, y2), (x3, y3), (x4, y4))

Las teclas se leen muchas más veces de las que se escriben.

¿Es correcto que los dictados python sufran tiempos de acceso lineal con tales entradas?

Por lo que yo sé, los conjuntos tienen tiempos de acceso logarítmicos garantizados.
¿Cómo puedo simular dictados utilizando conjuntos (o algo similar) en Python?

editar Según la petición, he aquí una (simplificado) versión de la función memoization:

def memoize(fun): 
    memoized = {} 
    def memo(*args): 
     key = args 
     if not key in memoized: 
      memoized[key] = fun(*args) 
     return memoized[key] 
    return memo 

Answer 1

Ver Time Complexity. El dict python es un hashmap, su peor caso es por lo tanto O (n) si la función hash es mala y resulta en muchas colisiones. Sin embargo, es un caso muy raro en el que cada elemento agregado tiene el mismo hash y, por lo tanto, se agrega a la misma cadena, lo que para una implementación de Python importante sería extremadamente poco probable. La complejidad promedio del tiempo es, por supuesto, O (1).

El mejor método sería verificar y echar un vistazo a los hashs de los objetos que está utilizando. El CPython Dict usa int PyObject_Hash (PyObject *o) que es el equivalente a hash(o).

Después de una comprobación rápida, que aún no han logrado encontrar dos tuplas que hash para el mismo valor, lo que indicaría que la búsqueda es O (1)

l = [] 
for x in range(0, 50): 
    for y in range(0, 50): 
     if hash((x,y)) in l: 
      print "Fail: ", (x,y) 
     l.append(hash((x,y))) 
print "Test Finished" 

CodePad (disponible durante 24 horas)

Answer 2

Usted no es correcta. dict es probable que tu problema no sea tu problema aquí. Es casi seguro que O (1), a menos que tenga algunas entradas muy extrañas o una función de hash muy mala. Pegue un código de muestra de su aplicación para un mejor diagnóstico.

Answer 3

Sería más fácil hacer sugerencias si proporcionó código de ejemplo y datos.

Es poco probable que el acceso al diccionario sea un problema, ya que esa operación es O(1) on average, and O(N) amortized worst case. Es posible que las funciones hash incorporadas estén experimentando colisiones para sus datos. Si tiene problemas con la función hash incorporada, puede proporcionar la suya.

de Python aplicación diccionario reduce la complejidad media de búsquedas de diccionario a O (1) por que requiere que los objetos proporcionan una función clave "control".Dicha función hash toma la información en un objeto clave y la utiliza para generar un número entero, llamado valor hash. Este valor hash se usa para determinar en qué "cubo" se debe colocar este par (clave, valor) .

Puede sobrescribir el método __hash__ en su clase para implementar una función hash personalizado como este:

def __hash__(self):  
    return hash(str(self)) 

Dependiendo de cuáles son sus datos en realidad se parece, usted podría ser capaz de llegar a una más rápida función hash que tiene menos colisiones que la función estándar. Sin embargo, esto es poco probable. Consulte Python Wiki page on Dictionary Keys para obtener más información.

Answer 4

Como han señalado otros, acceder a los dictados en Python es rápido. Probablemente sean la estructura de datos mejor engrasada en el lenguaje, dado su papel central. El problema está en otra parte.

¿Cuántas tuplas estás recordando? ¿Has considerado la huella de memoria? Quizás esté gastando todo su tiempo en el asignador de memoria o memoria de paginación.

Answer 5

Mi programa parece sufrir de acceso lineal a diccionarios, su tiempo de ejecución crece exponencialmente aunque el algoritmo sea cuadrático.

Uso un diccionario para memorizar valores. Eso parece ser un cuello de botella.

Esto es evidencia de un error en su método de memorización.

Answer 6

para responder a sus preguntas específicas:

P1: "" "Estoy en lo correcto que predice pitón sufren de tiempos de acceso lineales con dichas entradas?" ""

A1: Si se refiere a que el tiempo promedio de búsqueda es O (N) donde N es el número de entradas en el dict, entonces es muy probable que estés equivocado. Si está en lo cierto, a la comunidad de Python le gustaría saber bajo qué circunstancias está en lo cierto, para que el problema pueda mitigarse o al menos advertirse. Ni el código de "muestra" ni el código "simplificado" son útiles. Por favor, muestre el código real y los datos que reproducen el problema. El código debe estar equipada con cosas como número de elementos dict y el número de dict accesos para cada P donde P es el número de puntos en la llave (2 < = P < = 5)

Q2: "" "Por lo como sé, los conjuntos tienen tiempos de acceso logarítmicos garantizados. ¿Cómo puedo simular dictados usando conjuntos (o algo similar) en Python? "" "

A2: ¿Los conjuntos tienen tiempos de acceso logarítmicos garantizados en qué contexto? No hay tal garantía para las implementaciones de Python. De hecho, las versiones recientes de CPython usan una implementación dict de reducción (solo claves, sin valores), por lo que la expectativa es un comportamiento promedio de O (1). ¿Cómo se puede simular dicts con sets o algo similar en cualquier idioma? Respuesta corta: con extrema dificultad, si desea cualquier funcionalidad más allá de dict.has_key(key).