Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Re: dict: retrieve the original key by key

Reply
Thread Tools

Re: dict: retrieve the original key by key

 
 
Christoph Groth
Guest
Posts: n/a
 
      05-15-2011
Chris Rebert <(E-Mail Removed)> writes:

> On Sun, May 15, 2011 at 1:28 AM, Christoph Groth <(E-Mail Removed)> wrote:
>> I use a huge python dictionary where the values are lists of that
>> dictionary's keys (yes, a graph). *Each key is thus referenced
>> several times.
>>
>> As the keys are rather large objects, I would like to save memory by
>> re-using key objects wherever possible, instead of having several
>> equal objects in memory.
>>
>> There does not seem to be a way to retrieve the original key from a
>> python dictionary. *Is there a technical reason for this? *(Other
>> than that such functionality was not considered to be useful enough.)

>
> Define "original key".


def original_key(dictionary, key):
for k in dictionary:
if k == key:
return k
raise KeyError(key)

But this is not efficient.

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.

 
Reply With Quote
 
 
 
 
Steven D'Aprano
Guest
Posts: n/a
 
      05-15-2011
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.


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.


--
Steven
 
Reply With Quote
 
 
 
 
Christoph Groth
Guest
Posts: n/a
 
      05-15-2011
Steven D'Aprano <(E-Mail Removed)> 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.

>
> 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.

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.

Thanks a lot for the hint!

Christoph

 
Reply With Quote
 
Terry Reedy
Guest
Posts: n/a
 
      05-15-2011
On 5/15/2011 6:46 AM, Christoph Groth wrote:
> Steven D'Aprano<(E-Mail Removed)> 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

 
Reply With Quote
 
Chris Rebert
Guest
Posts: n/a
 
      05-15-2011
On Sun, May 15, 2011 at 1:53 PM, Terry Reedy <(E-Mail Removed)> wrote:
> On 5/15/2011 6:46 AM, Christoph Groth wrote:

<snip>
>> 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.


Still exists in sys module though:
http://docs.python.org/dev/library/sys.html#sys.intern

Cheers,
Chris
 
Reply With Quote
 
Ian Kelly
Guest
Posts: n/a
 
      05-16-2011
On Sun, May 15, 2011 at 4:18 AM, Steven D'Aprano
<(E-Mail Removed)> wrote:
> 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.

>
> Based on the idea of interning, which is used for Python strings:
>
> cache = {}
> def my_intern(obj):
> * *return cache.setdefault(obj, obj)


And if the idea of a dictionary with identical keys and values
offends, you can also use a set:

cache = set()
def my_intern(obj):
cache.add(obj)
return cache.intersection([obj]).pop()

Cheers,
Ian
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
dict: retrieve the original key by key Christoph Groth Python 0 05-15-2011 08:28 AM
How do I retrieve original text format? Moz Tunnel Computer Information 1 08-05-2009 05:01 PM
Replace Tab Key to Return Key (Enter Key) from Web Forms? M P ASP General 1 08-06-2004 08:32 AM
Retrieve lost product key. =?Utf-8?B?anls?= Microsoft Certification 1 05-04-2004 01:27 AM



Advertisments