«

Thanks, looks interesting... but it actually doesn't really address the
question I was asking. It doesn't matter since I think the intern solution
is fine for me. But if I'm not mistaken, your solution still stores the
node names in the values of the dictionary (via the Node objects). So in
effect you do still have a dictionary of the form { 'node1name':
('node1name', other node1 data), 'node2name': ('node2name', other node2
data)). It doesn't seem as silly when you have a real node object, though.
In my application the nodes are really just strings; I don't need anything
else.

Andy

"Bengt Richter" <> wrote in message
news:bgho7i$790$0@216.39.172.122...
> On Sat, 02 Aug 2003 23:34:20 GMT, "Andy C" <> wrote:
>
> >> Google("intern-like memory saver").
> >
> >Well, that seems very sensical, so how come it hasn't made it into the
> >language? And what's wrong with intern? (Though intern only works on
> >strings, not for immutable objects in general. I believe someone was
asking
> >a pretty much identical question here, and someone replied with the
> >'memoize' pattern).
> >
> >Can this be done without C, now that you can subclass the built-in
> >dictionary?
> >
> For a subclass of dict that may be of interest, see my post in this thread
> timestamped less than 2 minutes before this post of yours
>
> Regards,
> Bengt Richter

On Sun, 03 Aug 2003 08:51:40 GMT, "Andy C" <> wrote:

>Thanks, looks interesting... but it actually doesn't really address the
>question I was asking. It doesn't matter since I think the intern solution
I thought it did

>is fine for me. But if I'm not mistaken, your solution still stores the
>node names in the values of the dictionary (via the Node objects). So in
No, just references, not duplicate strings.

>effect you do still have a dictionary of the form { 'node1name':
>('node1name', other node1 data), 'node2name': ('node2name', other node2
>data)). It doesn't seem as silly when you have a real node object, though.
>In my application the nodes are really just strings; I don't need anything
>else.
Well, don't you need the adjacency lists you were talking about? I assumed they were
all lists of out-edges associated with graph vertices. So I defined a Node class
with the two things: a name and an adj_list. You can eliminate the name reference
and just let the graph dict keys be the only reference, but then you will not
so conveniently have the name available to algorithms that process the nodes.
E.g., for some node myNode you might have to search the dict something like

for key,value in graph.items(): # untested!
if value is myNode: myName=key; break
else:
myName = "?? can't find name of %r ??'%myNode

One caveat though, if your graph has cycles, changing the adjacency lists to direct node
references instead of names will create reference cycles that may have to be broken for
the gc. I have to look into that. You can comment that fixup loop out if you want to
keep adjacency lists as name string references instead of node references.

BTW, have you looked at the sets module of 2.3? That would let you have a set of strings
with no associated values, and no duplicates (but how do you represent adjacency lists then?)

Anyway, unless I goofed, the { 'node1name''node1name', other node 1 data) } analogy is
not using two separate strings. It's more like the result of (untested!):

s = 'node1name'
graph.update({ ss, other node 1 data)}) # pseudo-tuple-element at graph[s][1]
del s

To check, I added the assert below, where it scans the node names in the
graph.show() method, and it didn't complain:

def show(self):
node_names = self.keys()
8< snip >8
for node_name in node_names:
assert node_name is self[node_name].name
prtree(self[node_name])
ret.append('')
return '\n'.join(ret)

Regards,
Bengt Richter

> >is fine for me. But if I'm not mistaken, your solution still stores the
> >node names in the values of the dictionary (via the Node objects). So in
> No, just references, not duplicate strings.

OK, you're right -- I assumed that the key and value were duplicated, but
that's not the case. I don't know why I thought that, maybe since the key
must be immutable and the value is mutable. So I guess having a dictionary
of the form { 'A': 'A', 'B': 'B' } is not as stupid as it first seems, since
only a reference is stored. But still I wonder why the language doesn't
have a facility for getting a reference to the key value in constant time.
Apparently someone did it by modifying the C source for the dictionary to
add a ref_key() accessor. It seems like it would be useful quite often.

> One caveat though, if your graph has cycles, changing the adjacency lists
to direct node
> references instead of names will create reference cycles that may have to
be broken for
> the gc. I have to look into that. You can comment that fixup loop out if
you want to
> keep adjacency lists as name string references instead of node references.

Good point... I thought though that the new python (2.3?) will GC data with
cycles.

> BTW, have you looked at the sets module of 2.3? That would let you have a
set of strings
> with no associated values, and no duplicates (but how do you represent
adjacency lists then?)

Actually, I did run across the sets type recently. It is actually built *on
top of* dict, so it's no better. Ex:

>>> a = Set([1,2,3])
>>> a
Set([1, 2, 3])
>>> a._data
{1: True, 2: True, 3: True}

It just stores a dummy value as the value of the dict.

BTW I am using a regular dictionary for the adjacency list, with the list of
destination edges. I was using another dictionary for the 'cache' of names.

Thanks for the help.

Andy

In article <jyFXa.342$> ,
Andy C <> wrote:
>
>OK, you're right -- I assumed that the key and value were duplicated,
>but that's not the case. I don't know why I thought that, maybe since
>the key must be immutable and the value is mutable. So I guess having
>a dictionary of the form { 'A': 'A', 'B': 'B' } is not as stupid as it
>first seems, since only a reference is stored. But still I wonder why
>the language doesn't have a facility for getting a reference to the key
>value in constant time. Apparently someone did it by modifying the C
>source for the dictionary to add a ref_key() accessor. It seems like
>it would be useful quite often.

Well, you're the first person I recall caring about this specific issue.
Of course, general caching issues come up quite frequently. All the
people I've seen wanting to use intern() come at it from a performance
rather than memory perspective, for which a dict would be no use.
--
Aahz () <*> http://www.pythoncraft.com/

This is Python. We don't care much about theory, except where it intersects
with useful practice. --Aahz

> These days I have an extension which merely subclasses dict to add on
> a key reference method and an increment method which does something
> like:

You did this in C or python? If in python, how did you do it? (without
keys()?) If in C, why don't you submit it to the source tree?

thanks,
Andy

"Andy C" <> wrote in message news:<IJ0Ya.969$ .com>...
> > These days I have an extension which merely subclasses dict to add on
> > a key reference method and an increment method which does something
> > like:
>
> You did this in C or python? If in python, how did you do it? (without
> keys()?) If in C, why don't you submit it to the source tree?

C. There were two people interested in having it in the core, me and Pat Malone.