Snažím se optimalizovat vnořené smyčky, které porovnávají prvek v poli se zbytkem prvku v poli .
Existují dvě části, první část je například pole má 3 prvky a každý prvek je slovník:
[{"someKey_1":"a"}, {"someKey_1":"b"}, {"somekey_1":"a"}] 1. iterace (1. prvek se porovnává s 2. prvkem):
Testovací klíč funkce „someKey“ „pro dva prvky, protože a != b, pak neděláme nic
2. iterace (1. prvek se porovnává s 3. prvkem):
Testovací klíč „someKey“ pro dva prvky, protože a == a provádíme nějakou logiku
Kód (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 Část kódu #Some Logic vyžaduje kombinaci klíčů z jednoho slovníku do druhého, například:
for key in val_2.keys(): val[key]=val_2[key] Kód:
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) Ukázkový vstup (set_of_pk_values):
Takže na základě ukázkového vstupu chceme porovnat, zda jsou předchůdci stejní, pokud jsou stejní, vezměme si tyto dva například:
{"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"} Protože mají stejné předchůdce, spojíme tyto dva slovníky kromě klíčů: uživatelské jméno, časový_řetězec, setid_hash, setid, podmínka (pokud existuje) ),
{"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"} Druhá část je velmi podobná předchozímu příkladu (3 položky v seznamu), ve stejném slovníku máme pole spojené s klíčem (nyní existuje jeden slovník se dvěma klíči v každém prvku pole), řekněme:
[{"someKey_1":[b,f]}{"someKey_2":a}, {"someKey_1":[e,f]}{"someKey_2":b}, {"somekey_1":[h,k]}{"someKey_2":c}] 1. iterace (1. prvek se porovnává s 2. prvkem):
prochází pole pomocí klíče: someKey_1
b == b (2. prvek) s someKey_2), pak proveďte nějakou logiku
f != b (2. prvek „s someKey_2), žádná logika se neprovede
2. iterace (porovnání 1. prvku s s 3. prvkem):
prochází pole s klíčem: someKey_1
b == c (3. element „s someKey_2), pak proveďte nějakou logiku
f != c (3. prvek „s someKey_2), žádná logika není hotová
Kód (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 Část kódu #Some Logic je stejná jako první vnořená smyčka, která vyžaduje kombinaci klíčů a jejich hodnot z jednoho slovníku do druhého, protože příklad:
for key in val_2.keys(): val[key]=val_2[key] Kód:
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) Podobně to má být je porovnání pole předchůdce s setid_hash, pokud jsou stejné, pak kombinujeme.
Celý kód:
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) Momentálně je doba běhu pro první vnořenou smyčku: 21 sekund a druhá vnořená smyčka je přibližně 19 sekund. Ve srovnání s jinými procesy, které se pohybují od 0 do 1 sekundy, je tato část zjevně překážkou.
Může mi někdo ukázat správný směr, jak optimalizovat tento jednoduchý, ale extrémně časově náročný kód? / p>
Upravit:
Zkuste vložit ast.literal_eval před vnořenými smyčkami:
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 Přijmout
ast.literal_eval(...)
Pokud můžeme odstranit vaše hovory na ast.literal_eval(...) měli bychom vidět pěkné zkrácení doby běhu vašich smyček. Proč ale můžeme toto dotazování odstranit? Zvažte:
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 Jak vidíte z úryvku výše, ast.literal_eval(...) analyzuje a vyhodnotí jakýkoli řetězec, který předáte it a vrátit doslovnou reprezentaci tohoto řetězce (za předpokladu, že řetězec představuje platný literál). Je zřejmé, že je efektivnější porovnávat m a n než porovnávat x a y. Rovněž se nezdá, že by vás zajímalo, zda val nebo val_2 je platný literál pythonu, protože podle scénáře ast.literal_eval(...) vyvolá výjimku, výchozí je pouze porovnání řetězců vrácených getter(val) a getter(val_2) . Stručný příběh, můžete odstranit try: / except: a použít pouze příkazy, které máte v klauzuli except.
for key in val_2.keys()
Výše uvedená smyčka se vyskytuje jako nejvnitřnější smyčka obou smyček 1 a 2. S každou iterací kontrolujete, zda key neodpovídá 7 dalším možným klíčovým hodnotám. 6 z těchto klíčových hodnot se vyskytuje v datech, která jste předložili, a 7. (condition) to není.Mělo by být efektivnější nahradit:
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] s:
# 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] Komentáře
- Mám nějaké doslovné vyjádření řetězců, které byly uvnitř dvojice klíčových hodnot slovníku. Když jsem o tom přemýšlel, dokázal jsem napsat smyčku for, která se nejprve pokusí změnit pár klíč, hodnota. Potom již ‚ nemusím testovat ast.literal_eval později. To mělo výrazné zrychlení z 20 sekund na milisekundy.