If you can imply a partial order on your ranges then you can get O(n lg n) random access using a heap data structure.
You'll have to implement your own heap, but heap search is easy to implement (it's Heapify that might require a little thinking). This will only work, of course, if your ranges are disjoint. C On Mon, Apr 7, 2008 at 4:58 PM, Steve Holden <[EMAIL PROTECTED]> wrote: > 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/ > > -- > http://mail.python.org/mailman/listinfo/python-list >
-- http://mail.python.org/mailman/listinfo/python-list
