Should I use a dictionary for membership testing?

Question

Suppose I have two lists A, B such that A is a subset of B. If I were to parse through the points of B and each time I want to test if an element is a member of A, would representing A as a dictionary be better than as a list? I ask because I am under the impression that dictionaries have worst case lookup time O(1), whereas for arrays it is O(n).

That is, which of the following would be more efficient in terms of time complexity?

# Code 1
A = [1, 2, 3]
B = [1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 1, 2, 3]

for i in B:
    if i in A:
        print (i)
    else:
        print (-1)

# Code 2
A = [1, 2, 3]
B = [1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 1, 2, 3]

A_dict = {}
for i in A:
    A_dict[i] = 0

for i in B:
    if i in A_dict:
        print (i)
    else:
        print (-1)

It seems that if what I said about time complexities above is true, then the first code has complexity O(|B| x |A|), whereas the second has complexity O(|B|). Is this correct?

Answer 1

You should use sets for that. They have O(1) lookup, like dicts, but they aren't key-value pairs.

Your code would then look like this:

A = [1, 2, 3]
B = [1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 1, 2, 3]

A_set = set(A)

for i in B:
    if i in A_set:
        print (i)
    else:
        print (-1)

or:

A = {1, 2, 3}
...