Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.000 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'cache': 0.04; 'rejected': 0.04; 'memory.': 0.05; 'algorithms': 0.07; 'cached': 0.07; 'dictionary': 0.07; 'terry': 0.07; 'though.': 0.07; 'python': 0.07; '+0200,': 0.09; '3.x': 0.09; 'collections': 0.09; 'dict': 0.09; 'graph': 0.09; 'object.': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:80.91.229.12': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'received:lo.gmane.org': 0.09; 'sun,': 0.09; '>>>': 0.12; 'def': 0.13; 'am,': 0.14; 'wrote:': 0.14; 'dictionary,': 0.16; 'does,': 0.16; 'equal,': 0.16; 'hashed': 0.16; 'identifiers,': 0.16; 'reedy': 0.16; 'stumbled': 0.16; 'subject:key': 0.16; 'far.': 0.19; 'writes:': 0.20; 'jan': 0.22; 'header:In-Reply-To:1': 0.22; 'values': 0.23; 'keys': 0.23; 'objects': 0.24; 'cases': 0.25; 'there.': 0.26; 'object': 0.27; 'changed': 0.27; 'function': 0.27; 'string': 0.29; 'minimal': 0.29; 'detail.': 0.31; 'strings,': 0.31; 'does': 0.31; 'however,': 0.31; 'equal': 0.31; 'entry': 0.32; 'to:addr:python-list': 0.32; 'another': 0.32; 'idea': 0.32; 'implemented': 0.33; 'maps': 0.33; 'sufficient': 0.33; 'test': 0.33; 'reference': 0.34; 'header:X-Complaints-To:1': 0.34; 'actually': 0.34; 'requires': 0.35; 'purposes': 0.35; 'header :User-Agent:1': 0.35; 'put': 0.35; 'accessing': 0.35; 'typical': 0.35; 'properties': 0.36; 'case,': 0.36; 'some': 0.37; 'identity': 0.38; 'proposed': 0.38; 'steven': 0.38; 'but': 0.38; 'used': 0.38; 'received:org': 0.38; 'set': 0.39; 'to:addr:python.org': 0.39; 'header:Mime-Version:1': 0.39; 'map': 0.40; 'would': 0.40; 'header:Received:5': 0.40; 'twice': 0.60; '2011': 0.62; 'property': 0.62; 'and,': 0.63; 'presented': 0.63; 'due': 0.67; 'collection': 0.71; 'hey,': 0.74; 'collection,': 0.84; 'dict,': 0.84; 'node': 0.84; 'subject:original': 0.84 X-Injected-Via-Gmane: http://gmane.org/ To: python-list@python.org From: Terry Reedy Subject: Re: dict: retrieve the original key by key Date: Sun, 15 May 2011 16:53:07 -0400 References: <874o4wwenu.fsf@falma.de> <4dcfa885$0$29996$c3e8da3$5496439d@news.astraweb.com> <87sjsgutqg.fsf@falma.de> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Gmane-NNTP-Posting-Host: rain.gmane.org User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2.17) Gecko/20110414 Lightning/1.0b2 Thunderbird/3.1.10 In-Reply-To: <87sjsgutqg.fsf@falma.de> X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 52 NNTP-Posting-Host: 82.94.164.166 X-Trace: 1305492800 news.xs4all.nl 41117 [::ffff:82.94.164.166]:60484 X-Complaints-To: abuse@xs4all.nl Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:5446 On 5/15/2011 6:46 AM, Christoph Groth wrote: > Steven D'Aprano writes: > >> On Sun, 15 May 2011 11:11:41 +0200, Christoph Groth wrote: >> >>> I would like to avoid having _multiple_ objects which are equal (a == >>> b) but not the same (a is not b). This would save a lot of memory. Python hashed collections have methods used to test if the collection has an item/key that is equal to some object. They do not currently have a method to return the equal item/key already there. This has been proposed and, I believe, rejected due to lack of sufficient presented use cases or because, conceptually, one wants to map key values to an object with the key value and Stephen's identity dict does precisely that. In any case, if you put an object into a collection and you want to use the object for other purposes without accessing the collection, you must keep a reference to it outside of the collection. >> Based on the idea of interning, which is used for Python strings: >> >> cache = {} def my_intern(obj): >> return cache.setdefault(obj, obj) >> >> >> x = make_some_object() x = my_intern(x) >> >> This ensures that equal objects in the graph are not just equal, but >> the same cached object. > > This requires another dictionary, though. It does, however, twice reuse the key already in your graph dict, so each entry is minimal extra memory. It is typical in graph algorithms to have both a graph map (nodes to set of nodes) and a properties map (nodes to property structure). Some properties are fixed, others are changed during particular algoritms. It is also typical to use counts as node identifiers, so that both maps are implemented as sequences, but string indentifiers and dict for maps work too. > But hey, they keys of my dictionary are actually strings, so I can use > the built-in intern. Somehow, I have never stumbled accross this > built-in function so far. It was, however, removed in 3.x as a seldom-externally-used internal implementation detail. -- Terry Jan Reedy