Floats as keys in dict

[Alex Martelli]

Brian Elmegaard <brian at rkspeed-rugby.dk> 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