Data structure recommendation?

Steven Clark steven.p.clark at gmail.com
Mon Apr 7 22:39:56 CEST 2008


Hi all-

I'm looking for a data structure that is a bit like a dictionary or a
hash map. In particular, I want a mapping of floats to objects.
However, I want to map a RANGE of floats to an object.

This will be used for timestamped storage / lookup, where the float
represents the timestamp.
get(x) should return the object with the "newest" (biggest) timestamp
y <= x, if it exists.
Example:

foo = Foo()

foo.get(1.5)
-> None
foo.put(1.3, 'a')
foo.put(2.6, 'b')
foo.get(1.5)
-> 'a'
foo.get(7.8)
-> 'b'
foo.put(5.0, 'c')
foo.get(7.8)
-> 'c'

In otherwords, by the end here, for foo.get(x),
x < 1.3 maps to None,
1.3 <= x < 2.6 maps to 'a',
2.6 <= x < 5.0 maps to 'b',
5.0 <= x maps to 'c'.

I know that foo.get() will be called many times for each foo.put(). Is
there any way to achieve O(1) performance for foo.get(), maybe via
some kind of hash function? Or is the best thing to use some kind of
binary search?

Thanks for any advice.

-Steven



More information about the Python-list mailing list