Data structure recommendation?

[Paul McGuire]

On Apr 7, 3:58 pm, Steve Holden <st... at holdenweb.com> wrote:
>
> I believe the best way to implement this would be a binary search
> (bisect?) on the actual times, which would be O(log N).

bisect is definitely the way to go.  You should take care with
floating point precision, though.  One way to do this is to choose a
number of digits of precision that you want, and then internally to
your class, multiply the keys by 10**precision and truncate, so that
you are working with ints internal to the Foo class.  Here is a stab
at a solution to your question, with precision to 1 decimal place.  I
also added __getitem__ and __setitem__, since your class has many dict-
like semantics.

-- Paul


import bisect

class Foo(object):
    def __init__(self):
        self.items = {}
        self.keys = []

    def put(self,key,value):
        key = int(key * 10)
        if key not in self.items:
            bisect.insort(self.keys, key)
        self.items[key] = value

    def get(self,key):
        key = int(key * 10)
        idx = bisect.bisect_left(self.keys,key)
        if idx:
            return self.items[self.keys[idx-1]]

    def __setitem__(self,key,value):
        self.put(key,value)

    def __getitem__(self,key):
        return self.get(key)

if __name__ == "__main__":
    foo = Foo()
    print foo.get(1.5) #    -> None
    foo.put(1.3, 'a')
    foo.put(2.6, 'b')
    print foo.get(1.5) #    -> 'a'
    print foo.get(7.8) #    -> 'b'
    foo.put(5.0, 'c')
    print foo.get(7.8) #    -> 'c'
    print foo[1.0] #    -> None
    foo[6.3] = 'z'
    print foo[7.8]