Detecting changes to a dict
Steven D'Aprano
steven at REMOVE.THIS.cybersource.com.au
Mon Sep 28 01:11:16 EDT 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