Why is the dictionary lookup not faster in this case?

I recently asked about the fastest way to create powers of ten, and it turned out that the fastest way is actually a bit of a sneaky workaround, where you create all the possible values first, and then simply look them up whenever you need them.

In the solution, a list was used as the lookup-table, however, I’ve just learned that dicts should be much faster when it comes to lookup operations (see e.g. also here). But when I tried out a dict as the lookup table, the process was actually slower:

n = 200
 18 ns   18 ns   18 ns  f[n]  # list
 22 ns   22 ns   22 ns  g[n]  # dict

n = -200
 18 ns   18 ns   18 ns  f[n]  # list
 29 ns   29 ns   29 ns  g[n]  # dict

Why is that? Does it have to do with the fact that the keys are integers and not strings? (Also I guess sets cannot be used in this case?)

Here is the code I ran:

from timeit import repeat


solutions = [
    'f[n]  # list',
    'g[n]  # dict',
]

for n in 200, -200:
    print(f'n = {n}')
    setup = f'''
n = {n}
f = [10.0 ** i for i in [*range(309), *range(-323, 0)]]
g = {{i: 10.0 ** i for i in range(-323, 309)}}
'''
    for solution in solutions:
        try:
            ts = sorted(repeat(solution, setup, repeat=50))[:3]
        except OverflowError:
            ts = [None] * 3
        print(
            *('%3d ns ' % (t * 1e3) if t else ' error ' for t in ts), solution
        )
    print()

>Solution :

collection[key_or_index] is O(1) for both list and dict. What is different is the performance of key_or_value in collection.

It’s the difference between "What is the ith power of ten in my list?" versus "Is x a power of ten that is in my list?"

Indexing is slightly faster for list because dictionaries need to calculate the hash of their key, as well as check for collisions.


The confusion is because "lookup" can refer both to the indexing operation as well as checking for presence, depending on the context.


Here is an overview of how to do the equivalent operation in both lists and dictionaries:

List Dictionary
Indexing lst[i] dct[key]
Checking for presence of key/index -len(lst) <= i < len(lst) key in dct
Checking for presence of value value in lst value in dct.values()
Looping over values for value in lst for value in dct.values()
Looping over keys/indexes for i in range(len(lst)) for key in dct
Looping over both for i, value in enumerate(lst) for key, value in dct.items()

Leave a Reply