Estoy tratando de optimizar un bucle for anidado que compara un elemento en la matriz con el resto del elemento en la matriz .
Hay dos partes, la primera es, por ejemplo, una matriz tiene 3 elementos, y cada el elemento es un diccionario:
[{"someKey_1":"a"}, {"someKey_1":"b"}, {"somekey_1":"a"}] Primera iteración (el primer elemento se compara con el segundo elemento):
Clave de prueba de «someKey «para dos elementos, desde a != b, entonces no hacemos nada
2ª iteración (el 1er elemento se compara con el 3º elemento):
Prueba la clave de «someKey» para dos elementos, desde a == a, hacemos algo de lógica
El código (Sudo):
for idx, first_dictionary in enumerate(set_of_pk_values): for second_dictionary in (set_of_pk_values[idx+1:]): if (first_dictionary["someKey"] == second_dictionary["someKey"]): #Some Logic La parte #Some Logic del código requiere combinar claves de un diccionario a otro, por ejemplo:
for key in val_2.keys(): val[key]=val_2[key] El código:
newList = [] skipList = [] checked = [] getter = itemgetter("predecessor") getter_2 = itemgetter("setid_hash") for idx, val in enumerate(set_of_pk_values): if(idx not in skipList): for val_2 in set_of_pk_values[idx+1:]: if(idx not in checked): try: if (ast.literal_eval(getter(val)) == ast.literal_eval(getter(val_2))): for key in val_2.keys(): if(key != "block" and key != "username" and key != "setid" and key != "setid_hash" and key != "predecessor" and key != "time_string" and key != "condition"): val[key]=val_2[key] skipList.append(idx) except: if (getter(val) == getter(val_2)): for key in val_2.keys(): if(key != "block" and key != "username" and key != "setid" and key != "setid_hash" and key != "predecessor" and key != "time_string" and key != "condition"): val[key]=val_2[key] skipList.append(idx) checked.append(idx) Entrada de muestra (set_of_pk_values):
De acuerdo con la entrada de muestra, lo que queremos hacer es comparar si los predecesores son iguales, si son iguales, tomemos estos dos como por ejemplo:
{"username": u"radcad", "predecessor": u"[u"6a5e4bc9a328c1aeb52c565b675e6141", u"818428a59215e75d76111c8ca29a314d", u"6c acfc059508f8cb716ad0126f001f84"]", "time_string": u"2014/06/26@07:02:40", "S.clpe_leafcell.UTC_Post_start": u"1403766190", "setid_hash": u"14443f7238927d6e95 befbe12ecc6dd0", "setid": u"1986068", "block": u"simple_buff"} {"username": u"radcad", "predecessor": u"[u"6a5e4bc9a328c1aeb52c565b675e6141", u"818428a59215e75d76111c8ca29a314d", u"6c acfc059508f8cb716ad0126f001f84"]", "S.rcxt_maxcl.Predecessors": u"clpe_leafcell", "time_string": u"2015/03/08@03:06:26", "setid_hash": u"ffce9f0c46f3459acbba4f0ced884f3a", "setid": u"3095862", "block": u"simple_buff"} Como tienen los mismos predecesores, combinaremos estos dos diccionarios, excepto la clave «s: username, time_string, setid_hash, setid, condition (si existe ),
{"username": u"radcad", "predecessor": u"[u"6a5e4bc9a328c1aeb52c565b675e6141", u"818428a59215e75d76111c8ca29a314d", u"6c acfc059508f8cb716ad0126f001f84"]", "time_string": u"2014/06/26@07:02:40", "S.clpe_leafcell.UTC_Post_start": u"1403766190", "S.rcxt_maxcl.Predecessors": u"clpe_leafcell", "setid_hash": u"14443f7238927d6e95 befbe12ecc6dd0", "setid": u"1986068", "block": u"simple_buff"} La segunda parte es muy similar al ejemplo anterior (3 elementos en la lista), en el mismo diccionario, tenemos un matriz asociada con una clave (ahora hay un diccionario único con dos claves en cada elemento de la matriz), digamos:
[{"someKey_1":[b,f]}{"someKey_2":a}, {"someKey_1":[e,f]}{"someKey_2":b}, {"somekey_1":[h,k]}{"someKey_2":c}] Primera iteración (el primer elemento se compara con el segundo elemento):
recorre la matriz con la clave: someKey_1
b == b (segundo elemento » s someKey_2), luego haga algo de lógica
f != b (segundo elemento «s someKey_2), no se hace lógica
2nd iteración (primer elemento comparar s con el tercer elemento):
recorre la matriz con la clave: someKey_1
b == c (tercer elemento «s someKey_2), luego hacer algo de lógica
f != c (3er elemento «s someKey_2), no hay lógica
El código (Sudo):
for idx, val in enumerate(set_of_pk_values): for idx_2, val_2 in enumerate(set_of_pk_values): for pred in val["someKey_1"]: if(val_2["someKey_2"] == pred): #Some Logic La parte #Some Logic del código es la misma que la del primer ciclo anidado, que requiere combinar claves y sus valores de un diccionario a otro, para ejemplo:
for key in val_2.keys(): val[key]=val_2[key] El código:
newList = [] skipList = [] checked = [] getter = itemgetter("predecessor") getter_2 = itemgetter("setid_hash") for idx, val in enumerate(set_of_pk_values): if(idx not in skipList): for idx_2, val_2 in enumerate(set_of_pk_values): if(idx != idx_2): try: for pred in ast.literal_eval(getter(val)): if(getter_2(val_2) == pred): for key in val_2.keys(): if(key != "block" and key != "username" and key != "setid" and key != "setid_hash" and key != "predecessor" and key != "time_string" and key != "condition"): val[key]=val_2[key] skipList.append(idx_2) except: for pred in getter(val): if(getter_2(val_2) == pred): for key in val_2.keys(): if(key != "block" and key != "username" and key != "setid" and key != "setid_hash" and key != "predecessor" and key != "time_string" and key != "condition"): val[key]=val_2[key] skipList.append(idx_2) De manera similar, lo que se supone que debe hacer es la comparación de la matriz del predecesor con setid_hash, si son iguales, entonces combinamos.
Código completo:
def test(): set_of_pk_values = [] cache = chartCache.objects.get(username_chartNum="Test 3_leimax", openedConfig="chartTable_774164170") data = chartCache_Data.objects.filter(ID = cache) max_value = data.aggregate(Max("counter"))["counter__max"] if(max_value != None): if(max_value != 0): cached = True for i in xrange(0, max_value+1): newItem = {} set_of_pk_values.append(newItem) for items in data.iterator(): set_of_pk_values[items.counter][str(items.key)] = items.value newList = [] skipList = [] checked = [] getter = itemgetter("predecessor") getter_2 = itemgetter("setid_hash") print str(len(set_of_pk_values)) timeNow = datetime.datetime.now() ############################################## #First Nested For Loop ############################################## for idx, val in enumerate(set_of_pk_values): if(idx not in skipList): for val_2 in set_of_pk_values[idx+1:]: if(idx not in checked): try: if (ast.literal_eval(getter(val)) == ast.literal_eval(getter(val_2))): for key in val_2.keys(): if(key != "block" and key != "username" and key != "setid" and key != "setid_hash" and key != "predecessor" and key != "time_string" and key != "condition"): val[key]=val_2[key] skipList.append(idx) except: if (getter(val) == getter(val_2)): for key in val_2.keys(): if(key != "block" and key != "username" and key != "setid" and key != "setid_hash" and key != "predecessor" and key != "time_string" and key != "condition"): val[key]=val_2[key] skipList.append(idx) checked.append(idx) ############################################## #Second Nested For Loop ############################################## for idx, val in enumerate(set_of_pk_values): if(idx not in skipList): for idx_2, val_2 in enumerate(set_of_pk_values): if(idx != idx_2): try: for pred in ast.literal_eval(getter(val)): if(getter_2(val_2) == pred): for key in val_2.keys(): if(key != "block" and key != "username" and key != "setid" and key != "setid_hash" and key != "predecessor" and key != "time_string" and key != "condition"): val[key]=val_2[key] skipList.append(idx_2) except: for pred in getter(val): if(getter_2(val_2) == pred): for key in val_2.keys(): if(key != "block" and key != "username" and key != "setid" and key != "setid_hash" and key != "predecessor" and key != "time_string" and key != "condition"): val[key]=val_2[key] skipList.append(idx_2) for idx, val in enumerate(set_of_pk_values): if(idx not in skipList): newList.append(val) set_of_pk_values = newList print str(len(set_of_pk_values)) timeEnd = datetime.datetime.now() print str(timeEnd - timeNow) Actualmente, el tiempo de ejecución del primer ciclo anidado es de 21 segundos y el del segundo ciclo anidado es de alrededor de 19 segundos. En comparación con otros procesos, que van de 0 a 1 segundos, esta parte es claramente un cuello de botella.
¿Alguien puede indicarme la dirección correcta sobre cómo optimizar esta pieza de código simple pero que consume mucho tiempo?
Editar:
Intente hacer un ast.literal_eval antes de los bucles anidados:
for items in set_of_pk_values: for key in item.keys(): getter = itemgetter(key) try: toChange = ast.literal_eval(getter(items)) items[key] = toChange except: pass Responder
ast.literal_eval(...)
Si podemos eliminar sus llamadas a ast.literal_eval(...) deberíamos ver una buena reducción en el tiempo de ejecución de sus bucles. Pero, ¿por qué podemos eliminar esto que preguntas? Considere:
m = "[0, 1, 2, ... , 9,999]" # a str representation of list w/ 10k elements, 0-9999 n = "[0, 1, 2]" x = ast.literal.eval(m) y = ast.literal.eval(n) x == range(10000) # true Como puede ver en el fragmento anterior, ast.literal_eval(...) analizará y evaluará cualquier cadena que pase y devolver una representación literal de esa cadena (asumiendo, por supuesto, que la cadena representa un literal válido). Claramente, es más eficiente comparar m y n que comparar x y y. Además, no parece que le preocupe si val o val_2 es un literal de Python válido porque en el escenario que ast.literal_eval(...) genera una excepción, de forma predeterminada, solo se comparan las cadenas devueltas por getter(val) y getter(val_2) . Para resumir, puede eliminar la try: / except: y simplemente usar las declaraciones que tiene bajo la except cláusula.
for key in val_2.keys()
El ciclo anterior ocurre como el ciclo más interno de ambos ciclos 1 y 2. Con cada iteración, comprueba que key no es «equivalente a otros 7 valores clave posibles. Seis de estos valores clave se encuentran en los datos que «ha presentado y el séptimo (condition) no lo hace.Debería ser más eficaz reemplazar:
for key in val_2.keys(): if(key != "block" and key != "username" and key != "setid" and key != "setid_hash" and key != "predecessor" and key != "time_string" and key != "condition"): val[key]=val_2[key] por:
# put this at the top of the test function x_keys = set(["block", "username", "setid", "setid_hash", "predecessor", "time_string", "condition"]) # ... for key in set(val_2.keys()) - x_keys: val[key] = val_2[key] Comentarios
- Tengo una representación literal de cadenas que estaba dentro del par clave-valor del diccionario. Pensando en eso, pude escribir un bucle for que intenta cambiar la clave, el par de valores primero. Entonces no ‘ no necesito probar ast.literal_eval más tarde. Esto tuvo una aceleración significativa, de 20 segundos a milisegundos.