Data structure recommendation?

Steven Clark steven.p.clark at gmail.com
Tue Apr 8 17:49:39 CEST 2008


>  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.

Thanks for the reply. Can you explain how I could be bitten by
floating point precision here?
I'm familiar with how&why 1.3*3 != 3.9, etc., but I'm not sure how it
applies here, or what you are gaining by converting to int.

What do you guys think of this approach which uses tuples:


from bisect import insort_right, bisect_right

class Heavy(object):
    def __cmp__(self, other):
        return 1

heavy = Heavy()

class Foo(object):
    def __init__(self):
        self.data = []

    def __setitem__(self, k, v):
        #if k's are the same, will be sorted by v's. may or may not be
desireable
        insort_right(self.data, (k, v))

    def __getitem__(self, k):
        i = bisect_right(self.data, (k, heavy))
        if i == 0:
            return None
        else:
            return self.data[i-1][1]

def main():
    foo = Foo()
    assert(foo[1.5] == None)
    foo[1.3] = 'a'
    foo[2.6] = 'b'
    assert(foo[1.2999] == None)
    assert(foo[1.3] == 'a')
    assert(foo[1.5] == 'a')
    assert(foo[2.6] == 'b')
    assert(foo[7.8] == 'b')
    foo[5.0] = 'c'
    assert(foo[7.8] == 'c')
    print('Foo checks passed.')

if __name__ == '__main__':
    main()



More information about the Python-list mailing list