Нахождение k ближайших чисел до заданного числа

Скажем, у меня есть список [1,2,3,4,5,6,7]. Я хочу найти 3 ближайших номера, скажем, 6.5. Тогда возвращаемое значение будет [5,6,7].

Поиск одного ближайшего номера не так сложно в python, что можно сделать с помощью

min(myList, key=lambda x:abs(x-myNumber))

Но я стараюсь не ставить цикл вокруг этого, чтобы найти k ближайших чисел. Существует ли питонический способ достижения вышеуказанной задачи?

Ответы

Ответ 1

Функция 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)

Ответ 2

Вы можете вычислять расстояния и сортировать:

[n for d, n in sorted((abs(x-myNumber), x) for x in myList)[:k]]

Это делает следующее:

  • Создайте последовательность кортежей (d, x), где d - это расстояние до вашей цели.
  • Выберите первые k элементы этого списка
  • Извлеките только числовые значения из результата, отбросив расстояние

Ответ 3

Оба ответа были хорошими, и Грег был прав, ответ Раймонда был более высоким и более простым в реализации, но я основывался на ответе Грега, потому что было легче манипулировать, чтобы соответствовать моим потребностям.

В случае, если кто-то ищет способ найти 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.