Python: найти ближайший ключ в словаре по заданному ключу ввода

Question

У меня есть данные в виде словаря .. Теперь я беру ввод от пользователя, и это может быть что угодно .. И я пытаюсь сделать следующее. Если ключ существует, тогда круто .. получите значение из словаря. если нет, то выберите ближайший (в числовом смысле). Например, если клавиша ввода - 200 и ключи как: ....

197,202,208...

Тогда, вероятно, 202 является ближайшим ключом к 200 .. Теперь с точки зрения алгоритма. прямо вперед ... но есть ли питонский способ сделать это? Спасибо

Answer 1

Эта проблема усложняется из-за того, что клавиши dict не расположены в определенном порядке. Если вы можете поиграть с тем, как вы делаете дикт, чтобы они были в порядке (как в вашем примере) и использовали python> = 2.7, вы можете использовать OrderedDict и bisect , чтобы сделать эту молнию быстрой.

import collections
a = collections.OrderedDict()
for i in range(100):
    a[i] = i

import bisect
ind = bisect.bisect_left(a.keys(), 45.3)

Тогда вам нужно только проверить элементы ind и ind-1, чтобы увидеть, какой из них ближе, тем самым делая гораздо меньше вычислений.

---

Как указано ниже Стивеном Дж., В Python3 .keys () - это не просто список, и его нужно изменить в один.

bisect.bisect_left(list(a.keys()), 45.3)

Answer 2

здесь ваша функция в одной строке:

data.get(num, data[min(data.keys(), key=lambda k: abs(k-num))])

edit: чтобы не вычислять мин, когда ключ используется в dict:

data[num] if num in data else data[min(data.keys(), key=lambda k: abs(k-num))]

или если все значения в data оцените True вы можете использовать:

data.get(num) or data[min(data.keys(), key=lambda k: abs(k-num))]

Answer 3

Вместо использования OrderedDict и bisect рассмотрим тип SortedDict в модуле sortedcontainers . Это реализация на чистом Python и fast-as-C отсортированного списка, отсортированного dict и отсортированного набора типов со 100% охватом тестирования и часами стресса.

С помощью SortedDict вы можете разделить пополам нужный ключ. Например:

from itertools import islice
from sortedcontainers import SortedDict

def closest(sorted_dict, key):
    "Return closest key in `sorted_dict` to given `key`."
    assert len(sorted_dict) > 0
    keys = list(islice(sorted_dict.irange(minimum=key), 1))
    keys.extend(islice(sorted_dict.irange(maximum=key, reverse=True), 1))
    return min(keys, key=lambda k: abs(key - k))

Функция closest использует SortedDict.irange для создания итератора ключей, ближайшего к данному ключу. Ключи разделены пополам с log(N) сложность времени выполнения.

>>> sd = SortedDict({-3: 'a', 0: 'b', 2: 'c'})
>>> for num in range(-5, 5):
...     key = closest(sd, num)
...     print('Given', num, ', closest:', key)
Given -5 , closest: -3
Given -4 , closest: -3
Given -3 , closest: -3
Given -2 , closest: -3
Given -1 , closest: 0
Given 0 , closest: 0
Given 1 , closest: 2
Given 2 , closest: 2
Given 3 , closest: 2
Given 4 , closest: 2

Это Pythonic использовать PyPI!

Answer 4

Если все, что у вас есть, это словарь Python, вы не можете лучше проверить все записи в словаре (как в ответе Уилла). Однако, если вы хотите найти ближайший ключ более эффективно, чем этот (т. Е. В O(log N) вместо O(N)), вам нужно какое-то сбалансированное дерево.

К сожалению, я не верю, что Python имеет такую ​​структуру данных в своей стандартной библиотеке - поскольку Pythonic использует вместо этого dict. Так что, если вы собираетесь сделать много таких запросов на большой карте, лучшим выбором может быть поиск библиотеки расширений или даже сворачивание вашей собственной ...

Answer 5

Это должно делать то, что вы хотите (за исключением получения ключа), но вы можете понять это:).

f = lambda a,l:min(l,key=lambda x:abs(x-a))
numbers = (100, 200, 300, 400)
num = int(raw_input())
print 'closest match:', f(num, numbers)

Примечание: f от этот вопрос .