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(
            *('= ns ' % (t * 1e3) if t else ' error ' for t in ts), solution
        )
    print()

CodePudding user response：

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: