Python data structure for a collection of objects with random access based on an attribute

Question

I need a collection of objects which can be looked up by a certain (unique) attribute common to each of the objects. Right now I am using a dicitionary assigning the dictionary key to the attribute. Here is an example of what I have now:

class Item():
    def __init__(self, uniq_key, title=None):
        self.key = uniq_key
        self.title = title

item_instance_1 = Item("unique_key1", title="foo")
item_instance_2 = Item("unique_key3", title="foo")
item_instance_3 = Item("unique_key2", title="foo")

item_collection = {
        item_instance_1.key: item_instance_1,
        item_instance_2.key: item_instance_2,
        item_instance_3.key: item_instance_3
        }

item_instance_1.key = "new_key"

Now this seems a rather cumbersome solution, as the key is not a reference to the attribute but takes the value of the key-attribute on assignment, meaning that:

the keys of the dictionary duplicate information already present in form of the object attribute and
when the object attribute is changed the dictionary key is not updated.

Using a list and iterating through the object seems even more inefficient.

So, is there more fitting data structure than dict for this particular case, a collection of objects giving me random access based on a certain object attribute?

This would need to work with Python 2.4 as that's what I am stuck with (at work).

If it hasn't been obvious, I'm new to Python.

Alex Martelli · Accepted Answer · 2009-09-05T17:43:37.823

There is actually no duplication of information as you fear: the dict's key, and the object's .key attribute, are just two references to exactly the same object.

The only real problem is "what if the .key gets reassigned". Well then, clearly you must use a property that updates all the relevant dicts as well as the instance's attribute; so each object must know all the dicts in which it may be enregistered. Ideally one would want to use weak references for the purpose, to avoid circular dependencies, but, alas, you can't take a weakref.ref (or proxy) to a dict. So, I'm using normal references here, instead (the alternative is not to use dict instances but e.g. some special subclass -- not handy).

def enregister(d, obj):
  obj.ds.append(d)
  d[obj.key] = obj

class Item(object):
    def __init__(self, uniq_key, title=None):
        self._key = uniq_key
        self.title = title
        self.ds = []

    def adjust_key(self, newkey):
        newds = [d for d in self.ds if self._key in d]
        for d in newds:
          del d[self._key]
          d[newkey] = self
        self.ds = newds
        self._key = newkey

    def get_key(self):
        return self._key

    key = property(get_key, adjust_key)

Edit: if you want a single collection with ALL the instances of Item, that's even easier, as you can make the collection a class-level attribute; indeed it can be a WeakValueDictionary to avoid erroneously keeping items alive, if that's what you need. I.e.:

class Item(object):

    all = weakref.WeakValueDictionary()

    def __init__(self, uniq_key, title=None):
        self._key = uniq_key
        self.title = title
        # here, if needed, you could check that the key
        # is not ALREADY present in self.all
        self.all[self._key] = self

    def adjust_key(self, newkey):
        # "key non-uniqueness" could be checked here too
        del self.all[self._key]
        self.all[newkey] = self
        self._key = newkey

    def get_key(self):
        return self._key

    key = property(get_key, adjust_key)

Now you can use Item.all['akey'], Item.all.get('akey'), for akey in Item.all:, and so forth -- all the rich functionality of dicts.

Yes, all instances of Item need to be in one collection. Cool, that looks like an elegant solution. — , Sep 05 '09 at 19:25

score 3 · Answer 2 · answered Sep 05 '09 at 16:44

3

There are a number of great things you can do here. One example would be to let the class keep track of everything:

class Item():
    _member_dict = {}
    @classmethod
    def get_by_key(cls,key):
        return cls._member_dict[key]
    def __init__(self, uniq_key, title=None):
        self.key = uniq_key
        self.__class__._member_dict[key] = self
        self.title = title

>>> i = Item('foo')
>>> i == Item.get_by_key('foo')
True

Note you will retain the update problem: if key changes, the _member_dict falls out of sync. This is where encapsulation will come in handy: make it (practically) impossible to change key without updating the dictionary. For a good tutorial on how to do that, see this tutorial.

answered Sep 05 '09 at 16:44

David Berger

12,385
6
38
51

In this case, you could also define __new__ to prevent creation of an Item with a key that has already been used. – PaulMcG Sep 05 '09 at 16:49
How does one surround a word with double underscores and not have stackoverflow interpret this as bolding? – PaulMcG Sep 05 '09 at 16:50
@Paul, use `backquotes` around the word were you want underscores preserved as such. – Alex Martelli Sep 05 '09 at 17:37

score 0 · Answer 3 · answered Sep 05 '09 at 16:41

Well, dict really is what you want. What may be cumbersome is not the dict itself, but the way you are building it. Here is a slight enhancement to your example, showing how to use a list expression and the dict constructor to easily create your lookup dict. This also shows how to create a multimap kind of dict, to look up matching items given a field value that might be duplicated across items:

class Item(object):
    def __init__(self, **kwargs):
        self.__dict__.update(kwargs)
    def __str__(self):
        return str(self.__dict__)
    def __repr__(self):
        return str(self)

allitems = [
    Item(key="red", title="foo"),
    Item(key="green", title="foo"),
    Item(key="blue", title="foofoo"),
    ]

# if fields are unique
itemByKey = dict([(i.key,i) for i in allitems])

# if field value can be duplicated across items
# (for Python 2.5 and higher, you could use a defaultdict from 
# the collections module)
itemsByTitle = {}
for i in allitems:
    if i.title in itemsByTitle:
        itemsByTitle[i.title].append(i)
    else:
        itemsByTitle[i.title] = [i]



print itemByKey["red"]
print itemsByTitle["foo"]

Prints:

{'key': 'red', 'title': 'foo'}
[{'key': 'red', 'title': 'foo'}, {'key': 'green', 'title': 'foo'}]

Anon · Answer 4 · 2009-09-05T21:55:21.737

Editing to correct the problem I had - which was due to my "collection = dict()" default parameter (*bonk*). Now, each call to the function will return a class with its own collection as intended - this for convenience in case more than one such collection should be needed. Also am putting the collection in the class and just returning the class instead of the two separately in a tuple as before. (Leaving the default container here as dict(), but that could be changed to Alex's WeakValueDictionary, which is of course very cool.)

def make_item_collection(container = None):
    ''' Create a class designed to be collected in a specific collection. '''
    container = dict() if container is None else container
    class CollectedItem(object):
        collection = container
        def __init__(self, key, title=None):
            self.key = key
            CollectedItem.collection[key] = self
            self.title = title
        def update_key(self, new_key):
            CollectedItem.collection[
                new_key] = CollectedItem.collection.pop(self.key)
            self.key = new_key
    return CollectedItem

# Usage Demo...

Item = make_item_collection()
my_collection = Item.collection

item_instance_1 = Item("unique_key1", title="foo1")
item_instance_2 = Item("unique_key2", title="foo2")
item_instance_3 = Item("unique_key3", title="foo3")

for k,v in my_collection.iteritems():
    print k, v.title

item_instance_1.update_key("new_unique_key")

print '****'
for k,v in my_collection.iteritems():
    print k, v.title

And here's the output in Python 2.5.2:

unique_key1 foo1
unique_key2 foo2
unique_key3 foo3
****
new_unique_key foo1
unique_key2 foo2
unique_key3 foo3

Python data structure for a collection of objects with random access based on an attribute

4 Answers4

Linked