Membership test in List vs Set

Hi Pythonistas!,

Today we are going to discuss the performance comparison of in operator using list and set.

Let us dive into the code.

Code

import timeit
import random

item_set = set(range(1000))
item_list = list(range(1000))

def using_set():
    number = random.randint(1, 2000)
    return number in item_set

def using_list():
    number = random.randint(1, 2000)
    return number in item_list

Analysis using timeit module

time_taken = timeit.timeit(using_set, number=1000_000)
print("Time taken by the function using_set is: ", time_taken)

time_taken = timeit.timeit(using_list, number=1000_000)
print("Time taken by the function using_list is: ", time_taken)

Output

Time taken by the function using_set is:  0.5206331130000308
Time taken by the function using_list is:  4.244615108000062

Why

We can see that set is very faster compared to list for membership testing. Because the set is internally created using hashtables and list is created using dynamic array. In hashtables searching is O(1) but in array is O(n).

Note: Don't use set everywhere because iterating over set is slower that list. So use set or list according to your requirement

Hope you have learned something from this post. Please feel to contact us at afsal@parseltongue.co.in