Data structure recommendation?

[Charles Mason]

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 <steve at holdenweb.com> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20080407/90f5cd77/attachment-0001.html>