# 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()

```