Speeding dictionary lookup of instances

[Brian Kelley]

Sometimes one wants to use an instance as a key in a dictionary

class Foo:
    pass

f = Foo()
d = {}
d[f] = 1

It turns out that this is relatively slow.  In a previous post I was 
using a unique integer handle as a hash key.

class IDGenerator:
   def __init__(self):
        self.start = -1
   def next(self):
        self.start += 1
        return self.start

class Foo:
    def __init__(self, generator=IDGenerator()):
        self.handle = generator.next()

f = Foo()
d[f.handle] = 1

This speeds up dictionary lookup by a factor of 20.  Not that 
implementing a __hash__ method to return the handle won't speed up the 
lookup.

Paul Foley pointed out the builtin id function which I had forgotten 
about could be used for the same purpose.

d[id(f)] = 1

It turns out this the speed of this is identical to the speed of using 
the handle.  I like using the handle because the dictionary is picklable 
  with the instance.  id(f) changes during different sessions.

The drawback to using this method is that the keys of the dictionary are 
not actually the objects themselves, however it does dramatically 
increase the speed of dictionaries.

So if you want faster lookups using instances as keys, use a handle or 
the id.

Attached is some simple timing code showing these three methods.

Brian Kelley
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: test_handles.py
URL: <http://mail.python.org/pipermail/python-list/attachments/20011220/0f7e755a/attachment.ksh>