Скажем, у меня есть список [1,2,3,4,5,6,7]. Я хочу найти 3 ближайших номера, скажем, 6.5. Тогда возвращаемое значение будет [5,6,7].
Поиск одного ближайшего номера не так сложно в python, что можно сделать с помощью
min(myList, key=lambda x:abs(x-myNumber))
Но я стараюсь не ставить цикл вокруг этого, чтобы найти k ближайших чисел. Существует ли питонический способ достижения вышеуказанной задачи?
Функция heapq.nsmallest() сделает это аккуратно и эффективно:
>>> from heapq import nsmallest
>>> s = [1,2,3,4,5,6,7]
>>> nsmallest(3, s, key=lambda x: abs(x-6.5))
[6, 7, 5]
По сути, это говорит: "Дайте мне три входных значения, которые имеют самую низкую абсолютную разницу от числа 6.5".
Алгоритм nsmallest делает один проход по данным, сохраняя в любое время не более n лучших значений в памяти (это означает, что он работает с любым итератором ввода, эффективен с точки зрения кеша и экономичен в пространстве).
Алгоритм добавляет новые значения в кучу, когда будет найдено новое "лучшее" значение. Соответственно, это сводит к минимуму количество проведенных сравнений. Например, если вы ищете 100 лучших значений из 1 000 000 случайных входов, это обычно составляет менее 1008000 сравнений (примерно на 0,8% больше, чем при использовании min() чтобы найти единственное лучшее значение).
Функции клавиш для параметров min(), nsmallest() и sorted() гарантируют, что ключевая функция вызывается ровно один раз за значение во входном итерабельном. Это означает, что этот метод будет эффективен для еще более сложных и интересных примеров проблемы с n-ближайшей ценностью (т.е. слова, которые звучат наиболее похожими, ближайший цвета, самые маленькие различия, наименьшие генетические мутации, евклидовое расстояние и т.д.).
Оба nsmallest() и sorted() возвращают ранжирование списка, упорядоченное по близости (привязки устанавливаются по тому, какое значение было видно первым).
Для тех, кто интересуется, есть несколько вовлеченный анализ ожидаемого количества сравнений здесь и здесь. Краткое резюме:
n + k * (log(k, 2) * log(n/k) + log(k, 2) + log(n/k))n + k * log(k, 2)n * log(k, 2)Вы можете вычислять расстояния и сортировать:
[n for d, n in sorted((abs(x-myNumber), x) for x in myList)[:k]]
Это делает следующее:
(d, x), где d - это расстояние до вашей цели.k элементы этого спискаОба ответа были хорошими, и Грег был прав, ответ Раймонда был более высоким и более простым в реализации, но я основывался на ответе Грега, потому что было легче манипулировать, чтобы соответствовать моим потребностям.
В случае, если кто-то ищет способ найти n ближайших значений из списка dicts.
Мой dict выглядит так: npi - это просто идентификатор, который мне нужен вместе со значением:
mydict = {u'fnpi': u'1982650024',
u'snpi': {u'npi': u'1932190360', u'value': 2672},
u'snpis': [{u'npi': u'1831289255', u'value': 20},
{u'npi': u'1831139799', u'value': 20},
{u'npi': u'1386686137', u'value': 37},
{u'npi': u'1457355257', u'value': 45},
{u'npi': u'1427043645', u'value': 53},
{u'npi': u'1477548675', u'value': 53},
{u'npi': u'1851351514', u'value': 57},
{u'npi': u'1366446171', u'value': 60},
{u'npi': u'1568460640', u'value': 75},
{u'npi': u'1326046673', u'value': 109},
{u'npi': u'1548281124', u'value': 196},
{u'npi': u'1912989989', u'value': 232},
{u'npi': u'1336147685', u'value': 284},
{u'npi': u'1801894142', u'value': 497},
{u'npi': u'1538182779', u'value': 995},
{u'npi': u'1932190360', u'value': 2672},
{u'npi': u'1114020336', u'value': 3264}]}
value = mydict['snpi']['value'] #value i'm working with below
npi = mydict['snpi']['npi'] #npi (identifier) i'm working with below
snpis = mydict['snpis'] #dict i'm working with below
Чтобы получить список [id, value] (а не только список значений), я использую это:
[[id,val] for diff, val, id in sorted((abs(x['value']-value), x['value'], x['npi']) for x in snpis)[:6]]
Что производит это:
[[u'1932190360', 2672],
[u'1114020336', 3264],
[u'1538182779', 995],
[u'1801894142', 497],
[u'1336147685', 284],
[u'1912989989', 232]]
ИЗМЕНИТЬ
На самом деле мне было очень легко манипулировать Raymond ответом, если вы имеете дело с dict (или списком списков).
from heapq import nsmallest
[[i['npi'], i['value']] for i in nsmallest(6, snpis, key=lambda x: abs(x['value']-value))]
Это приведет к тому же, что и предыдущий вывод.
И этот
nsmallest(6, snpis, key=lambda x: abs(x['value']-value)) будет производить вместо этого dict.