Ich versuche, eine verschachtelte for-Schleife zu optimieren, die ein Element im Array vergleicht mit dem Rest des Elements im Array .
Es gibt zwei Teile, der erste Teil besteht beispielsweise aus einem Array mit jeweils 3 Elementen Element ist ein Wörterbuch:
[{"someKey_1":"a"}, {"someKey_1":"b"}, {"somekey_1":"a"}] 1. Iteration (1. Element im Vergleich zum 2. Element):
Testschlüssel von „someKey“ „für zwei Elemente, da a != b, dann machen wir nichts
2. Iteration (1. Element vergleicht mit 3. Element):
Testschlüssel von „someKey“ für zwei Elemente, da a == a wir eine Logik ausführen
Der Code (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 Der Teil #Some Logic des Codes erfordert das Kombinieren von Schlüsseln von einem Wörterbuch zu einem anderen, zum Beispiel:
for key in val_2.keys(): val[key]=val_2[key] Der Code:
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) Beispieleingabe (set_of_pk_values):
Basierend auf der Beispieleingabe möchten wir also vergleichen, ob die Vorgänger gleich sind. Wenn sie gleich sind, nehmen wir diese beiden wie zum Beispiel:
{"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"} Da sie dieselben Vorgänger haben, werden diese beiden Wörterbücher mit Ausnahme der Schlüssel kombiniert: Benutzername, Zeitzeichenfolge, setid_hash, setid, Bedingung (falls vorhanden) ),
{"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"} Der zweite Teil ist dem vorherigen Beispiel sehr ähnlich (3 Elemente in der Liste), im selben Wörterbuch haben wir eine Array, das einem Schlüssel zugeordnet ist (jetzt gibt es ein einzelnes Wörterbuch mit zwei Schlüsseln in jedem Element des Arrays), sagen wir:
[{"someKey_1":[b,f]}{"someKey_2":a}, {"someKey_1":[e,f]}{"someKey_2":b}, {"somekey_1":[h,k]}{"someKey_2":c}] 1. Iteration (1. Element im Vergleich zum 2. Element):
durchläuft das Array mit dem Schlüssel: someKey_1
b == b (2. Element “ s someKey_2), dann mache eine logische
f != b (2. Element „s someKey_2), es wird keine Logik gemacht
2 .. Iteration (1. Elementvergleich s mit 3. Element):
durchläuft das Array mit dem Schlüssel: someKey_1
b == c (3. Element „s someKey_2) mache eine Logik
f != c (3. Element „someKey_2), es wird keine Logik gemacht
Der Code (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 Der Teil #Some Logic des Codes ist derselbe wie die erste verschachtelte Schleife, für die Schlüssel und ihre Werte von einem Wörterbuch zum anderen kombiniert werden müssen Beispiel:
for key in val_2.keys(): val[key]=val_2[key] Der Code:
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) Ähnlich soll dies geschehen ist das Vergleichen des Arrays des Vorgängers mit setid_hash, wenn sie gleich sind, kombinieren wir.
Vollständiger Code:
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) Derzeit beträgt die Laufzeit für die erste verschachtelte Schleife 21 Sekunden, und die zweite verschachtelte Schleife beträgt etwa 19 Sekunden. Im Vergleich zu anderen Prozessen im Bereich von 0 bis 1 Sekunden ist dieser Teil eindeutig ein Engpass.
Kann mich jemand auf die richtige Richtung hinweisen, wie dieser einfache, aber äußerst zeitaufwändige Code optimiert werden kann?
Bearbeiten:
Versuchen Sie, vor verschachtelten Schleifen ein ast.literal_eval auszuführen:
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 Antwort
ast.literal_eval(...)
Wenn wir Ihre Anrufe an Wir sollten eine schöne Reduzierung der Laufzeit Ihrer Loops sehen. Aber warum können wir das entfernen, fragen Sie? Beachten Sie:
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 Wie Sie dem obigen Snippet entnehmen können, analysiert ast.literal_eval(...) die von Ihnen übergebene Zeichenfolge und wertet sie aus und geben Sie eine Literaldarstellung dieser Zeichenfolge zurück (vorausgesetzt natürlich, dass die Zeichenfolge ein gültiges Literal darstellt). Es ist eindeutig effizienter, m und n zu vergleichen, als x zu vergleichen und y. Es scheint auch nicht so, als ob Sie sich darum kümmern, ob val oder val_2 ein gültiges Python-Literal ist, da dies unter dem Szenario der Fall ist ast.literal_eval(...) löst eine Ausnahme aus. Sie vergleichen standardmäßig nur die von getter(val) und getter(val_2) zurückgegebenen Zeichenfolgen Kurz gesagt, Sie können die try: / except: entfernen und einfach die Anweisungen verwenden, die Sie unter der except -Klausel haben.
for key in val_2.keys()
Die obige Schleife tritt als innerste Schleife beider Schleifen auf 1 und 2. Mit jeder Iteration überprüfen Sie, ob key nicht 7 anderen möglichen Schlüsselwerten entspricht. 6 dieser Schlüsselwerte kommen in den von Ihnen präsentierten Daten vor und die 7. (condition) nicht.Das Ersetzen von:
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] durch:
# 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] Kommentare
- Ich habe eine wörtliche Darstellung von Zeichenfolgen, die sich im Schlüsselwertpaar des Wörterbuchs befanden. Als ich darüber nachdachte, konnte ich eine for-Schleife schreiben, die zuerst versucht, das Schlüssel-Wert-Paar zu ändern. Dann muss ich ‚ später nicht mehr auf ast.literal_eval testen. Dies hatte eine signifikante Beschleunigung von 20 Sekunden auf Millisekunden.
- Ich habe eine wörtliche Darstellung von Zeichenfolgen, die sich im Schlüsselwertpaar des Wörterbuchs befanden. Als ich darüber nachdachte, konnte ich eine for-Schleife schreiben, die zuerst versucht, das Schlüssel-Wert-Paar zu ändern. Dann muss ich ‚ später nicht mehr auf ast.literal_eval testen. Dies hatte eine signifikante Beschleunigung von 20 Sekunden auf Millisekunden.