python - Encontrar k números más cercanos a un número dado

closest

Question

Digamos que tengo una lista [1,2,3,4,5,6,7] . Quiero encontrar los 3 números más cercanos a, por ejemplo, 6.5. Entonces el valor devuelto sería [5,6,7] .

Encontrar un número más cercano no es tan complicado en Python, que se puede hacer usando

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

Pero estoy tratando de no poner un lazo alrededor de esto para encontrar k números más cercanos. ¿Hay una manera pitónica para lograr la tarea anterior?

Answer 1

La respuesta corta

La función heapq.nsmallest() hará esto de manera clara y eficiente:

>>> 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]

Esencialmente, esto dice: "Dame los tres valores de entrada que tienen la diferencia absoluta más baja desde el número 6.5 ".

El algoritmo y su tiempo de ejecución.

El algoritmo para nsmallest hace una sola pasada sobre los datos, manteniendo en la actualidad no más que los n mejores valores en la memoria (eso significa que funciona con cualquier iterador de entrada, es eficiente en caché y eficiente en espacio).

El algoritmo solo agrega nuevos valores al montón cuando se encuentra un nuevo valor "mejor". En consecuencia, minimiza el número de comparaciones realizadas. Por ejemplo, si está buscando los 100 mejores valores de cada 1,000,000 entradas aleatorias, generalmente hace menos de 1,008,000 comparaciones (aproximadamente un 0,8% más de las comparaciones que usar min() para encontrar el mejor valor).

Las funciones clave para min () , nsmallest () y sorted () garantizan que la función clave se llame exactamente una vez por valor en la entrada iterable. Eso significa que esta técnica será eficiente para ejemplos aún más complejos e interesantes del problema de valor n más cercano (es decir, las palabras que suenan más parecidas , los colors más cercanos, las diferencias más pequeñas , la menor cantidad de mutaciones genéticas, la distancia euclidiana, etc.).

Tanto nsmallest () como sorted () devolverán un rango de lista ordenado por proximidad (los empates se establecen según el valor que se vio primero).

Para aquellos que están interesados, hay un análisis un tanto complicado del número esperado de comparaciones here y here . Sumario rápido:

• Caso promedio para entradas aleatorias: n + k * (log(k, 2) * log(n/k) + log(k, 2) + log(n/k))
• El mejor caso para entradas ascendentes: n + k * log(k, 2)
• El peor caso para las entradas descendentes: n * log(k, 2)

Optimización para búsquedas repetidas

En los comentarios, @Phylliida, preguntó cómo optimizar para búsquedas repetidas con diferentes puntos de inicio. La clave es ordenar previamente los datos y luego usar bisect para ubicar el centro de un segmento de búsqueda pequeño:

from bisect import bisect

def k_nearest(k, center, sorted_data):
    ''Return *k* members of *sorted_data* nearest to *center*''
    i = bisect(sorted_data, center)
    segment = sorted_data[max(i-k, 0) : i+k]
    return nsmallest(k, segment, key=lambda x: abs(x - center))

Por ejemplo:

>>> s.sort()
>>> k_nearest(3, 6.5, s)
[6, 7, 5]
>>> k_nearest(3, 0.5, s)
[1, 2, 3]
>>> k_nearest(3, 4.5, s)    
[4, 5, 3]
>>> k_nearest(3, 5.0, s)
[5, 4, 6]

Tanto bisect () como nsmallest () aprovechan los datos ordenados. El primero ejecuta el tiempo O (log2 k) y el último se ejecuta en el tiempo O (n) .

Answer 2

Ambas respuestas fueron buenas, y Greg tenía razón, la respuesta de Raymond es de un nivel más alto y más fácil de implementar, pero me basé en la respuesta de Greg porque era más fácil de manipular para satisfacer mis necesidades.

En caso de que alguien esté buscando una manera de encontrar los n valores más cercanos de una lista de dictados.

Mi dict se parece a esto, donde npi es solo un identificador que necesito junto con el valor:

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

Para obtener una lista [id, value] (no solo una lista de valores), uso esto:

[[id,val] for diff, val, id in sorted((abs(x[''value'']-value), x[''value''], x[''npi'']) for x in snpis)[:6]]

Lo que produce esto:

[[u''1932190360'', 2672],
 [u''1114020336'', 3264],
 [u''1538182779'', 995],
 [u''1801894142'', 497],
 [u''1336147685'', 284],
 [u''1912989989'', 232]]

EDITAR

De hecho, también me resultó bastante fácil manipular la respuesta de Raymond, si estás tratando con un dict (o lista de listas).

from heapq import nsmallest
[[i[''npi''], i[''value'']] for i in nsmallest(6, snpis, key=lambda x: abs(x[''value'']-value))]

Esto producirá lo mismo que la salida anterior.

Y esto

nsmallest(6, snpis, key=lambda x: abs(x[''value'']-value)) producirá un dict en su lugar.

Answer 3

Podrías calcular distancias y ordenarlas:

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

Esto hace lo siguiente:

1. Cree una secuencia de tuplas (d, x) donde d es la distancia a su objetivo
2. Selecciona los primeros k elementos de esa lista.
3. Extraiga solo los valores numéricos del resultado, descartando la distancia