Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #35019

Re: Delete dict and subdict items of some name

Show all headers | View raw

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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Delete dict and subdict items of some name Gnarlodious <gnarlodious@gmail.com> - 2012-12-17 09:27 -0800
  Re: Delete dict and subdict items of some name Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2012-12-17 17:42 +0000
  Re: Delete dict and subdict items of some name Mitya Sirenef <msirenef@lightbird.net> - 2012-12-17 12:43 -0500
  Re: Delete dict and subdict items of some name Paul Rubin <no.email@nospam.invalid> - 2012-12-17 09:48 -0800
  Re: Delete dict and subdict items of some name Dave Angel <d@davea.name> - 2012-12-17 12:50 -0500
  Re: Delete dict and subdict items of some name Tim Chase <python.list@tim.thechases.com> - 2012-12-17 12:30 -0600
  Re: Delete dict and subdict items of some name Mitya Sirenef <msirenef@lightbird.net> - 2012-12-17 16:33 -0500
  Re: Delete dict and subdict items of some name Chris Angelico <rosuav@gmail.com> - 2012-12-18 08:53 +1100
  Re: Delete dict and subdict items of some name Dave Angel <d@davea.name> - 2012-12-17 17:00 -0500
  Re: Delete dict and subdict items of some name MRAB <python@mrabarnett.plus.com> - 2012-12-17 23:08 +0000
  Re: Delete dict and subdict items of some name Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-12-18 00:17 +0000
  Re: Delete dict and subdict items of some name Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2012-12-18 00:22 +0000
  Re: Delete dict and subdict items of some name Mitya Sirenef <msirenef@lightbird.net> - 2012-12-17 20:09 -0500
  Re: Delete dict and subdict items of some name Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2012-12-17 23:44 +0000
  Re: Delete dict and subdict items of some name Dave Angel <d@davea.name> - 2012-12-17 21:13 -0500
  Re: Delete dict and subdict items of some name Gnarlodious <gnarlodious@gmail.com> - 2012-12-17 21:30 -0800
    Re: Delete dict and subdict items of some name Hans Mulder <hansmu@xs4all.nl> - 2012-12-18 11:31 +0100
      Re: Delete dict and subdict items of some name Gnarlodious <gnarlodious@gmail.com> - 2012-12-18 07:27 -0800
        Re: Delete dict and subdict items of some name Terry Reedy <tjreedy@udel.edu> - 2012-12-18 11:29 -0500

csiph-web