Python - Copy missing elements from one list into another

Question

I am looking for the most efficient way to update a list.

I have a variable self.myGlobalList = []

I also have a recursive function that on each one of its calls is going to generate a new list with coordinates.

Say in the first iteration, I obtain the following list:

[(1,1), (21,22), (84,6)]

Since self.myGlobalList does not contain any of those coordinates, I will append them to it:

for elem in generatedList:
   if elem not in self.myGlobalList:
      self.myGlobalList.append(elem);

Then, on the second iteration I obtain a new generated list:

[(1,1), (21,22), (9,18), (71, 89), (13, 21)]

Now my code will again go through each element of the newly generated list and check if any are missing from self.myGlobalList, and if yes, append them. The result should contain the new elements:

[(1,1), (21,22), (84,6), (9,18), (71, 89), (13, 21)]

So far so good, everything works fine.

However, my lists can contain more than 500 000+ coordinates. In terms of efficiency, will this method be sufficient, and are there any suggestions you could offer in order to optimise it?

Answer 1

For instance you could do something like this (toy example):

iterations = [
    [(1, 1), (21, 22), (84, 6)], [(1, 1), (21, 22), (9, 18), (71, 89), (13, 21)]]

global_set = set()
global_list = []
for iteration in iterations:
    for pair in iteration:
        if pair not in global_set:
            global_list.append(pair)
            global_set.add(pair)

print(global_list)

Output

[(1, 1), (21, 22), (84, 6), (9, 18), (71, 89), (13, 21)]

Explanation

The expression if pair not in global_set is O(1) (that is it takes constant time to check if an element is present), in the other hand if pair not in global_list would take O(n) to check if an element is present.

Further

1. Python set.
2. List vs Set

Answer 2

Make each generated_list into a set, and then just keep performing union on the set. The repeated code should go into a loop.

myGlobal = set()

generated_list = [(1,1), (21,22), (84,6)]
myGlobal = myGlobal.union(set(generated_list))
print(myGlobal)

generated_list = [(1,1), (21,22), (9,18), (71, 89), (13, 21)]
myGlobal = myGlobal.union(set(generated_list))
print(myGlobal)

Output:

{(21, 22), (1, 1), (84, 6)}
{(21, 22), (71, 89), (84, 6), (9, 18), (1, 1), (13, 21)}