Efficient Data Structure Questions

[Stefan Schwarzer]

Hello Jeff

Jeff Layton wrote:
>    I'm struggling with a data structure design problem.
> It basically boils down to a list of dictionaries or a dictionary
> of lists.
 > [...]
>    I need to search through 'key1' for a match to a string and
> then get the 'key2' and 'key3' data associated with the
> matched value of 'key1'.
>    Does anyone have any suggestions as to the most efficient
> data structure? (I like efficiency but I also like ease of coding).
> Can anyone explain why one is better than the other (I know
> that's subjective, but I'm looking to learn something from
> this :)

If you want to use only basic Python datastructures, you could use the
dictionary of lists for the mentioned purpose. You can do the lookup with

 >>> d = {}
 >>> d['key1'] = ['s1', 's2', 's3']
 >>> d['key2'] = [1, 2, 3]
 >>> d['key3'] = [[1,2,3], [4,5,6], [7,8,9]]
 >>>
 >>> index = d['key1'].index('s2')
 >>> index
1
 >>> d['key2'][index]
2
 >>> d['key3'][index]
[4, 5, 6]

However, this results in a linear search through a list. Probably better is

 >>> d = {}
 >>> d['s1'] = (1, [1,2,3])
 >>> d['s2'] = (2, [4,5,6])
 >>> d['s3'] = (3, [7,8,9])
 >>> d['s2'][0]
2
 >>> d['s2'][1]
[4, 5, 6]

In this data structure, you would loose entries if you have the same key
(the 's1' etc.) more than once. On the other hand, you couldn't access them too
in the first structure anyway.

Depending on your application, I would wrap the above structure in a class
to hide the implementation.

Stefan