Sto cercando di ottimizzare un ciclo for annidato che confronta un elemento dellarray con il resto dellelemento nellarray .
Ci sono due parti, la prima parte è per esempio, un Array ha 3 elementi e ciascuna elemento è un dizionario:
[{"someKey_1":"a"}, {"someKey_1":"b"}, {"somekey_1":"a"}] 1a iterazione (1 ° elemento confronta con 2 ° elemento):
Test chiave di “someKey “per due elementi, poiché a != b, non facciamo nulla
2a iterazione (il 1 ° elemento si confronta con il 3 ° elemento):
Verifica la chiave di “someKey” per due elementi, poiché a == a, facciamo un po di logica
Il codice (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 codice richiede la combinazione di chiavi da un dizionario a un altro, ad esempio:
for key in val_2.keys(): val[key]=val_2[key] Il codice:
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) Esempio di input (set_of_pk_values):
Quindi, in base allinput di esempio, quello che vogliamo fare è confrontare se i predecessori sono gli stessi, se sono gli stessi, prendiamo questi due come per esempio:
{"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"} Dato che hanno gli stessi predecessori, combineremo questi due dizionari tranne la chiave “s: nomeutente, stringa_ora, setid_hash, setid, condizione (se esiste ),
{"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 seconda parte è molto simile allesempio precedente (3 elementi nellelenco), nello stesso dizionario, abbiamo un array associato a una chiave (ora cè un singolo dizionario con due chiavi in ogni elemento dellarray), diciamo:
[{"someKey_1":[b,f]}{"someKey_2":a}, {"someKey_1":[e,f]}{"someKey_2":b}, {"somekey_1":[h,k]}{"someKey_2":c}] 1a iterazione (il primo elemento viene confrontato con il secondo elemento):
scorre larray con la chiave: someKey_1
b == b (secondo elemento ” s someKey_2), quindi esegui un po di logica
f != b (secondo elemento “s someKey_2), non viene eseguita alcuna logica
2 ° iterazione (1 ° elemento confronta s con 3 ° elemento):
scorre larray con la chiave: someKey_1
b == c (3 ° elemento “s someKey_2), quindi fai un po di logica
f != c (terzo elemento “s someKey_2), nessuna logica è fatta
Il codice (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 codice è la stessa del primo ciclo annidato, che richiede la combinazione delle chiavi e dei loro valori da un dizionario allaltro, per esempio:
for key in val_2.keys(): val[key]=val_2[key] Il codice:
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) Allo stesso modo cosa dovrebbe fare è il confronto dellarray del predecessore con setid_hash, se sono uguali, combiniamo.
Codice 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) Attualmente il runtime per il primo ciclo annidato: 21 secondi e il secondo ciclo annidato è di circa 19 secondi. Rispetto ad altri processi, che vanno da 0 a 1 secondo, questa parte è chiaramente un collo di bottiglia.
Qualcuno può indicarmi la giusta direzione su come ottimizzare questo pezzo di codice semplice ma estremamente dispendioso in termini di tempo?
Modifica:
prova a eseguire un ast.literal_eval prima dei cicli annidati:
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 Rispondi
ast.literal_eval(...)
Se possiamo rimuovere le tue chiamate a ast.literal_eval(...) dovremmo vedere una bella riduzione del tempo di esecuzione dei tuoi loop. Ma perché possiamo rimuovere questo, chiedi? Considera:
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 Come puoi vedere dallo snippet sopra, ast.literal_eval(...) analizzerà e valuterà qualunque stringa passi e restituisce una rappresentazione letterale di quella stringa (assumendo ovviamente che la stringa rappresenti un valore letterale valido). Chiaramente, è più efficiente confrontare m e n che confrontare x e y. Inoltre, non sembra che ti interessi se val o val_2 sia o meno un letterale Python valido perché nello scenario che ast.literal_eval(...) genera uneccezione, per impostazione predefinita si limita a confrontare le stringhe restituite da getter(val) e getter(val_2) Per farla breve, puoi rimuovere la try: / except: e utilizzare semplicemente le istruzioni che hai sotto la clausola except.
for key in val_2.keys()
Il ciclo precedente si presenta come il ciclo più interno di entrambi i cicli 1 e 2. Con ogni iterazione controlli che key non è “t equivalente ad altri 7 possibili valori chiave. 6 di questi valori chiave si trovano nei dati che hai presentato e il 7 ° (condition) no “t.Dovrebbe essere più efficiente sostituire:
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] con:
# 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] Commenti
- Ho una rappresentazione letterale di stringhe che si trovava allinterno della coppia di valori chiave del dizionario. Pensando a questo, sono stato in grado di scrivere un ciclo for che cerca di cambiare prima la chiave, la coppia di valori. Quindi non ‘ bisogno di testare ast.literal_eval più tardi. Questo ha avuto un significativo aumento della velocità, da 20 secondi a millisecondi.