Create a sub dictionary with O(K) complexity in Python

How'd you create a sub dictionary from a dictionary where the keys of the sub-dict are provided as a list?

I was reading a tweet by Ned Bachelder on this today and that made me realize that I usually solve it with O(DK) complexity, where K is the length of the sub-dict keys and D is the length of the primary dict. Here's how I usually do that without giving it any thoughts or whatsoever:

This prints:

While this works fine, if you look carefully you'll notice that in the above snippet, the complexity of creating the sub-dict is O(DK). This means, in the worst-case scenario, it'll have to traverse the entire length of the main-dict and all the keys of the sub-dict to create the sub-dict. We can do better. Consider this:

It prints out the same thing as before:

It's quite a bit faster because in the worst case scenario, it'll only have to traverse the entire sub_keys list - O(K) complexity achieved. This is so simple and elegant. How did I miss that! There's another functional but subjectively less readable way of achieving the same thing. Here you go:

Benchmarks

I ran this naive benchmark in an ipython console:

It shows that the solution I was using does suffer from the effects of O(DK) complexity even when the dict size is as small as 9 elements. The second solution is the fastest and the least complex one to understand. While the third one is better than the first solution, it's a gratuitously complex way of doing something so trivial.

Further reading

• Second solution from a comment on the same tweet