13

if I have a dictionary like this

>>> d = {10: 3, 100: 2, 1000: 1}

I can type something like:

>>> d.get(10), d.get(100), d.get(1000)
(3, 2, 1)

Though I want that if the given key is not found, the value corresponding to the nearest key respect the given key is returned:

>>> d.get(20), d.get(60), d.get(200)
(3, 2, 2)

Instead the result in Python is

(None, None, None)

What's a Pythonic way to implement the behavior I described?

Thanks

Paolo
  • 20,112
  • 21
  • 72
  • 113
  • 2
    Not an exact duplicate, but useful: http://stackoverflow.com/questions/2390827/how-to-properly-subclass-dict-and-override-get-set – Robᵩ Apr 27 '11 at 18:50

3 Answers3

17

You can derive from dict to change the behaviour of the get() method:

class ClosestDict(dict):
    def get(self, key):
        key = min(self.iterkeys(), key=lambda x: abs(x - key))
        return dict.get(self, key)

d = ClosestDict({10: 3, 100: 2, 1000: 1})
print (d.get(20), d.get(60), d.get(200))

prints

(3, 2, 2)

Note that the complexity of get() no longer is O(1), but O(n).

Sven Marnach
  • 574,206
  • 118
  • 941
  • 841
  • 3
    This makes lookup O(n) though, so use with care. Perhaps you should give it a different name instead. –  Apr 27 '11 at 18:53
  • 2
    +1 Nice use of min/key, a trivial optimization may be to test for a direct hit. `if key not in self: key = min(...`. – kevpie Apr 27 '11 at 20:27
6

bisect module allows fast lookup of insertion position in a sorted list.

from bisect import bisect_right

def closest_matches(data, query):
    keys = sorted(data)
    return [data[i] for i in (min(map(abs, (keys[p-1], keys[p]))) for p in (bisect_right(keys, k) for k in query))]

>>> d = {10: 3, 100: 2, 1000: 1}
>>> closest_matches(d, [20, 60, 200])
[3, 3, 2]
Imran
  • 87,203
  • 23
  • 98
  • 131
2

Checkout this recipe Fuzzy matching dictionary.

z33m
  • 5,993
  • 1
  • 31
  • 42