CODEWITHSUNDEEP
pythonpython-3.xtime-complexity
green frog
green frog

Reputation: 166

Should I use a dictionary for membership testing?

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?

Upvotes: 3

Views: 968

Answers (1)

Maximouse
Maximouse

Reputation: 4383

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}
...

Upvotes: 3

Related Questions