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

[MonkeeSage]

On Dec 10, 8:31 am, Neil Cerutti <horp... at yahoo.com> wrote:
> On 2007-12-10, MonkeeSage <MonkeeS... at gmail.com> wrote:
>
> > 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).
>
> It also depends on if the dictionary shall be mutated between
> reverse lookups.
>
> > 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.
>
> It wouldn't be merely an optimization if reverse lookups and
> mutations were interleaved.
>
> --
> Neil Cerutti
> You only get a once-in-a-lifetime opportunity so many times. --Ike Taylor

Well true, but you enter a whole other level of complexity in that
case...something like Theta(log(n*(m-n))). I might have calculated
that incorrectly, but that just goes to show how complex a lookup
is(!) in such a case.

Regards,
Jordan