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

[MonkeeSage]

On Dec 10, 3:50 am, Seongsu Lee <se... at senux.com> wrote:
> On 12월10일, 오후12시18분, Adonis Vargas <adon... at REMOVETHISearthlink.net>
> wrote:
>
>
>
> > Seongsu Lee 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.
>
> > > How can I do this with Python? Ideas?
>
> > You can try this:
>
> > items = {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]}
>
> > def findItem(item, dictionary):
> >      for key, value in dictionary.iteritems():
> >          if item in value:
> >              print key, value
>
> > findItem(104, items)
>
> > This will allow you to work with the existing dataset without needing to
> > duplicate it. It will print all occurrances.
>
> Hi,
>
> Yes, it works. But I think it works in O(n * m), doesn't it?
> (n is # of keys in the dictionary and m is # of items in the list.)
> So, we need to create a reverse index. (a reverse dictionary) or
> need something better at least, I think.
>
> > Also, you should never use reserved words like 'dict' this creates
> > confusion and can cause Python to misbehave since you are rebinding the
> > name.
>
> Yep. :)
>
> > Hope this helps.
>
> > Adonis Vargas- 따온 텍스트 숨기기 -
>
> > - 따온 텍스트 보기 -

If I'm not mistaken, building a reverse dictionary like that will be
O(n*m) because dict/list access is O(n) (ammortized). Somebody correct
me if I'm wrong. In that case, it really depends on how you will use
the dict to see whether you get any benefit from building the reversed
dict. If you want to do several lookups, then the initial overhead
(speed/memory) of building the reversed dict might be worth it so that
you can just run lookups at O(n). But if you only need it once, it is
a waste of time and space to create a reverse dict when your access
time is the same for the lookup as for building the reversed dict.

If you do need more than one lookup, it would also be a good
optimization strategy to build the reverse dict in parallel, as you
execute the first search; that way you can combine the time spent on
building the reverse dict and the lookup, to get a total of O(n*m)
rather than O(n^2*m). The first search is "free" since you need the
reverse dict anyway.

Regards,
Jordan