algorithm - Comparing two lists of coordinates in python and using coordinate values to assign values

Question

I have two sets of data taken from two separate import files which are both being imported into python and have currently been placed in lists as follows.

List 1 is in the form:

(reference number, x coordinate, y coordinate)

Example list 1: [[1, 0, 0], [2, 0, 10], [3, 0, 20], [4, 0, 30], [5, 0, 40]]

List 2 is in the form:

(x coordinate, y coordinate, temperature)

Example list 2: [[0, 0, 100], [0, 10, 110], [0, 20, 120], [0, 30, 130], [0, 40, 140]]

I need to compare the two lists using the x and y coordinates and if they find a match produce a new list containing the corresponding reference number and temperature.

for example from the two lists above the output list would follow the form:

(reference number, temperature)

Example Output list: [[1, 100], [2, 110], [3, 120], [4, 130], [5, 140]]

This is to be done with a large amount of data and I am really struggling to find a solution, any help would be really appreciated. Cheers

Answer 1

This works 0(n^2) but it is very easy to read and understand.

 result = []
 for reference, x, y in list1:
     for a, b, temperature in list2:
         if x == a and y == b:
             result.append([temperature, reference])

You can reduce the complexity to 0(n) by iterating over the lists and store coordinates in a dict as follows:

 dict1 = {}
 for reference, x, y in list1:
     dict[(x, y)] = reference

 dict2 = {}
 for x, y, temperature in list2:
     dict2[(x, y)] = temperature

 result = []
 for coordinate, reference in dict1.iteritems():
     temperature = dict2.get(coordinate)
     if temperature:
         result.append([temperature, reference])