Efficiency question: how to compare two huge nested lists and make changes based on criteria

Duon 0
Viewed 28

I want to compare two huge identical nested lists and by iterating over both of them. I'm looking for nested lists in where list_a[0] is equal to list_b[1]. In that case I want to merge those lists (the order is important). The non-matches lists I also want in the output.

rows_a = [['a', 'b', 'z'], ['b', 'e', 'f'], ['g', 'h', 'i']]  
rows_b = [['a', 'b', 'z'], ['b', 'e', 'f'], ['g', 'h', 'i']]

data = []  

for list_a in rows_a:  
    for list_b in rows_b:  
        if list_a[0] == list_b[1]:  
            list_b.extend(list_a)     
            data.append(list_b)  
        else:  
            data.append(list_b)

#print(data): [['a', 'b', 'z', 'b', 'e', 'f'], ['b', 'e', 'f'], ['g', 'h', 'i'], ['a', 'b', 'z', 'b', 'e', 'f'], ['b', 'e', 'f'], ['g', 'h', 'i'], ['a', 'b', 'z', 'b', 'e', 'f'], ['b', 'e', 'f'], ['g', 'h', 'i']]

Above is the output that I do NOT want, because it is way too much data. All this unnecessary data is caused by the double loop over both rows. A solution would be to slice an element off rows_b by every iteration of the for loop on rows_a. This would avoid many duplicate comparisons. Question: How do I skip first element of a list every time it has looped from start to end?

In order to show the desired outcome, I correct the outcome by deleting duplicates below:

res=[]
for i in data:
    if tuple(i) not in res:
        res.append(tuple(i))
        
print(res)

#Output: [('a', 'b', 'z', 'b', 'e', 'f'), ('b', 'e', 'f'), ('g', 'h', 'i')]

This is the output I want! But faster...And preferably without removing duplicates.

I managed to get what I want when I work with a small data set. However, I am using this for a very large data set and it gives me a 'MemoryError'. Even if it didn't give me the error, I realise it is a very inefficient script and it takes a lot of time to run.

Any help would be greatly appreciated.

coding-efficiency performance python
1 Answers

tuple(i) not in res is not efficient since it iterate over the whole list over and over in linear time resulting in a quadratic execution time (O(n²)). You can speed this up using a set:

list({tuple(e) for e in data})

This does not preserve the order. If you want to do that, then you can use a dict (requires a quire recent version of Python):

list({tuple(e): None for e in data}.keys())

This should be significantly faster. An alternative solution is to convert the element to tuple, then sort them and compare close pairs of values so to remove duplicates. Note you can also merge two set or two dict with the update method.

As for the memory space, there is not much to do. The problem is CPython itself which is clearly not designed for computing large data with such data structure (only native data structures like Numpy arrays are efficient). Each character is encoded as a Python object taking 24-32 bytes. Lists contains references to objects taking 8 bytes each on a 64-bit architecture. This means 40 bytes per characters while 1 byte is actually needed (and this is what a native C/C++ program can actually use in practice). That being said CPython can cache 1-byte character so to use "only" 8 byte per character in this specific case (which is still 8 time more than required). If you use list of characters in your real-world application, please consider using string instead. Otherwise, please consider using another language.

Jérôme Richard0
Related