tutorial - Claves del diccionario de Python. Complejidad "en"

the django project

Question

Pregunta rápida para satisfacer principalmente mi curiosidad sobre el tema.

Estoy escribiendo algunos grandes programas de python con un back-end de base de datos SQlite y trataré con una gran cantidad de registros en el futuro, así que necesito optimizar todo lo que pueda.

Para algunas funciones, estoy buscando claves en un diccionario. He estado utilizando la palabra clave "in" para creación de prototipos y estaba planeando volver atrás y optimizar esas búsquedas más tarde, ya que sé que la palabra clave "in" es generalmente O (n) (ya que esto se traduce a python iterando sobre una lista completa y comparando cada elemento). Pero, como un dict python es básicamente solo un mapa hash, el intérprete python es lo suficientemente inteligente como para interpretar:

if(key in dict.keys()):
...code...

a:

if(dict[key] != None):
...code...

Básicamente es la misma operación, pero la parte superior sería O (n) y la parte inferior sería O (1).

Para mí es fácil usar la versión inferior en mi código, pero luego sentí curiosidad y pensé que podría preguntar.

Answer 1

El operador in para dict tiene un promedio de tiempo-complejidad de O (1). Para obtener información detallada sobre la complejidad temporal de otros métodos dict (), visite este link .

Answer 2

En Python 2 dict.keys() crea primero la lista completa de claves, por eso es una operación O(N) , mientras que key in dict es una operación O(1) .

if(dict[key] != None) levantará KeyError si la clave no se encuentra en el dict, por lo que no es equivalente al primer código.

Python 2 resultados:

>>> dic = dict.fromkeys(range(10**5))
>>> %timeit 10000 in dic
1000000 loops, best of 3: 170 ns per loop
>>> %timeit 10000 in dic.keys()
100 loops, best of 3: 4.98 ms per loop
>>> %timeit 10000 in dic.iterkeys()
1000 loops, best of 3: 402 us per loop
>>> %timeit 10000 in dic.viewkeys()
1000000 loops, best of 3: 457 ns per loop

En Python 3 dict.keys() devuelve un objeto de vista que es bastante más rápido que las keys() de Python 2 keys() pero aún más lento, con la key in dict normal simple key in dict :

Python 3 resultados:

>>> dic = dict.fromkeys(range(10**5))
>>> %timeit 10000 in dic
1000000 loops, best of 3: 295 ns per loop
>>> %timeit 10000 in dic.keys()
1000000 loops, best of 3: 475 ns per loop

Use solo:

if key in dict:
#code

Answer 3

La forma correcta de hacerlo sería

if key in dict:
do stuff

el operador in es O (1) para diccionarios y conjuntos en python.

Answer 4

Primero, la key in d.keys() le garantiza el mismo valor que la key in d para cualquier dict d .

Y la operación en un dict , o el objeto dict_keys que recibe al llamar a keys() (en 3.x), no es O (N), es O (1).

No hay una verdadera "optimización" en marcha; es solo que usar el hash es la forma obvia de implementar __contains__ en una tabla hash, así como es la forma obvia de implementar __getitem__ .

Puede preguntar dónde está garantizado.

Bueno, no lo es. Mapping Types define dict como, básicamente, una implementación de la tabla hash de collections.abc.Mapping . No hay nada que impida que alguien cree una implementación de tabla hash de un Mapeo, pero que aún proporcione búsquedas O (N). Pero sería un trabajo extra realizar una implementación tan mala, ¿por qué lo harían?

Si realmente necesita demostrárselo a usted mismo, puede probar cada implementación que le interese (con un generador de perfiles, o utilizando algún tipo con __hash__ y __eq__ que registra llamadas, o ...), o lea la fuente.

En 2.x, no desea llamar a las keys , ya que eso genera una list de las claves, en lugar de un KeysView . Puede usar iterkeys , pero eso puede generar un iterador u otra cosa que no sea O (1). Entonces, solo usa el dict mismo como una secuencia.

Incluso en 3.x, no quiere llamar a las keys , porque no es necesario. Iterar un dict , verificar sus __contains__ , y en general tratarlo como una secuencia siempre es equivalente a hacer lo mismo con sus claves, entonces, ¿para qué molestarse? (Y, por supuesto, construir el KeyView trivial y acceder a él a través de él, agregará unos nanosegundos a su tiempo de ejecución y unas pocas teclas presionadas a su programa).

(No está del todo claro que el uso de operaciones de secuencia sea equivalente para d.keys() / d.iterkeys() d en 2.x. Además de los problemas de rendimiento, son equivalentes en cada implementación de CPython, Jython, IronPython y PyPy, pero no parece expresarse en ninguna parte de la forma en que está en 3.x. Y no importa, simplemente use la key in d .)

Mientras estamos en eso, tenga en cuenta que esto:

if(dict[key] != None):

... no va a funcionar. Si la key no está en el dict , esto aumentará KeyError , no devolverá None .

Además, nunca debe marcar None con == o != ; siempre uso is .

Puede hacer esto con un try -o, más simplemente, hacer if dict.get(key, None) is not None . Pero, de nuevo, no hay ninguna razón para hacerlo. Además, eso no manejará los casos donde None es un elemento perfectamente válido. Si ese es el caso, debe hacer algo como sentinel = object(); if dict.get(key, sentinel) is not sentinel: sentinel = object(); if dict.get(key, sentinel) is not sentinel:

Entonces, lo correcto para escribir es:

if key in d:

De manera más general, esto no es verdad:

Sé que la palabra clave "in" es generalmente O (n) (ya que esto simplemente se traduce a python iterando sobre una lista completa y comparando cada elemento

El operador in , como la mayoría de los otros operadores, es solo una llamada a un método __contains__ (o el equivalente para un __contains__ C / Java / .NET / RPython). list implementa iterando la lista y comparando cada elemento; dict implementa mezclando el valor y buscando el hash; blist.blist implementa al caminar un árbol B +; etc. Entonces, podría ser O (n), O (1), O (log n), o algo completamente diferente.