Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Date: Mon, 17 Dec 2012 20:09:01 -0500
From: Mitya Sirenef <msirenef@lightbird.net>
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>
In-Reply-To: <50CF95FB.6060800@davea.name>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.1005.1355793018.29569.python-list@python.org>
Lines: 52
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:35032

On 12/17/2012 05:00 PM, 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.
>
> 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.
>
>

Thanks, this is quite interesting..


-- 
Lark's Tongue Guide to Python: http://lightbird.net/larks/