Detecting changes to a dict

Steven D'Aprano steven at REMOVE.THIS.cybersource.com.au
Mon Sep 28 07:11:16 CEST 2009


On Sun, 27 Sep 2009 21:42:10 -0700, CTO wrote:

>> Is there a fast way to see that a dict has been modified?
...


> d = {"a": "b", "c": "d"}
> d2 = d.copy()
> assert d == d2
> d["e"] = "f"
> assert d == d2
> 
> Is this what you're looking for?

In general, no. I was hoping for an O(1) check. Yours test is only O(1) 
if the length of the dict changes[1], and probably O(N) otherwise. 
Perhaps I'm guilty of premature optimization, but the above simple check 
may be expensive in both space and time if the dict is very large and the 
modification doesn't change the length. If the dict is large enough, 
duplicating it may cause swapping, which is O(N**2) or worse.

In my case, the dict only has a few hundred items, so your suggestion is 
probably perfectly adequate for my specific need. But as a general 
solution, imagine checking a dict with tens of millions of key/values. If 
the length is different, that's a fast check. But if the length is the 
same, the equality test has to check every key/value pair in the dict 
(presumably bailing out early if it finds a difference).

For my specific need, I'll probably end up using your suggestion simply 
because I'm lazy and it's more convenient than writing a subclass.






[1] That is, I *assume* that dict equality checking uses that obvious 
optimization.


-- 
Steven



More information about the Python-list mailing list