On 2007-12-10, MonkeeSage <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list