resueltos - La complejidad del tiempo de acceso a un dict de Python

determinar la complejidad de un algoritmo online

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 aunque el algoritmo es cuadrático.
Yo uso un diccionario para memorizar valores. Eso parece ser un cuello de botella.

Los valores con los que me hash son tuplas de puntos. Cada punto es: (x, y), 0 <= x, y <= 50
Cada clave del diccionario es: Una tupla de 2-5 puntos: ((x1, y1), (x2, y2), (x3, y3), (x4, y4))

Las claves se leen muchas veces más a menudo de lo que están escritas.

¿Estoy en lo cierto al afirmar que los dicts de python sufren tiempos de acceso lineal con tales entradas?

Por lo que sé, los conjuntos han garantizado los tiempos de acceso logarítmico.
¿Cómo puedo simular dicts usando conjuntos (o algo similar) en Python?

editar Según la solicitud, aquí hay una versión (simplificada) de la función de memoria:

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

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

Yo 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 2

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

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

Answer 3

No estás en lo correcto. Es improbable que el acceso dict sea ​​tu problema aquí. Es casi seguro que es O (1), a menos que tenga entradas muy extrañas o una función de hashing muy mala. Pegue un código de muestra de su aplicación para un mejor diagnóstico.

Answer 4

Para responder a sus preguntas específicas:

P1: "" "¿Estoy en lo correcto al decir que los dicts de python sufren tiempos de acceso lineal con tales entradas?"

A1: Si quiere decir que el tiempo promedio de búsqueda es O (N) donde N es el número de entradas en el dictado, entonces es muy probable que esté equivocado. Si está en lo correcto, a la comunidad de Python le gustaría mucho saber en qué circunstancias está en lo correcto, para que el problema pueda ser mitigado o al menos prevenido. 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 instrumentado con elementos como el número de elementos dict y el número de accesos dict para cada P donde P es el número de puntos en la clave (2 <= P <= 5)

P2: "" "Por lo que sé, los conjuntos han garantizado los tiempos de acceso logarítmico. ¿Cómo puedo simular los dictados utilizando conjuntos (o algo similar) en Python?" ""

A2: ¿Los conjuntos han garantizado los tiempos de acceso logarítmico en qué contexto? No hay tal garantía para las implementaciones de Python. De hecho, las versiones recientes de CPython utilizan una implementación de dictados reducidos (solo claves, sin valores), por lo que la expectativa es un comportamiento O (1) promedio. ¿Cómo puedes simular dictos con conjuntos o algo similar en cualquier idioma? Respuesta corta: con extrema dificultad, si desea alguna funcionalidad más allá de dict.has_key(key) .

Answer 5

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

Es poco probable que el acceso al diccionario sea un problema, ya que la operación es O (1) en promedio y O (N) se amortiza en el peor de los casos . Es posible que las funciones de hashing incorporadas experimenten colisiones para sus datos. Si tiene problemas con la función hash incorporada, puede proporcionar la suya propia.

La implementación del diccionario de Python reduce la complejidad promedio de las búsquedas de diccionario a O (1) al requerir que los objetos clave proporcionen una función "hash". Dicha función de hash toma la información de un objeto clave y la utiliza para producir un entero, llamado valor de hash. Este valor hash se usa para determinar en qué "grupo" se debe colocar este par (clave, valor).

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

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

Dependiendo de la apariencia de sus datos, es posible que tenga una función hash más rápida que tenga menos colisiones que la función estándar. Sin embargo, esto es poco probable. Consulte la página de Python Wiki en Teclas de diccionario para obtener más información.

Answer 6

Ver la complejidad del tiempo . El dict de python es un hashmap, su peor caso es, por lo tanto, O (n) si la función hash es mala y da lugar a muchas colisiones. Sin embargo, ese 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 importante de Python sería extremadamente improbable. La complejidad media del tiempo es, por supuesto, O (1).

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

Después de una comprobación rápida, todavía no he logrado encontrar dos tuplas que tengan 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 por 24 horas)