1
\$\begingroup\$

For a current node_pair, this program computes the number of variables matches it has. The matches for a node pair combined with a key are stored in a weight_dictionary with keys for each node pair. It only has a match if the keys of the node_pair in weight_dict align with the current mapping (this function is part of program that finds the best mapping of variables). We also have to avoid duplicates, we do this by sorting the tuple and keeping track of what we have already done in matched_tuple_keys.

Note that this is a function, meaning that all variables in the function already have a value (e.g. ’matched_tuple_keys` can already contain values).

  • key: either -1, a tuple (3,4) or a tuple of tuples ((2,3), (3,5))
  • current node_pair: a tuple (5,6) of a node pair that we are currently checking
  • weight_dict: a dictionary with tuples as keys (5,6). Each key is also a dictionary, which possible values described in 'key'. Those keys contain the scores, which are integers.
  • mapping: list of integers, e.g. [3,5,1], meaning that 0 maps to 3, 1 maps to 5 and 2 maps to 1 in that example
  • matched_tuple_keys: dictionary of tuples that we already matched. Tuples are sorted on their first instance, because we never want to match duplicates, e.g. if we matched (5,3) we don't want to match (3,5), and if we matched (0,0),(1,1),(2,2) we don't want to also match (1,1), (0,0),(2,2).

This is the bottleneck in my program. It takes a lot of time to do this for each node_pair and then check all possible matches for a certain key. If a node pair and key match depends on the current mapping, therefore it is impossible/hard to do calculations in advance. This is the code:

def compute_match_for_key(key, current_node_pair,
    weight_dict, mapping, matched_tuple_keys):

    # for key = -1 the result is simply what is in the weight dict 
    # for this node pair and key   
    if key == -1:
        match_num = weight_dict[current_node_pair][key]

    # key looks like this: (2,3)
    elif not any(isinstance(inst, tuple) for inst in key): 

        #tuple in weight dict is combination of node_pair (tuple) and current key
        #because we want to keep track of the fact that we already did 
        #this key combined with this node pair
        sorted_t = (key,) + (current_node_pair,)

        #sort tuple to avoid duplicates later
        sorted_tuple = tuple(sorted(sorted_t, key=lambda item: item[0]))

        #already matched, don't do again - e.g. if we matched (0,0),(1,1) 
        #we don't want to also match (1,1), (0,0)
        if sorted_tuple in matched_tuple_keys:
            match_num = 0

        #otherwise we check if the mapping for the first item in the key (int) 
        #is the same as the second item in the key
        #basically checks if both variable map to each other
        elif mapping[key[0]] == key[1]:
            #read from weight dictionary the number of matches
            match_num = weight_dict[current_node_pair][key] 
            #save that we did this, sorted_tuple represents the key 
            #and the current node pair
            #but it is sorted to avoid duplicates
            matched_tuple_keys[sorted_tuple] = 1
        else:
            match_num = 0       

    #key looks like this: ((2,3), (3,4), (4,7)) 
    else: 
        #sorted tuple that represents key + current node pair 
        #is now a bit larger
        sorted_t = key + (current_node_pair,)
        sorted_tuple = tuple(sorted(sorted_t, key=lambda item: item[0]))

        #already matched, don't do again - e.g. if we matched (0,0),(1,1),(2,2) 
        #we don't want to also match (1,1), (0,0),(2,2)
        if sorted_tuple in matched_tuple_keys:
            match_num = 0
        #again we have to check if both keys in the mapping match with the 
        #second key item, but now for 2 keys
        else:
            if mapping[key[0][0]] == key[0][1] and mapping[key[1][0]] == key[1][1]:
                #if both nodes match read in match number
                match_num = weight_dict[current_node_pair][key]
                matched_tuple_keys[sorted_tuple] = 1
            else:
                match_num = 0

    return match_num, matched_tuple_keys

Any help is greatly appreciated! I'm also using Cython, so simple cython tricks to use that will speed up the process are also welcome. The only thing I've done is compiling the python code I had with Cython and then using it.

I understand it is very difficult to understand the program with what I've given you here, so I appreciate even minor comments that might help efficiency. Thanks in advance.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.