0
\$\begingroup\$

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]

Since there are a lot of key combines, and sometimes a key contains duplicates, hence I decided to change lists that is inside a key,value pair to become sets instead of lists:

x_keys = set(['block', 'username', 'predecessor', 'time_string', 'condition'])
x_keys_2 = set(['block', 'username', 'time_string', 'condition'])
#Reconstruct the array with ast.literal_eval if possible
for items in set_of_pk_values:
    for key in items.keys():
        getterSet = itemgetter(key)
        try:
            toChange = ast.literal_eval(getterSet(items))
            items[key] = set(toChange)
        except:
            pass
#Reconstruct the array to use sets
for items in set_of_pk_values:
    for key in set(items.keys()) - x_keys_2:
        getterSet_2 = itemgetter(key)
        if(not isinstance(items[key], set) and str(key).count('.') != 2):
            items[key] = set([items[key]])

The Code:

newList = []
skipList = []
checked = []
getter = itemgetter("predecessor")
getter_2 = itemgetter("setid_hash")

#This part we combine keys, value that has the same predecessors
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 and idx_2 not in skipList):
                if (getter(val) == getter(val_2) and (getter(val) != set([]) or getter(val_2) != set([]))):
                    for key in set(val_2.keys()) - x_keys:
                        getter_3 = itemgetter(key)
                        if(key != "setid" and key != "setid_hash"):
                                val[key] = getter_3(val_2)
                        elif(key == "setid" or key == "setid_hash"):
                            setChange = getter_3(val) | getter_3(val_2)
                            val[key] = setChange
                    skipList.append(idx_2)

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

#This part we find out the predecessors
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 and idx_2 not in skipList):
                for pred in getter(val):
                    for items in getter_2(val_2):
                        if(items == pred):
                            for key in set(val_2.keys()) - x_keys_2:
                                getter_3 = itemgetter(key)
                                if(key != "setid" and key != "setid_hash" and key != "predecessor"):
                                    val[key]=getter_3(val_2)
                                elif(key == "setid" or key == "setid_hash" or key == "predecessor"):
                                    setChange = getter_3(val) | getter_3(val_2)
                                    val[key] = setChange
                            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:

newList = []
skipList = []
checked = []
getter = itemgetter("predecessor")
getter_2 = itemgetter("setid_hash")
x_keys = set(['block', 'username', 'predecessor', 'time_string', 'condition'])
x_keys_2 = set(['block', 'username', 'time_string', 'condition'])
if(predecessorLink == True):
    logger.info("Linking Predecessors, User:" + str(requestUsername) + ", UUID:" + str(logger_uuid) + ", Time:" + str(logger_time))
    #Reconstruct the array with ast.literal_eval if possible
    for items in set_of_pk_values:
        for key in items.keys():
            getterSet = itemgetter(key)
            try:
                toChange = ast.literal_eval(getterSet(items))
                items[key] = set(toChange)
            except:
                pass
    #Reconstruct the array to use sets
    for items in set_of_pk_values:
        for key in set(items.keys()) - x_keys_2:
            getterSet_2 = itemgetter(key)
            if(not isinstance(items[key], set) and str(key).count('.') != 2):
                items[key] = set([items[key]])
    #This part we combine stages that has the same predecessors (RCXT MAXC and RCXT MAXCL)
    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 and idx_2 not in skipList):
                    if (getter(val) == getter(val_2) and (getter(val) != set([]) or getter(val_2) != set([]))):
                        for key in set(val_2.keys()) - x_keys:
                            getter_3 = itemgetter(key)
                            if(key != "setid" and key != "setid_hash"):
                                    val[key] = getter_3(val_2)
                            elif(key == "setid" or key == "setid_hash"):
                                setChange = getter_3(val) | getter_3(val_2)
                                val[key] = setChange
                        skipList.append(idx_2)
    #Rebuild the array, to save some memory
    for idx, val in enumerate(set_of_pk_values):
        if(idx not in skipList):
            newList.append(val)
        val = {}
    del set_of_pk_values
    set_of_pk_values = newList
    del newList
    newList = []
    skipList = []
    #This part we find out the predecessors
    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 and idx_2 not in skipList):
                    for pred in getter(val):
                        for items in getter_2(val_2):
                            if(items == pred):
                                for key in set(val_2.keys()) - x_keys_2:
                                    getter_3 = itemgetter(key)
                                    if(key != "setid" and key != "setid_hash" and key != "predecessor"):
                                        val[key]=getter_3(val_2)
                                    elif(key == "setid" or key == "setid_hash" or key == "predecessor"):
                                        setChange = getter_3(val) | getter_3(val_2)
                                        val[key] = setChange
                                skipList.append(idx_2)
    #This part we only put in complete dictionaries. Where previous dictionaries that got extracted data are called
    #are in the skipList array
    for idx, val in enumerate(set_of_pk_values):
        if(idx not in skipList):
            newList.append(val)
    set_of_pk_values = newList

I think one of the bottleneck is that set looping takes time. Also set concatenation takes some time as well.

Compared to a full list solution, it is around 50~100% slower. However, on large set_of_pk_values, a list solution instead of set creates arrays inside dictionaries that has around ~1000 items. If you use a set, it becomes around 30 items.

It will give memory errors using lists, but faster, on the other hand, sets will use least amount of memory, but slower. Is it possible to get best of both worlds?

\$\endgroup\$

1 Answer 1

Reset to default
1
\$\begingroup\$

While operator.itemgetter is a more efficient alternative to an equivalent lambda function, it does not beat normal dictionary lookup [], and using it for that purpose makes code harder to read.

Your code looks very complicated to me and I find it hard to follow, but the most likely bottleneck is the five-fold nested for loop.

In there, my first thought would be to consider if these lines...

            for pred in getter(val):
                for items in getter_2(val_2):
                    if(items == pred):

...or, if we eliminate the getter...

            for pred in val["predecessor"]:
                for items in val_2["setid_hash"]:
                    if(items == pred):

...could be replaced by a set operation such as:

            if not val["predecessor"].isdisjoint(val_2["setid_hash"]):
\$\endgroup\$
3
  • \$\begingroup\$ I thought using getters was faster because it is in the C level? \$\endgroup\$
    – user1157751
    Commented Mar 19, 2015 at 19:38
  • \$\begingroup\$ The speed difference in using dictionary lookup vs itemgetter was less than 1% when I tested it in my code. \$\endgroup\$
    – user1157751
    Commented Mar 19, 2015 at 20:24
  • \$\begingroup\$ there was a 5% speedup when using disjoint instead of comparing. I think one of the bottlenecks is that two-fold set_of_pk_values loop. Thanks for your help! \$\endgroup\$
    – user1157751
    Commented Mar 19, 2015 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.