Delete dict and subdict items of some name

[Dave Angel]

On 12/17/2012 04:33 PM, Mitya Sirenef wrote:
> On 12/17/2012 01:30 PM, Tim Chase wrote:
>> On 12/17/12 11:43, Mitya Sirenef wrote:
>>> On 12/17/2012 12:27 PM, Gnarlodious wrote:
>>>> Hello. What I want to do is delete every dictionary key/value
>>>> of the name 'Favicon' regardless of depth in subdicts, of which
>>>> there are many. What is the best way to do it?
>>> Something like this should work:
>>>
>>> def delkey(d, key):
>>>       if isinstance(d, dict):
>>>           if key in d: del d[key]
>>>           for val in d.values():
>>>               delkey(val, key)
>> Unless you have something hatefully recursive like
>>
>>    d = {}
>>    d["hello"] = d
>>
>> :-)
>
> True -- didn't think of that..!
>
> I guess then adding a check 'if val is not d: delkey(val, key)'
> would take care of it?
>
No, that would only cover the self-recursive case.  If there's a dict
which contains another one, which contains the first, then the recursion
is indirect, and much harder to check for.

Checking reliably for arbitrary recursion patterns is tricky, but
do-able.  Most people degenerate into just setting an arbitrary max
depth.  But I can describe two approaches to this kind of problem.

1) build a list of the recursion path at present, and compare against
the whole path, rather than just the tail.  If there are any matches, quit.

2) make the iterator an object, and instantiate two of them.  Then each
recursive level, iterate the main one once, and the secondary one
twice.  If the two ever match, you have a loop.  Deciding what to do at
that point is tricky because you may have processed some nodes multiple
times already.  But at least it'll terminate, and it doesn't use linear
memory to do so.  I call this one the lollypop algorithm.


-- 

DaveA