dictionary speed

This entry got me thinking.

Here's my 5 cents. In all cases the construct

if key in dictionary:
    value = dictionary[key]
else:
    value = default

performed best.

update: I increased the amount of data to reduce the amount of white-noise in the test results, though things haven't changed. An explanation to the output. The programm compares nine data-sets against four test functions. The nine data sets are the combinations of size-distribution between search/dictionary and size-distribution between search and matching keysets ( thereof the small/even/big combinations ).

update2: Why, the version of python is 2.4 of course :)

Here's the output of the programm.

big dict, small search, big intersect
 test_has_key         0.9690
 test_get             1.0000
 test_try             1.2190
 test_in              0.5930
big dict, small search, small intersect
 test_has_key         0.8750
 test_get             1.0320
 test_try             6.6250
 test_in              0.5150
big dict, small search, half intersect
 test_has_key         0.9220
 test_get             1.0310
 test_try             3.9530
 test_in              0.5470
even, big intersect
 test_has_key         1.4370
 test_get             1.4840
 test_try             1.7030
 test_in              1.0780
even, small intersect
 test_has_key         1.4530
 test_get             1.6090
 test_try             7.3120
 test_in              1.0780
even, half intersect
 test_has_key         1.4690
 test_get             1.5620
 test_try             4.5630
 test_in              1.0780
small dict, big search, big intersect
 test_has_key         0.1090
 test_get             0.1250
 test_try             0.7970
 test_in              0.0630
small dict, big search, small intersect
 test_has_key         1.0790
 test_get             1.2180
 test_try             7.0160
 test_in              0.7340
small dict, big search, half intersect
 test_has_key         0.5790
 test_get             0.6560
 test_try             3.8440
 test_in              0.3910

and that's the programm

import sys, time

def random_key( keylen = 10 ):
    import random
    return ''.join(chr(random.randint(ord('a'),ord('z'))) for _ in range( keylen ))

def new_key( existing_keys ):
    key = random_key()
    while key in existing_keys:
        key = random_key()
    return key

def unique_keys( amount=1000, existing_keys=set() ):
    keys = set( existing_keys )
    for _ in xrange( amount ):
        key = new_key( keys )
        keys.add( key )
    return keys-existing_keys

def data( dictionary_size=1000, search_size=3000, intersection=0.5 ):
    dict_keys = unique_keys( dictionary_size )
    intersection_amount = int(search_size*intersection)
    unique_search_keys = unique_keys( search_size-intersection_amount, dict_keys )
    intersection_search_keys = set(list(dict_keys)[0:intersection_amount])
    return dict((key,None) for key in dict_keys), unique_search_keys | intersection_search_keys


def core_test( out_prefix, dictionary, searched, test_functions ):
    print out_prefix
    for function in test_functions:
        start = time.time()
        for _ in range( 20*(len(dictionary)/len(searched) or 1) ):
            function( dictionary, searched, None )
        end = time.time()
        print '\t%-20s %2.4f'%(function.__name__, end-start)

def inner_test( out_prefix, dictionary_size, search_size, test_functions ):
    #big intersection
    dictionary, search = data( dictionary_size, search_size, 0.9 )
    core_test( '%s, big intersect'%out_prefix, dictionary, search, test_functions )
    #small intersection
    dictionary, search = data( dictionary_size, search_size, 0.1 )
    core_test( '%s, small intersect'%out_prefix, dictionary, search, test_functions )
    #half intersection
    dictionary, search = data( dictionary_size, search_size, 0.5 )
    core_test( '%s, half intersect'%out_prefix, dictionary, search, test_functions )


#test functions
def test_has_key( dictionary, searched, default ):
    for key in searched:
        if dictionary.has_key( key ):
            value = dictionary[key]
        else:
            value = default

def test_get( dictionary, searched, default ):
    for key in searched:
        value = dictionary.get(key, default)

def test_try( dictionary, searched, default ):
    for key in searched:
        try:
            value = dictionary[key]
        except KeyError:
            value = default

def test_in( dictionary, searched, default ):
    for key in searched:
        if key in dictionary:
            value = dictionary[key]
        else:
            value = default

def test():
    factor = 100
    test_functions = [test_has_key, test_get, test_try, test_in]
    #big dict, small search, small
    inner_test( 'big dict, small search', 1000*factor, 1*factor, test_functions )

    #even dict/search
    inner_test( 'even', 1000*factor, 1000*factor, test_functions )

    #small dict, big search
    inner_test( 'small dict, big search', 1*factor, 1000*factor, test_functions )

if __name__ == '__main__':
    test()