Re: Floats as keys in dict

Alex Martelli wrote:
Brian Elmegaard <brian@xxxxxxxxxxxxxxxx> 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).

That might be a bit dangerous in cases close to changes in exponent, though, where you could get numbers that were very close but had hugely different mantissa values because their exponents were one different, no?

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).

Your first suggestion was better, I think. Bisect would do the job. I have always thought that dict's numerical index semantics were suspect, but it's probably way too late to alter that now. [I'm assuming that Py3.0 is retaining the numerical equivalence relations].

regards
Steve
--
Steve Holden +1 571 484 6266 +1 800 494 3119
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://del.icio.us/steve.holden
--------------- Asciimercial ------------------
Get on the web: Blog, lens and tag the Internet
Many services currently offer free registration
----------- Thank You for Reading -------------

.

Relevant Pages

  • Re: Sets in Python
    ... allow mutable items as keys is a bit arbitrary. ... The user doesn't need to know the mechanism, but the dict does. ... implemented as hash tables. ... Allow the hash of mutable objects to change, ...
    (comp.lang.python)
  • Re: Why are tuples immutable?
    ... If hash equals id, then the first of those cases fails. ... to key the dict. ... I need to know the order of the keys in that list. ... >keys being mutable objects, that they want to mutate those object while ...
    (comp.lang.python)
  • Floats as keys in dict
    ... I am making a script to optimiza by dynamic programming. ... store the nodes I have in play as keys in a dict. ... the dict keys are then floats and I have to round the values ...
    (comp.lang.python)
  • Re: Hashability?
    ... why not use the object's id for the hash value. ... > Wouldn't this allow typically non-hashable objects to be used as keys? ... Also, if you pickle such a dict and later restore it, all keys now hold bogus ...
    (comp.lang.python)
  • Re: Floats as keys in dict
    ... store the nodes I have in play as keys in a dict. ... the dict keys are then floats and I have to round the values ... give the same hash for two numbers that are "close enough" (e.g., ...
    (comp.lang.python)