clave python en dict.keys() rendimiento para diccionarios grandes

Question

Me preguntaba si ustedes podrían darme algunos consejos con respecto a mejorar el rendimiento de mi código.

Tengo un conjunto de bucles for que buscan ver si una clave está en un diccionario cuyos valores son una lista, si la clave existe, se agrega a la lista y si no agrega una nueva lista en para esa tecla

dict={} 
for value in value_list: 
    if value.key in dict.keys(): 
     temp_list = dict[value.key] 
     temp_list.append(value.val) 
     dict[value.key] = temp_list 
    else: 
     dict[value.key] = [value.val] 

Ahora bien, este código funciona bien, pero evenrually como el diccionario comienza a llenar el value.key línea en dict.keys() se vuelve más y más engorroso.

¿Hay una mejor manera de hacerlo?

Gracias,

Mike

Answer 1

No haga esto:

value.key in dict.keys() 

que - Python 2, en el le ast - crea una lista que contiene todas las claves. Eso se vuelve cada vez más caro a medida que el diccionario se hace más grande, y realiza una búsqueda O (n) en la lista para encontrar la clave, lo que frustra el propósito de usar un dict.

En cambio, sólo lo hacen:

value.key in dict 

que no crea una lista temporal, y hace una búsqueda en la tabla hash de la clave en lugar de una búsqueda lineal.

setdefault, como se menciona en otros lugares, es la forma más limpia de hacerlo, pero es muy importante entender lo anterior.

Answer 2

Uso collections.defaultdict, esto se puede simplificar a

d = collections.defaultdict(list) 
for value in value_list: 
    d[value.key].append(value.val) 

Answer 3

your_dict.setdefault(value.key, []).append(value.val) 

Answer 4

if value.key in dict.keys(): 

Es muy caro porque está convirtiendo a una lista de claves y luego buscando en la lista. Sólo la sustitución de eso con:

if value.key in dict: 

deberían acortar la búsqueda a ~ log N (EDIT: Estoy corregida por Glenn, probablemente incluso más rápido debido a los diccionarios de Python utilizan una tabla hash). Entonces simplemente:

dict[key].append(value.val) 

Debe acelerar un poco las cosas. No se requiere el uso de un temporizador temporal y solo consume algunos ciclos de CPU.

Si puede dar más detalles sobre lo que intenta hacer, es posible que alguien pueda sugerir un mejor algoritmo.

Answer 5

Paso 1: transformamos el código utilizando la temp_list en una sola expresión (supongo que temp_list no es necesario fuera de este código), mediante la adición de en lugar del método append. Además, no es necesario que use dict.keys() explícitamente, como otros mencionaron (y de hecho, desperdicia una gran cantidad de tiempo).

for value in value_list: 
    if value.key in dict: 
     dict[value.key] = dict[value.key] + [value.val] 
    else: 
     dict[value.key] = [value.val] 

Paso 2: Transformar la asignaciones-to-the-same-ubicación utilizando la sintaxis de la expresión condicional.

for value in value_list: 
    dict[value.key] = dict[value.key] + [value.val] if value.key in dict else [value.val] 

Paso 3: Al añadir o anteponiendo una lista vacía no tiene efecto sobre el valor de una lista, por lo que se puede insertar eso, y luego factorizar la 'adición' común del valor.

for value in value_list: 
    dict[value.key] = (dict[value.key] if value.key in dict else []) + [value.val] 

Paso 4: Reconocer que el dict ha incorporado en la funcionalidad para proporcionar un valor 'por defecto' cuando la llave está ausente:

for value in value_list: 
    dict[value.key] = dict.get(value.key, []) + [value.val] 

Paso 5: En lugar de obtener un valor, modificándolo y el establecimiento de nuevo, podemos utilizar .setdefault para darnos el contenido actual (o configurarlas si no está ya allí), y luego volver a utilizar .append para modificar la lista:

for value in value_list: 
    dict.setdefault(value.key, []).append(value.val) 

(Quiero decir ... podría haberlo mirado y pensado un poco y llegué a esto, pero ver cada paso lo deja más claro hacia dónde vamos ...)