An array of dictionaries; comparing each {key, value} pair; and combining dictionaries

Question

I'm trying to optimize a nested for loops that compares an element in the array with the rest of the element in the array.

There's two part, the first part is for example, an Array has 3 elements, and each element is a dictionary:

[{"someKey_1":"a"}, {"someKey_1":"b"}, {"somekey_1":"a"}]

---

1st iteration(1st element compares with 2nd element):

Test key of "someKey" for two elements, since a != b, then we do nothing

---

2st iteration(1st element compares with 3nd element):

Test key of "someKey" for two elements, since a == a, we do some logic

---

The 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

The #Some Logic part of the code requires combining keys from one dictionary to another, for example:

for key in val_2.keys():
    val[key]=val_2[key]

The 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)

Sample input (set_of_pk_values):

{'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'8d899b7eec936785dfcbcf86879bd2b7', u'e0cd1b80ee537d2e9ce5efaf3542da22']", 't
ime_string': u'2014/06/27@07:02:15', 'S.clpe_leafcell.UTC_Post_start': u'1403852565', 'setid_hash': u'9172da57b62419041e
c76524de72e235', 'setid': u'1991185', 'block': u'simple_buff'}
{'username': u'radcad', 'predecessor': u"[u'755b2dafcace3c56a9f409899e219708', u'dd7e980b20027b8120c7884459bfab44']", 't
ime_string': u'2014/06/28@07:02:40', 'S.clpe_leafcell.UTC_Post_start': u'1403938989', 'setid_hash': u'0d7f3d2771a8defae0
f0c969cbdd8938', 'setid': u'1994886', 'block': u'simple_buff'}
{'username': u'radcad', 'predecessor': u"[u'8ccdc497036cc700512e44e53ae3b504', u'3ba9c3963d37d0415489ad73a66400d1', u'12
896a98310e9be61b60f8575bdc86fa']", 'S.rcxt_maxcl.Predecessors': u'clpe_leafcell', 'time_string': u'2015/03/07@03:05:48',
 'setid_hash': u'ed47755f1067c891322a9a778c4d8bc8', 'setid': u'3094622', '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'}

So Based on the sample input, what we want to do is compare if predecessors are the same, if they are the same, let's take these two as for example:

{'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'}

Since they have the same predecessors, we will combine these two dictionaries except the key's: username, time_string, setid_hash, setid, condition (if exists),

 {'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'}

---

The second part is very similar to the previous example (3 items in the list), in the same dictionary, we have an array associated with a key(now there's a single dictionary with two keys in each element of the array), let's say:

[{"someKey_1":[b,f]}{"someKey_2":a}, 
 {"someKey_1":[e,f]}{"someKey_2":b}, 
 {"somekey_1":[h,k]}{"someKey_2":c}]

---

1st iteration (1st element compares with 2nd element):

loops through the array with the key: someKey_1

b == b (2nd element's someKey_2), then do some logic

f != b (2nd element's someKey_2), no logic is done

---

2nd iteration (1st element compares with 3rd element):

loops through the array with the key: someKey_1

b == c (3rd element's someKey_2), then do some logic

f != c (3rd element's someKey_2), no logic is done

---

The 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

The #Some Logic part of the code is the same as the first nested loop, which requires combining keys and their values from one dictionary to another, for example:

for key in val_2.keys():
    val[key]=val_2[key]

The 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)

Similarly what this is supposed to do is the compare the array of predecessor with setid_hash, if they are equal, then we combine.

---

Full 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)

---

Currently the runtime for the first nested loop: 21 seconds, and the second nested loop is around 19 seconds. Compared to other processes, ranging from 0-1 seconds, this part is clearly a bottleneck.

Can anybody point me to the right direction on how to optimize this piece of simple, yet extremely time consuming code?

---

Edit:

Try to do an ast.literal_eval before nested loops:

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

Answer 1

ast.literal_eval(...)

If we can remove your calls to ast.literal_eval(...) we should see a nice reduction in the run time of your loops. But, why can we remove this you ask? Consider:

    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

As you can see from the snippet above, ast.literal_eval(...) will parse and evaluate whatever string you pass it, and return a literal representation of that string (assuming of course that the string represents a valid literal). Clearly, it is more efficient to compare m and n than it is to compare x and y. Also, it doesn't appear that you are concerned with whether or not val or val_2 is a valid python literal because under the scenario that ast.literal_eval(...)throws an exception, you default to just comparing the strings returned by getter(val) and getter(val_2). Long story short you can remove the try: / except: and just use the statements you have under the except clause.

for key in val_2.keys()

The above loop occurs as the inner-most loop of both loops 1 and 2. With each iteration you check that key isn't equivalent to 7 other possible key values. 6 of these key values occur in the data you've presented and the 7th (condition) doesn't. It should be more efficient to replace:

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]

with:

# 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]