Compare number between keys of dictionary-CodePudding

Lets say I have the following dictionary;

d = {'a': 5,
     'b': 10,
     'c': 15,
     'd': 20}

Now I want to find out between which values a certain variable is and return the uppermost corresponding key. So for example for var = 8, I would like to return b. And for var = 10, I also would like to return b.

Because I'm using this in larger loop I would like to this as efficient as possible and that is why I came to StackOverflow

CodePudding user response：

Here is a version that returns the upper bound, or None if none is found:

d = {'a': 5,
     'b': 10,
     'c': 15,
     'd': 20}

var = 6

diff = float('inf')
match = None
for k, v in d.items():
    if var <= v and v-var < diff:
        diff = v-var
        match = k

print(match)

output: b

CodePudding user response：

If you're only doing this once, the simplest thing is to use min to find the value that is >= var where the difference from var is the smallest. This requires each item in the dictionary to be considered, making it O(n):

>>> d = {'a': 5,
...      'b': 10,
...      'c': 15,
...      'd': 20}
>>> var = 10
>>> min((k for k in d if d[k] >= var), key=lambda k: d[k] - var)
'b'
>>> var = 6
>>> min((k for k in d if d[k] >= var), key=lambda k: d[k] - var)
'b'
>>> var = 5
>>> min((k for k in d if d[k] >= var), key=lambda k: d[k] - var)
'a'

If you want to optimize this operation so you can do it with a bunch of different values and have it perform better than O(n) each time, you'll want to create an auxiliary data structure, like a sorted list that you can do a binary search on -- that would be O(n log n) up front, but each individual search would be only O(log n) thereafter.

CodePudding user response：

I would reorganize the keys & values of the dictionary and use bisect library:

from bisect import bisect_left

keys, values = list(zip(*sorted(d.items(), key=lambda x:x[1])))

def get_key(v):
    if v <= values[-1]:
        return keys[bisect_left(values, v)]
    else:
        return None