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

[Neil Cerutti]

On 2007-12-10, MonkeeSage <MonkeeSage 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