How do I get a reference to a KEY value of a dictionary?

Andrew Dalke adalke at mindspring.com
Fri Aug 1 10:40:20 CEST 2003


Andy C:
> Basically I want to create a graph with an adjacency list
> representation, but I don't want any of the adjacency lists to have
> duplicate strings when it is avoidable.

Took me a while but I finally figured out what you're asking.

Look in the docs for 'intern', which is a builtin.  It's rarely used
because most people don't worry about this sort of duplication.

> Is this a waste of time?  Because I know in python I cannot be certain
> that the argument strings that are read from files are even garbage
> collected anyway.  I could certainly do the job with duplicate
> strings, but it would seem wasteful.  I am a C programmer, and old
> habits die hard.

You can never be certain that anything is every garbage collected.
Python-the-language makes no guarantees on that.  Python-in-C
does make a stronger statement, but it's an implementation issue.  As
a C programmer you'll be happy that it's a reference counted scheme
and so long as there are no cycles (which can't happen with a string),
the string will be deallocated when your code lets go of it.

This is true even of interned strings, at least in newer Pythons.  If
no one references an interned string, it too goes away.  (Older
Pythons make the strings immortal.)

Here's how you might change your code.

class GraphAccumulator:
    def __init__( self, fileFunction ):
        self.fileFunction = fileFunction
        self.adjList = {}                       # adjacency list

    def createEdge( self, node1, node2 ):

        # another way of doing by using a dictionary
        node1 = intern(node1)
        node2 = intern(node2)
        adjList = self.adjList
        if adjList.has_key( node1 ):
            adjList[ node1 ].append( node2 );
        else:
            adjList[ node1 ] = [ node2 ];       # singleton edge list

But personally I would put the intern outside of the graph
code - either in the reader or the code between the reader
and this one.  Otherwise, consider:

# fully connect the graph
nodes = graph.adjList.keys()
for n1 in nodes:
  for n2 in nodes:
    if n1 != n2:
      graph.createEdge(n1, n1)

This does extra interning even though it isn't needed.

But then again, normally I wouldn't worry about the interning
at all.  ... Perhaps I should... Hmmm...

                    Andrew
                    dalke at dalkescientific.com






More information about the Python-list mailing list