Estou tentando otimizar um loop for aninhado que compara um elemento na matriz com o resto do elemento na matriz .
Há duas partes, a primeira parte é, por exemplo, uma matriz tem 3 elementos, e cada elemento é um dicionário:
[{"someKey_1":"a"}, {"someKey_1":"b"}, {"somekey_1":"a"}] 1ª iteração (1 ° elemento compara com 2 ° elemento):
Chave de teste de “someKey “para dois elementos, uma vez que a != b, não fazemos nada
2ª iteração (o primeiro elemento se compara com o terceiro elemento):
Teste a chave de “someKey” para dois elementos, uma vez que a == a, fazemos alguma lógica
O 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 A parte #Some Logic do código requer a combinação de chaves de um dicionário para outro, por exemplo:
for key in val_2.keys(): val[key]=val_2[key] O 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) Exemplo de entrada (set_of_pk_values):
Portanto, com base na entrada de amostra, o que queremos fazer é comparar se os predecessores são os mesmos, se eles são os mesmos, vamos pegar esses dois como exemplo:
{"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 eles têm os mesmos predecessores, combinaremos esses dois dicionários exceto a chave “s: nome de usuário, string de tempo, setid_hash, setid, condição (se existir ),
{"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"} A segunda parte é muito semelhante ao exemplo anterior (3 itens na lista), no mesmo dicionário, temos um array associado a uma chave (agora existe um único dicionário com duas chaves em cada elemento do array), digamos:
[{"someKey_1":[b,f]}{"someKey_2":a}, {"someKey_1":[e,f]}{"someKey_2":b}, {"somekey_1":[h,k]}{"someKey_2":c}] 1ª iteração (o primeiro elemento se compara com o segundo elemento):
faz um loop na matriz com a chave: someKey_1
b == b (segundo elemento ” s someKey_2), então faça alguma lógica
f != b (2º elemento “s someKey_2), nenhuma lógica é feita
2º iteração (comparação do 1º elemento s com terceiro elemento):
faz um loop através da matriz com a chave: someKey_1
b == c (terceiro elemento “s someKey_2), então faça alguma lógica
f != c (terceiro elemento “s someKey_2), nenhuma lógica é feita
O 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 A parte #Some Logic do código é igual ao primeiro loop aninhado, o que requer a combinação de chaves e seus valores de um dicionário para outro, para exemplo:
for key in val_2.keys(): val[key]=val_2[key] O 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) Da mesma forma, o que isso deve fazer é a comparação da matriz do predecessor com setid_hash, se eles forem iguais, então 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) Atualmente, o tempo de execução para o primeiro loop aninhado: 21 segundos, e o segundo loop aninhado é cerca de 19 segundos. Em comparação com outros processos, que variam de 0 a 1 segundo, essa parte é claramente um gargalo.
Alguém pode me indicar a direção certa sobre como otimizar esse código simples, mas extremamente demorado?
Editar:
Tente fazer um ast.literal_eval antes dos loops aninhados:
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 Resposta
ast.literal_eval(...)
Se pudermos remover suas chamadas para ast.literal_eval(...) devemos ver uma boa redução no tempo de execução de seus loops. Mas, por que podemos remover isso, você pergunta? 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 você pode ver no snippet acima, ast.literal_eval(...) analisará e avaliará qualquer string que você passar e retornar uma representação literal dessa string (assumindo, é claro, que a string representa um literal válido). Claramente, é mais eficiente comparar m e n do que comparar x e y. Além disso, não parece que você está preocupado se val ou val_2 é um literal python válido porque, sob o cenário de ast.literal_eval(...) lança uma exceção, o padrão é apenas comparar as strings retornadas por getter(val) e getter(val_2) . Resumindo, você pode remover o try: / except: e apenas usar as declarações que você tem na cláusula except.
for key in val_2.keys()
O loop acima ocorre como o loop mais interno de ambos os loops 1 e 2. Com cada iteração, você verifica se key não é equivalente a 7 outros valores de chave possíveis. 6 desses valores-chave ocorrem nos dados que você apresentou e o 7º (condition) não.Deve ser mais eficiente substituir:
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] Comentários
- Eu tenho algumas representações literais de strings que estavam dentro do par de valores-chave do dicionário. Pensando nisso, consegui escrever um loop for que tenta alterar o par chave e valor primeiro. Então, não ‘ preciso testar ast.literal_eval mais tarde. Isso teve uma aceleração significativa, de 20 segundos para milissegundos.