On 12/15/2016 09:06 AM, Steve D'Aprano wrote:
Has anyone dealt with data like this and could give a recommendation of the
right data structure to use?
I haven't dealt with a data structure exactly like this, but it's
basically a sparse array. (I'm sure it has a name somewhere in the
academic literature, but I couldn't find it with a quick search right
now...)
My solution to what you're asking for would be to have a list of
key-value pairs, only adding a key to the list if it "changes" the
value. I.e. your data structure would be this:
l = [
(1, "foo"),
(101, "bar"),
(103, "foobar"),
(104, "bar"),
(105, "foo"),
]
Then the only thing you need to do is define the lookup function. I
would basically just do a binary search on the first values in the
tuples. I.e. if "n" is your integer, you check if the middle values of
the list l has it's first element as less than or greater than your
value. Then you split l in two and do the same thing. Do this until you
either find your value, or you find a value less than your value with
the added property that the next value is greater than your value. After
that you spit out the final second value.
There might be better ways to find the keys, but I think this approach
is probably your best bet.
Cheers,
Thomas
--
https://mail.python.org/mailman/listinfo/python-list
