Finding value in dict given an integer that can be found in between dictionary's tuple key

user_610569 0
Viewed 67

Given an x dictionary of tuple keys and string values:

x = {(0, 4): 'foo', (4,9): 'bar', (9,10): 'sheep'}

The task is to write the function, find the value, given a specific number, e.g. if user inputs 3, it should return 'foo'. We can assume that there is no overlapping numbers in the key.

Another e.g., if user inputs 9, it should return 'bar'.

I've tried converting the x dict to a list and write the function as follows, but it's suboptimal if the range of values in the keys is extremely huge:

from itertools import chain

mappings = None * max(chain(*x))

for k in x:
    for i in range(k[0], k[1]):
        mappings[i] = x[k] 

def myfunc(num):
    return mapping[num]
  • How else can the myfunc function be written?
  • Is there a better data structure to keep the mapping?
key-value tuples data-structures dictionary python
4 Answers

You could simply iterate through keys and compare the values (rather than creating a mapping). This is a bit more efficient than creating a mapping first, since you could have a key like (0, 100000) which will create needless overhead.

Edited answer based on comments from OP

x = {(0, 4): 'foo', (4,9): 'bar', (9,10): 'sheep'}

def find_value(k):
    for t1, t2 in x:
        if k > t1 and k <= t2:   # edited based on comments
            return x[(t1, t2)]
    
    # if we end up here, we can't find a match
    # do whatever appropriate, e.g. return None or raise exception
    return None

Note: it's unclear in your tuple keys if they are inclusive ranges for the input number. E.g. if a user inputs 4, should they get 'foo' or 'bar'? This will affect your comparison in the function described above in my snippet. (see edit above, this should fulfill your requirement).

In this example above, an input of 4 would return 'foo', since it would fulfill the condition of being k >= 0 and k <= 4, and thus return before continuing the loop.

Edit: wording and typo fix

user_157442610

You can convert your key in a numpy array and use numpy.searchsorted to search a query. Since keys are left open I have incremented open value of keys by 1 in the array.

Each query is of order O(log(n)).

Create an array:

A = np.array([[k1+1, k2] for k1, k2 in x])
>>> A
array([[ 1,  4],
       [ 5,  9],
       [10, 10]])

Function to search query:

def myfunc(num):
    ind1 = np.searchsorted(A[:, 0], num, 'right')
    ind2 = np.searchsorted(A[:, 1], num, 'left')
    if ind1 == 0 or ind2 == A.shape[0] or ind1 <= ind2: return None
    return vals[ind2]

Prints:

>>> myfunc(3)
'foo'
user_78314210

Iterate over the dictionary comparing to the keys:

x = {(0, 4): 'foo', (4, 9): 'bar', (9, 10): 'sheep'}

def find_tuple(dct, num):
    for tup, val in dct.items():
        if tup[0] <= num < tup[1]:
            return val
    return None

print(find_tuple(x, 3))
# foo
print(find_tuple(x, 9))
# sheep
print(find_tuple(x, 11))
# None

A better data structure would be a dictionary with just the left boundaries of the intervals (as keys) and the corresponding values. Then you can use bisect as the other answers mention.

import bisect
import math

x = {
    -math.inf: None,
    0: 'foo',
    4: 'bar',
    9: 'sheep',
    10: None,
}

def find_tuple(dct, num):
    idx = bisect.bisect_right(list(dct.keys()), num)
    return list(dct.values())[idx-1]

print(find_tuple(x, 3))
# foo
print(find_tuple(x, 9))
# sheep
print(find_tuple(x, 11))
# None
user_9676210

Here's one solution using pandas.IntervalIndex and pandas.cut. Note, I "tweaked" the last key to (10, 11), because I'm using closed="left" in my IntervalIndex. You can change this if you want the intervals closed on different sides (or both):

import pandas as pd

x = {(0, 4): "foo", (4, 9): "bar", (10, 11): "sheep"}

bins = pd.IntervalIndex.from_tuples(x, closed="left")
result = pd.cut([3], bins)[0]

print(x[(result.left, result.right)])

Prints:

foo

Other solution using bisect module (assuming the ranges are continuous - so no "gaps"):

from bisect import bisect_left

x = {(0, 4): "foo", (4, 9): "bar", (10, 10): "sheep"}

bins, values = [], []
for k in sorted(x):
    bins.append(k[1])  # intervals are closed "right", eg. (0, 4]
    values.append(x[k])

idx = bisect_left(bins, 4)
print(values[idx])

Prints:

foo
user_100359850
Related