Sunday, March 18, 2012

Sets and dictionaries in Python are faster than lists for `in` operations

A test:
import time, random

def create_list(n):
    return list(range(n))

def create_set(n):
    return set(range(n))

def create_dict(n):
    return dict(zip(range(n), range(n)))


def test(create_func_name, n):
    create_func = globals()['create_' + create_func_name]
    obj = create_func(n)
    
    t = time.time()
    
    for i in range(100000):
        random.randint(0, n - 1) in obj # test
        
    print("%s: %.3f" % (create_func_name, time.time() - t))

    
test('list', 1000)
test('set', 1000)
test('dict', 1000)
Test results:
vic@ubuntu:~/Desktop$ python test.py 
list: 0.752
set: 0.157
dict: 0.155
vic@ubuntu:~/Desktop$ 
As you see, looking for a key in sets and dicts is 5 times faster then looking for a key (item) in lists.
Sets are like dicts, but without values.

No comments:

Post a Comment