Data structure recommendation?
Steven Clark
steven.p.clark at gmail.com
Tue Apr 8 11:49:39 EDT 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