On Dec 10, 9:45 am, MonkeeSage <[EMAIL PROTECTED]> wrote: > On Dec 10, 8:31 am, Neil Cerutti <[EMAIL PROTECTED]> wrote: > > > > > 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 > > 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
Sorry for the double-post...google is being beligerant right now. -- http://mail.python.org/mailman/listinfo/python-list
