Performance comparison between set and list

When the amount of data in the set is particularly large , To determine whether an element is in the set , It is recommended to use set instead of list , The two performances differ greatly . Here's a test ：

from tqdm import tqdm
import random
import time

The construction length is length Array of

def construct_data(length):
    l = []
    for i in range(length):
        l.append(i)
    random.shuffle(l)
    return l, set(l)

test num Time

test list

length, num = int(1e6), int(1e4)
l, s = construct_data(length)
start_l = time.time()
for _ in tqdm(range(num)):
    r = random.randint(0, length-1)
    if r in l:
        pass
end_l = time.time()
print("test list time: {} seconds".format(end_l-start_l))

100%|██████████| 10000/10000 [02:52<00:00, 58.00it/s]

test list time: 172.42421102523804 seconds

​

test set

start_s = time.time()
for _ in tqdm(range(num)):
    r = random.randint(0, length-1)
    if r in s:
        pass
end_s = time.time()
print("test set time: {} seconds".format(end_s-start_s))

100%|██████████| 10000/10000 [00:00<00:00, 343595.45it/s]

test set time: 0.03251051902770996 seconds

​

You can see ,set Is really faster than list Much faster . After all set The underlying use hash Hash implementation , To find an element, in theory, just O(1) Time , and list Is the traversal , need O(n) Time . When the data volume is small , There is no difference between the two , The amount of data is a little larger , The gap is very clear .