Compare elements of each list of lists to corresponding ones in different list

Question

My goal is to reduce processing time significantly (if possible) by making this working code more efficient. Currently 50k row by 105 column data taking about overall 2 hours to process. Share of this piece is 95%.

This piece is a key part of my Python 3.6.3 script that compares two set of list of lists element by element regardless of datatype. I spent long hours but seems I reached my limits here. This is running on Windows 10.

Sorry about lots of variables. Here is description:
Ap, Bu - list of lists. Each sublist

• may contain any datatype (usually String, Number, Null, Date).
• 1st element of list within list is always unique string.
• has equal number of elements as other lists
• each list in Ap has corresponding list in Bu (corresponding in here means 1st element and ID element (not necessarily other elements) of a sublist of Ap matches that of Bu, that's considered there is corresponding match)
• each sublist will contain unique ID in the same position. Meaning index of ID is same in every sublist (be it Ap or Bu).

prx - is index of a list within Ap

urx - corresponding/matching index of a list within Bu, as evidenced by urx=l_urx.index (prx)

cx - is index of an element in a single list of Au ux - is a corresponding element index of an element in a matching list of Bu, as evidenced by ux = l_ux.index(cx)

rng_lenAp - is range(len(Ap))
rng_ls - is range(individual list within Ap)

To visualize (just example):

Ap = [['egg', 12/12/2000, 10, ID1, NULL], ['goog', 23, 100, ID2,12/12/2000]]  
Bu = [['goog', '3434', 100, ID2, 12/12/2000], ['egg', 12/12/2000, 45, ID1, NULL]]

for prx in rng_lenAp:
    urx = l_urx.index (prx)
    if Ap[prx][0] == Bu[urx][0]:
        for cx in rng_ls:
            ux = l_ux.index(cx)
            #If not header, non-matching cells get recorded with their current value
            if cx!=0 and Ap[prx][cx] != Bu[urx][ux]:
                output[prx].append (str(Ap[prx][cx] + '^' + str(Bu[urx][ux]))
            #Unless it is row header or ID in column, matching cells gets 'ok'
            elif cx!=0 and prx!=0 and urx !=0 and Ap[prx][cx] == Bu[urx][ux]:
                output[prx].append ('ok' +'^' + 'ok')
            # Anything else gets recorded with their current value
            else: 
                output[prx].append (str(Ap[prx][cx] + '^' + str(Bu[urx][ux]))

There must a way to reduce processing time drastically. Currently the cell by cell comparison of 50k row by 100 column data to 50k row by 100 column data is takes about 2 hours. Expected under 30 min. 3.1 GHz, 4 CPUs (8196MB RAM).

Answer 1

Your algorithm uses the list.index function to get the indices of the sublists which is an \$O(n)\$ operation. You are also iterating through all the rows and columns of the data which is an \$O(k \times m)\$ operation where \$k\$ is the number of rows and \$m\$ is the number of columns. In the end it is an \$O(n \times k \times m)\$ algorithm.

In my algorithm getting the intersection of the keys is an \$O(\min(\text{len}(A), \text{len}(B)))\$ complexity then iterating the sublists is an \$O(m)\$ which results in an \$O(\min(\text{len}(A), \text{len}(B)) \times m)\$ complexity.

My alternate solution is based on the fact that the first element of each sublist is unique. I would structure the data in a different way and use dictionaries instead of lists. As each first element is unique this would be the key and the rest of the sublist would be the value in the dictionary. After inserting all the data in the dicts, taking the intersection of the keys would result in a (hopefully) smaller set of data. The output would be also a dictionary created while iterating through the resulting keys.

output = defaultdict(list) # from collections
keys = A.keys() & B.keys() # intersect the keys
for key in keys:
    # create output based on sublists
    output[key] = ['ok^ok' if a==b else '{}^{}'.format(a,b) for a,b in zip(A[key],B[key])]

For execution time I generated random strings for keys and values. Each key and sublist element was a randomly generated unique string of length 10. Each key had 50% chance to be included in both A and B and each sublist element also had a 50% to be the same for the corresponding element in the other dictionary. I created 50k keys and 104 sublist element for each key.

Generating the data took me around 26 seconds and creating the output took less than 1 second. The results depend on the matching key ratio of the two datasets but it never took more than 2 seconds to finish.

Answer 2

Folks, I appreciated who looked into this. After spending about 6 hours, I was able to resolve the issue by rewriting above section. Result: overall under 2 minutes processing, instead of previously reported 2 hour + processing time (for 52k X 105 to 52k X 105 matrix (list of lists) for element vs element comparison). May not still be perfect but I think this serves the purpose at this time and somebody may find this version helpful:

r = prx (for better look only)
c = ux (for better look only)

# Outer loop to iterate thru rows (sublists)
for r in rng_lenAp:
    # Inner loop to iterate thru columns (elements of a sublist)
    for c in rng_ls:
        # retain 1st sublist, which contains IDs
        if r == 0:
            output[r].append(str(Ap[r][c]) + '^' + str(Bu[l_urx[r]][l_ux[c]]))
        else:
            # retain 1st elements in each row: they uniquely id rows
            if c == 0:
                output[r].append(str(Ap[r][c]) + '^' + str(Bu[l_urx[r]][l_ux[c]]))
            else:
                if Ap[r][c]== Bu[l_urx[r]][l_ux[c]]:
                    output[r].append ('ok^ok')
                else:
                    output[r].append(str(Ap[r][c]) + '^' + str(Bu[l_urx[r]][l_ux[c]]))