Brian Elmegaard <[EMAIL PROTECTED]> wrote: > I am making a script to optimiza by dynamic programming. I do not know > the vertices and nodes before the calculation, so I have decided to > store the nodes I have in play as keys in a dict. > > However, the dict keys are then floats and I have to round the values > of new possible nodes in each step. When profiling I see that the most > time consuming part of my script is rounding. > > Is there a faster way than round() or is there a better way to test > than 'in' or should I store the keys in another way than a dict?
You may want to consider keeping a sorted list and using standard library module bisect for searches and insertions -- its behavior is O(log N) for a search, O(N) for an insertion, but it might be that in your case saving the rounding could be worth it. Otherwise, you need to consider a different container, based either on comparisons (e.g. AVL trees, of which there are several 3rd party implementations as Python extensions) or on a hashing function that will give the same hash for two numbers that are "close enough" (e.g., hash ignoring the lowest N bits of the float's mantissa for some N). round() operates on decimals and that may not be as fast as working on binary representations, but, to be fast, a helper function giving the "hash of a binary-rounded float" would have to be coded in C (or maybe use psyco). Alex -- http://mail.python.org/mailman/listinfo/python-list
