Próbuję zoptymalizować zagnieżdżone pętle, które porównują element w tablicy z resztą elementu w tablicy .
Są dwie części, pierwsza to na przykład Array składa się z 3 elementów, a każdy element jest słownikiem:
[{"someKey_1":"a"}, {"someKey_1":"b"}, {"somekey_1":"a"}] Pierwsza iteracja (pierwszy element porównuje się z drugim elementem):
Testuj klucz „someKey „dla dwóch elementów, ponieważ a != b, to nic nie robimy
2. iteracja (pierwszy element porównuje się z 3. elementem):
Przetestuj klucz „someKey” dla dwóch elementów, ponieważ a == a, wykonujemy pewną logikę
Kod (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 Część kodu #Some Logic wymaga połączenia kluczy z jednego słownika do drugiego, na przykład:
for key in val_2.keys(): val[key]=val_2[key] Kod:
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) Przykładowe dane wejściowe (set_of_pk_values):
Więc na podstawie przykładowych danych wejściowych chcemy porównać, czy poprzednicy są tacy sami, jeśli są tacy sami, weźmy te dwa jako na przykład:
{"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"} Ponieważ mają tych samych poprzedników, połączymy te dwa słowniki z wyjątkiem klucza „s: nazwa użytkownika, ciąg_czasu, setid_hash, setid, warunek (jeśli istnieje ),
{"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"} Druga część jest bardzo podobna do poprzedniego przykładu (3 pozycje na liście), w tym samym słowniku mamy tablica powiązana z kluczem (teraz „jest pojedynczy słownik z dwoma kluczami w każdym elemencie tablicy), powiedzmy:
[{"someKey_1":[b,f]}{"someKey_2":a}, {"someKey_1":[e,f]}{"someKey_2":b}, {"somekey_1":[h,k]}{"someKey_2":c}] Pierwsza iteracja (pierwszy element porównuje się z drugim elementem):
wykonuje pętlę przez tablicę z kluczem: someKey_1
b == b (2. element ” s someKey_2), a następnie wykonaj jakąś logikę
f != b (2. element „s someKey_2), logika nie jest wykonana
2. iteracja (porównanie pierwszego elementu s z trzecim elementem):
przegląda tablicę z kluczem: someKey_1
b == c (3rd element „s someKey_2), a następnie zrób jakąś logikę
f != c (trzeci element „s someKey_2), logika nie jest wykonywana
Kod (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 Część kodu #Some Logic jest taka sama jak pierwsza zagnieżdżona pętla, która wymaga łączenia kluczy i ich wartości z jednego słownika do drugiego, przykład:
for key in val_2.keys(): val[key]=val_2[key] Kod:
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) Podobnie, co to powinno zrobić jest tablicą porównania poprzednika z setid_hash, jeśli są równe, łączymy.
Pełny kod:
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) Obecnie czas wykonywania pierwszej pętli zagnieżdżonej wynosi 21 sekund, a drugiej pętli zagnieżdżonej około 19 sekund. W porównaniu z innymi procesami, trwającymi od 0 do 1 sekundy, ta część jest wyraźnie wąskim gardłem.
Czy ktoś może wskazać mi właściwy kierunek optymalizacji tego prostego, ale niezwykle czasochłonnego kodu?
Edytuj:
Spróbuj wykonać ast.literal_eval przed zagnieżdżonymi pętlami:
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 Odpowiedz
ast.literal_eval(...)
Jeśli możemy usunąć Twoje połączenia z ast.literal_eval(...) powinniśmy zobaczyć dobre skrócenie czasu wykonywania twoich pętli. Ale dlaczego możemy usunąć to, o co pytasz? Rozważ:
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 widać na powyższym fragmencie, ast.literal_eval(...) przeanalizuje i oszacuje każdy przekazany ciąg it i zwróć literalną reprezentację tego ciągu (zakładając oczywiście, że ciąg reprezentuje prawidłowy literał). Oczywiście porównywanie m i n jest bardziej wydajne niż porównywanie x i y. Nie wydaje się również, że martwisz się, czy val lub val_2 jest prawidłowym literałem Pythona, ponieważ w scenariuszu ast.literal_eval(...) zgłasza wyjątek, domyślnie porównujesz tylko ciągi zwracane przez getter(val) i getter(val_2) . Krótko mówiąc, możesz usunąć try: / except: i po prostu użyć instrukcji, które masz pod klauzulą except.
for key in val_2.keys()
Powyższa pętla występuje jako najbardziej wewnętrzna pętla obu pętli 1 i 2. Przy każdej iteracji sprawdzasz, czy key nie jest równoważne 7 innym możliwym wartościom klucza. Sześć z tych kluczowych wartości występuje w przedstawionych przez Ciebie danych, a siódma (condition) nie.Efektywniejsze powinno być zastąpienie:
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] przez:
# 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] Komentarze
- Mam dosłowną reprezentację ciągów znaków znajdujących się w parze klucz-wartość w słowniku. Myśląc o tym, byłem w stanie napisać pętlę for, która najpierw próbuje zmienić parę klucz, wartość. Wtedy nie ' nie muszę później testować pod kątem ast.literal_eval. To znacznie przyspieszyło, z 20 sekund do milisekund.