Detecting changes to a dict

[CTO]

On Sep 28, 1:11 am, Steven D'Aprano
<ste... at REMOVE.THIS.cybersource.com.au> wrote:
> 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

If you can enumerate the language of possible inputs you could
generate a unique binary representation. Against a language of size
l that would only take you O(l*n) to build the repr for a dict
and for certain repr sizes the comparison could be O(1), making
the entire operation O(l*n+l*m) vs O(n*m).

Geremy Condra