4

I was working on a piece of code which requires dictionary comparison, I am curious about the time complexity of it. How does python implement dictionary comparison?

if Dict_1 == Dict_2:
    do something
Steve Yang
  • 41
  • 4
  • It's a recursive lookup, depends on your dict values. https://stackoverflow.com/questions/1911273/is-there-a-better-way-to-compare-dictionary-values/5635309#5635309 – knh190 Apr 11 '19 at 08:23
  • If the recursion takes too long, try this DiffDicter library that is used to find the diff between two dictionaries. I have not timed it but may be faster - https://dictdiffer.readthedocs.io/en/latest/ – Nick Apr 11 '19 at 08:34

1 Answers1

2

It is recursively compares pairs key:value in dicts, so in theory the comparison time should be equal to number_of_all_recursive_items * time_to_check_one_item (of course I am looking at the worst case - when dicts are equal and all pairs are checking). But in practice there is many pitfalls. Look at this picture:

enter image description here

It is the dict_length-time graph for flat dicts. Moreover, you can look at the comparison of the nested dict:

enter image description here

So you can't guarantee that your comparison will spend a particular amount of time. But usually - yes, there is a linear connection between recursive dict length and comparison time.

vurmux
  • 9,420
  • 3
  • 25
  • 45