Path: csiph.com!usenet.pasdenom.info!goblin3!goblin.stu.neva.ru!rt.uk.eu.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Date: Mon, 17 Dec 2012 21:13:17 -0500
From: Dave Angel <d@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:16.0) Gecko/20121011 Thunderbird/16.0.1
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: Delete dict and subdict items of some name
References: <943dbf16-1cd1-4844-a666-d8863f5941f8@googlegroups.com> <50CF59DE.6080608@lightbird.net> <50CF64B8.6010305@tim.thechases.com> <50CF8FBC.9000100@lightbird.net> <50CF95FB.6060800@davea.name> <50CFA5E7.7020701@mrabarnett.plus.com>
In-Reply-To: <50CFA5E7.7020701@mrabarnett.plus.com>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Precedence: list
Reply-To: d@davea.name
Newsgroups: comp.lang.python
Message-ID: <mailman.1007.1355796826.29569.python-list@python.org>
Lines: 51
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:35034

On 12/17/2012 06:08 PM, MRAB wrote:
> On 2012-12-17 22:00, Dave Angel wrote:
>> 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.
>>
> Wouldn't a set of the id of the visited objects work?

Sure.  But the set will get lots larger than a list, which is limited to
the depth of max recursion.  It also locks a lot more objects in memory,
where the list only locks one per level.

Now, maybe if the search is depth-first, and if you prune the set on the
way back up, then it'll be space efficient.



-- 

DaveA