Brian Elmegaard <br***@rkspeed-rugby.dkwrote:
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
