Use range as a key value in a dictionary, most efficient way?

1987 views python
10

I have been wondering if there is some kind of data-structure or clever way to use a dictionary (O(1) lookup) to return a value if there are given values for defined ranges that do not overlap. So far I have been thinking this could be done if the ranges have some constant difference (0-2, 2-4, 4-6, etc.) or a binary-search could be done to do this in O(log(n)) time.

So, for example given a dictionary,

d = {[0.0 - 0.1): "a",
     [0.1 - 0.3): "b",
     [0.3 - 0.55): "c",
     [0.55 - 0.7): "d",
     [0.7 - 1.0): "e"}

it should return,

d[0.05] 
>>> "a"
d[0.8]
>>> "e"
d[0.9]
>>> "e"
d[random.random()] # this should also work

Is there anyway to achieve something like this? Thanks for any responses or answers on this.

answered question

Yes, since your ranges are arbitrary anyways you can write a function that maps ranges to integers. Then simply lookup that integer in a list (if number of ranges are fixed), or a dictionary. If the ranges were more systematic the function can be even be a simple lambda function.

I'm assuming that this solution requires some kind of search to check if the value is within the range, so is at least O(log(n)) in that case? This is fine, I was just wondering if there was some conventional method or data-structure to do it in O(1) time

1 Answer

0

First, split your data into two arrays:

limits = [0.1, 0.3, 0.55, 0.7, 1.0]
values = ["a", "b", "c", "d", "e"]

limits is sorted, so you can do binary search in it:

import bisect

def value_at(n):
    index = bisect.bisect_left(limits, n)
    return values[index]

posted this

Have an answer?

JD

Please login first before posting an answer.