How to find the difference of two arrays.

Question

I am working to find if a list has changed in python. The list contained a list inside each of its elements. Like this,

[[0,1,2,3],[2,7,3,4]]

Now image the list is longer and much bigger than this. I wonder is there a way I could find if this list has changed?

For an instance, [[0,1,2,3],[2,7,3,4]] > [[0,2,1,3],[2,7,3,4]]

As you can see, the list has changed.

My original idea is subtracting each elements of the list and if the number of the 0, say x - x = 0, is equals to the total elements of the list, say 100 elements. Then the list has not changed. If the difference is less than the total length of the list, then the list has changed.

However, by doing so, I am creating an extremely long processing time given the list is big.

What is your thoughts on this? What would you do differently to make the time shorter given this on any programming languages.

Thank you.

Answer 1

In Python use the following function (this can be easily translated into other languages):

from numbers import Number

def testEquality(elem1, elem2):
    if isinstance(elem1, list) and isinstance(elem2, list):
        # we are comparing two lists
        len1 = len(elem1)
        if len1 != len(elem2):
            return False
        for i in range(0, len1):
            if not testEquality(elem1[i], elem2[i]):
                return False
        return True
    elif isinstance(elem1, Number) and isinstance(elem2, Number):
        # we are comparing numbers
        return elem1 == elem2
    else:
        # we are comparing different types 
        return False

The function will work not only for simple list-of-lists of depth 2 (your example) but also for structures made of lists and numbers of arbitrary depth and composition. It will also fail early - it stops when it finds the first pair of elements that do not match.

The approach is recursive. First we test if we are comparing lists. If true, we'll check the length of both lists. If they do not match, the function will return $False$. If they do match, the function will recursively compare items from the lists.

If we are comparing numbers it's very easy to detect if we have a match or not. In all other cases, we are comparing different types (a list with a number, for example) and the answer is automatically $False$ (check the last example).

Some tests:

list1 = [[0,1,2,3],[2,7,3,4]]
list2 = [[0,1,2,3],[2,7,3,4]]
list3 = [[0,1,2,3],[2,7,4,3]]
list4 = [[0,1,2,3],[2,7,[4],3]]

print(testEquality(list1, list2)) # True
print(testEquality(list1, list3)) # False
print(testEquality(list1, list4)) # False