searching a value of a dict (each value is a list)

[Seongsu Lee]

On 12월10일, 오전6시49분, Jeremy C B Nicoll <jer... at omba.demon.co.uk> wrote:
> Seongsu Lee <se... at senux.com> wrote:
> > Hi,
>
> > I have a dictionary with million keys. Each value in the
> > dictionary has a list with up to thousand integers.
> > Follow is a simple example with 5 keys.
>
> > dict = {1: [1, 2, 3, 4, 5],
> >    2: [10, 11, 12],
> >    900000: [100, 101, 102, 103, 104, 105],
> >    900001: [20, 21, 22],
> >    999999: [15, 16, 17, 18, 19]}
>
> > I want to find out the key value which has a specific
> > integer in the list of its value. For example, if I search
> > 104 in the list, 900000 must be returned.
>
> Are the integers in the lists unique?  I mean, could 104 occur in more than
> one list?  If it did, would it matter which key was returned?

Yes, the intergers in the lists are unique.

> > How can I do this with Python? Ideas?
>
> When I see something like this my natural response is to think that the data
> structure is inappropriate for the use it's being put to.  
>
> The code someone else posted to reverse the keys is all very well, but
> surely hugely wasteful on cpu, maybe storage, and elapsed time.
>
> Even if the dict in this form is needed for some other reason, couldn't the
> code that created it also create a reverse index at the same time?

The reason I use the dict for my data is to speed up the search by
key.

The code could create also a reverse index (a reverse dict) at the
time. But as you said, it waste the space and I wanted to ask someone
who may know some way to reduce the waste of space while searching
fast.