dict: retrieve the original key by key

[Terry Reedy]

On 5/15/2011 6:46 AM, Christoph Groth wrote:
> Steven D'Aprano<steve+comp.lang.python at pearwood.info>  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