{
  "$type": "site.standard.document",
  "canonicalUrl": "https://rednafi.com/python/create-sub-dict/",
  "description": "Optimize Python dictionary slicing from O(DK) to O(K) complexity using direct key lookups instead of iterating through all items.",
  "path": "/python/create-sub-dict/",
  "publishedAt": "2022-01-30T00:00:00.000Z",
  "site": "at://did:plc:fgtm2c26vfcj74rfmeggbyqj/site.standard.publication/3mnl6f7ob462z",
  "tags": [
    "Python",
    "TIL"
  ],
  "textContent": "How'd you create a sub dictionary from a dictionary where the keys of the sub-dict are\nprovided as a list?\n\nI was reading a [tweet by Ned Bachelder] on this today and that made me realize that I\nusually solve it with O(DK) complexity, where K is the length of the sub-dict keys and\nD is the length of the primary dict. Here's how I usually do that without giving it any\nthoughts or whatsoever:\n\nThis prints:\n\nWhile this works fine, if you look carefully you'll notice that in the above snippet, the\ncomplexity of creating the sub-dict is O(DK). This means, in the worst-case scenario, it'll\nhave to traverse the entire length of the main-dict and all the keys of the sub-dict to\ncreate the sub-dict. We can do better. Consider this:\n\nIt prints out the same thing as before:\n\nIt's quite a bit faster because in the worst case scenario, it'll only have to traverse the\nentire sub_keys list - O(K) complexity achieved. This is so simple and elegant. How did I\nmiss that! There's another functional but subjectively less readable way of achieving the\nsame thing. Here you go:\n\nBenchmarks\n\nI ran this naive benchmark in an ipython console:\n\nIt shows that the solution I was using does suffer from the effects of O(DK) complexity\neven when the dict size is as small as 9 elements. The second solution is the fastest and\nthe least complex one to understand. While the third one is better than the first solution,\nit's a gratuitously complex way of doing something so trivial.\n\nFurther reading\n\n- [Second solution from a comment on the same tweet]\n\n\n\n\n[tweet by Ned Bachelder]:\n    https://twitter.com/nedbat/status/1487084661163626506\n\n[second solution from a comment on the same tweet]:\n    https://twitter.com/__mharrison__/status/1487087733633781766/photo/1",
  "title": "Create a sub dictionary with O(K) complexity in Python"
}