Why is the dictionary lookup not faster in this case?

Question

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()

Answer 1

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()