Cookbook: Associating multiple values with each key in a dictionary

[Michael Gilfix]

On Tue, Jul 30 @ 21:50, Egbert Bouwman wrote:
> On Tue, Jul 30, 2002 at 01:14:14PM -0400, Michael Gilfix wrote:
> > 
> >   I'm not really sure why you prefer the list method. Is there something
> > that you can't accomplish with the nested dictionaries?
> 
> When I need
>   { 'boys': ['mike', 'egbert'], 'girls': ['laura','lisa'] }
> it hurts me when I have to build:  
>   { 'boys': {'mike' : 1, 'egbert' : 1}, 'girls': {'laura' : 1,'lisa' : 1} }
>   
> That adds an extra layer of complexity when i construct it,
> I have to remember or document that the values can be thrown away,
> and I have now sets of keys, while I need sets of values.

  This is exactly the kind of situation that python classes dream of.
Check out the following class (which is very pythonic) and lemme know
if this does what you'd like:

Contents of t.py:
class mydict:
  def __init__ (self):
    self.nested_dict = { }
  def append (self, key, value):
    if not self.nested_dict.has_key (key):
      self.nested_dict[key] = { }
    self.nested_dict[key][value] = 1
  def __getitem__ (self, key):
    return self.nested_dict[key].keys ()

Python 2.1.3 (#1, Apr  9 2002, 20:09:43)
[GCC 2.95.3 20010315 (release)] on linux2
Type "copyright", "credits" or "license" for more information.
>>> import t
>>> f = t.mydict()
>>> f.append ('foo', 'mike')
>>> f.append ('foo', 'egbert')
>>> f.nested_dict
{'foo': {'egbert': 1, 'mike': 1}}
>>> f['foo']
['egbert', 'mike']

  By exploting __getitem__, I get the exact behavior you want while
I'm guaranteed that each item will be unique. AND, it'll be fast too.
This is also relatively straight-forward. The __getitem__ protocol
method allows you to use the object how you want while keeping its
internals separate.

> Of course that all changes when I really need the values, ie when
> they don't have some dummy value anymore. But in that case 
> we simply have a nested dictionary, which is not our subject now.

  I'm sure you can extend this interface to do whatever you like :)

> As an afterthought: is it necessary that lists are slower than
> dictionaries ?  Cannot they be subjected to some hash machine as well ?
> At least in some cases, ie when you search in lists ?

  Lists are not necessarily slower than dictionaries. They can be just
as fast for things like list appends. But lists are made for storing
sequences of objects and with each append, you extend the sequence.  A
dictionary (or hash table if you prefer) has the advantage that each
key maps to the same location (and quickly), whereas in a list, you
only have an index number to reference locations in the list. Thus
hashing is a better fit for the unique problem because you always look
in the same place, while in lists you have to search the entire list
to be sure that your item is unique.

  Hope that makes sense. If you have little experience with hash
tables, I suggest taking the time to read some literature, as they are
very common in nearly all CS problems and let you do some pretty
cool tricks.

                          -- Mike