Data structure recommendation?

[Steve Holden]

Steven Clark wrote:
> 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?
> 
I believe the best way to implement this would be a binary search 
(bisect?) on the actual times, which would be O(log N). Though since 
they are timestamps they should be monotonically increasing, in which 
case at least you don't have to go to the expense of sorting them.

"Some kind of hash function" won't hack it, since the purpose of a hash 
function is to map a large number of (possibly) evenly-distributed 
(potential) keys as nearly as possible randomly across a much smaller 
set of actual values.

You might try messing around with reducing the precision of the numbers 
to home in on a gross region, but I am not convinced that does anything 
other than re-spell binary search if carried to extremes.

regards
  Steve
-- 
Steve Holden        +1 571 484 6266   +1 800 494 3119
Holden Web LLC              http://www.holdenweb.com/