Each Answer to this Q is separated by one/two green lines.
I’ve got a large dictionary from which I have to look up for values a lot of times. My keys are integers but represent labels so do not need to be added, subtracted, etc… I ended up trying to assess access time between string key and integer key dictionary and here is the result.
from timeit import Timer Dint = dict() Dstr = dict() for i in range(10000): Dint[i] = i Dstr[str(i)] = i print 'string key in Dint', print(Timer("'7498' in Dint", "from __main__ import Dint").timeit(100000000)) print 'int key in Dint', print(Timer("7498 in Dint", "from __main__ import Dint").timeit(100000000)) print 'string key in Dstr', print(Timer("'7498' in Dstr", "from __main__ import Dstr").timeit(100000000)) print 'int key in Dstr', print(Timer("7498 in Dstr", "from __main__ import Dstr").timeit(100000000))
which produces slight variations between runs reproduced each time :
string key in Dint 4.5552944017 int key in Dint 7.14334390267 string key in Dstr 6.69923791116 int key in Dstr 5.03503126455
Does it prove that using dictionary with strings as keys is faster to access than with integers as keys?
dict implementation is in fact optimized for string key lookups. There are two different functions,
lookdict_unicode in Python 3), which can be used to perform lookups. Python will use the string-optimized version until a search for non-string data, after which the more general function is used. You can look at the actual implementation by downloading CPython’s source and reading through
As a result of this optimization, lookups are faster when a
dict has all string keys.
I’m afraid your times don’t really prove very much.
Your test for string in Dint is fastest: in general a test for anything that is not in a dictionary is quite likely to be fast, but that’s only because you were lucky and first time hit an empty cell so the lookup could terminate. If you were unlucky and chose a value that hit one or more full cells then it could end up slower than the cases that actually find something.
Testing for an arbitrary string in a dictionary has to calculate the hash code for the string. That takes time proportional to the length of the string, but Python has a neat trick and only ever calculates it once for each string. Since you use the same string over and over in your timing test the time taken to calculate the hash is lost as it only happens the first time and not the other 99999999 times. If you were using a different string each time you would get a very different result.
Python has optimised code for dictionaries where the keys are strings. Overall you should find that using string keys where you use the same keys multiple times is slightly faster, but if you have to keep converting integers to string before the lookup you’ll lose that advantage.
This was my question too. Apparently, dictionaries with string keys are more efficient, but access times are really close. I ran the following code using Python 3:
import random import timeit import uuid DICT_INT = dict() DICT_STR = dict() DICT_MIX = dict() for i in range(2000000): DICT_INT[i] = uuid.uuid4().hex DICT_STR[str(i)] = uuid.uuid4().hex DICT_MIX[i if random.randrange(2) else str(i)] = uuid.uuid4().hex def int_lookup(): int_key = random.randrange(len(DICT_INT)) str_key = str(int_key) mix_key = int_key if int_key % 2 else str_key return int_key in DICT_INT def str_lookup(): int_key = random.randrange(len(DICT_STR)) str_key = str(int_key) mix_key = int_key if int_key % 2 else str_key return str_key in DICT_STR def mix_lookup(): int_key = random.randrange(len(DICT_MIX)) str_key = str(int_key) mix_key = int_key if int_key % 2 else str_key return mix_key in DICT_MIX print('Int dict lookup: ', end='') print(timeit.timeit('int_lookup', 'from __main__ import int_lookup', number=1000000000)) print('Str dict lookup: ', end='') print(timeit.timeit("str_lookup", 'from __main__ import str_lookup', number=1000000000)) print('Mix dict lookup: ', end='') print(timeit.timeit("mix_lookup", 'from __main__ import mix_lookup', number=1000000000))
and this is the result:
Int dict lookup: 12.395361029000014 Str dict lookup: 12.097380312000041 Mix dict lookup: 12.109765773000163