Detecting changes to a dict

[Steven D'Aprano]

I'm pretty sure the answer to this is No, but I thought I'd ask just in
case...

Is there a fast way to see that a dict has been modified? I don't care
what the modifications are, I just want to know if it has been changed,
where "changed" means a key has been added, or deleted, or a value has
been set. (Modifications to mutable values aren't important.) In other
words, any of these methods count as modifying the dict:

__setitem__
__delitem__
clear
pop
popitem
setdefault
update

Of course I can subclass dict to do this, but if there's an existing way,
that would be better.

 

[Simon Forman]

I'm pretty sure the answer to this is No, but I thought I'd ask just in
case...

Is there a fast way to see that a dict has been modified? I don't care
what the modifications are, I just want to know if it has been changed,
where "changed" means a key has been added, or deleted, or a value has
been set. (Modifications to mutable values aren't important.) In other
words, any of these methods count as modifying the dict:

__setitem__
__delitem__
clear
pop
popitem
setdefault
update

Of course I can subclass dict to do this, but if there's an existing way,
that would be better.

Depending on what you're doing you could use something like this:

(Note that it doesn't work on empty dicts, and you'd have to "reset
it" if your dict ever became empty after processing.)

def f(d):
while True:
i = iter(d).next
try:
while True:
try:
i()
except RuntimeError:
yield True
break
else:
yield False
except StopIteration:
if not d:
break # else we'd enter an infinite loop.


In [1]: d = {23: 18}

In [2]: check = f(d).next

In [3]: check()
Out[3]: False

In [4]: d['cats'] = 'lol'

In [5]: check()
Out[5]: True

In [6]: check()
Out[6]: False

In [7]: d.clear()

In [8]: check()
Out[8]: True

In [9]: check()
---------------------------------------------------------------------------
StopIteration Traceback (most recent call last)

/home/sforman/<ipython console> in <module>()

StopIteration:



HTH,
~Simon

 

[CTO]

I'm pretty sure the answer to this is No, but I thought I'd ask just in
case...

Is there a fast way to see that a dict has been modified? I don't care
what the modifications are, I just want to know if it has been changed,
where "changed" means a key has been added, or deleted, or a value has
been set. (Modifications to mutable values aren't important.) In other
words, any of these methods count as modifying the dict:

__setitem__
__delitem__
clear
pop
popitem
setdefault
update

Of course I can subclass dict to do this, but if there's an existing way,
that would be better.

d = {"a": "b", "c": "d"}
d2 = d.copy()
assert d == d2
d["e"] = "f"
assert d == d2

Is this what you're looking for?

Geremy Condra

 

[Steven D'Aprano]

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.

 

[CTO]

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.

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