Python - set vs. list in a special case

Question

I need to store tuples. Everytime I add a tuple, I need to know whether the tuple was added or already existed, because if it already existed (in the list/set) I can break the inner for loop, so I do not have to check several other tuples.

My idea was to use a set, since the add-operation checks if the tuple is already there. But since there is no return value, I would have to check myself if the tuple is already in the set. So I would check and the add-operation would check again.

So is it faster to use a list, because I have to check myself anyway? So I would check if the tuple is already in the list and if not I would just append the tuple.

Answer 1

You should use a set, and test for membership:

if mytuple in set_of_tuples:
    break  # already added

set_of_tuples.add(mytuple)

Testing for membership against a set takes constant time (O(1)), while testing against a list takes linear time (O(N), each element in the list is tested against).

In other words, you do have to test if the tuple is in the data structure already, but testing against a list gets slower and slower, while testing against a set always takes the same amount of time, regardless of how many tuples are already in there.