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