Ricerca di k numeri più vicini ad un dato numero

Question

Dire che ho una lista [1,2,3,4,5,6,7]. Voglio trovare i 3 numeri più vicini, per esempio, 6.5. Quindi il valore restituito sarà [5,6,7].

Trovare un numero più vicino non è poi così difficile in pitone, che può essere fatto utilizzando

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

Ma sto cercando di non mettere un anello intorno a questo per trovare k numeri più vicini. Esiste un modo pititico per raggiungere il compito di cui sopra?

Answer 1

La funzione heapq.nsmallest() farà questo ordinatamente e in modo efficiente:

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

Essenzialmente questo dice: "Dammi i valori di tre ingressi che hanno la differenza assoluta più bassa dal numero 6.5" .

L'algoritmo per nsmallest rende un singolo passaggio sui dati, mantenendo non più dei n migliori valori nella memoria in qualsiasi momento (ciò significa che funziona con qualsiasi iteratore ingresso, è cache efficiente, e spazio-efficiente).

L'algoritmo aggiunge solo nuovi valori all'heap quando viene trovato un nuovo valore "migliore". Di conseguenza, riduce al minimo il numero di confronti effettuati. Ad esempio, se si cercano i 100 migliori valori su 1.000.000 di input casuali, in genere si ottengono meno di 1.008.000 confronti (circa lo 0,8% in più confronta rispetto all'utilizzo di min() per trovare il valore singolo migliore).

Il key functions per min(), nsmallest() e filtrate(), garantiscono che la funzione chiave viene chiamato esattamente una volta per ogni valore nell'input iterabile. Ciò significa che questa tecnica sarà efficiente anche per esempi più complessi e interessanti del problema del valore n-più vicino (ad esempio sound the most alike, più vicino colors, smallest diffs, poche mutazioni genetiche, distanza euclidea, ecc.).

Sia nsmallest() e ordinato() restituirà la graduatoria in ordine di vicinanza (legami sono regolate con cui valore è stato visto prima).

Per coloro che sono interessati, vi è un'analisi in qualche modo implicita del numero previsto di confronti here e here.Rapido riepilogo:

• caso medio per gli ingressi casuali: n + k * (log(k, 2) * log(n/k) + log(k, 2) + log(n/k))
• migliore caso per gli ingressi ascendenti: n + k * log(k, 2)
• caso peggiore per gli ingressi discendente: n * log(k, 2)

Answer 2

Si potrebbe calcolare distanze, e ordinare:

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

Questo fa il seguente:

1. creare una sequenza di tuple (d, x) dove d è la distanza al vostro obiettivo
2. selezionare la prima k elementi di quell'elenco
3. Estrarre solo i valori numerici dal risultato, scartare ing la distanza

Answer 3

Entrambe le risposte sono state buone, e Greg era a destra, la risposta di Raymond è più di alto livello e più facile da implementare, ma ho costruito la risposta di Greg perché era più facile da manipolare per soddisfare le mie necessità.

Nel caso qualcuno stia cercando un modo per trovare i valori più vicini da un elenco di dict.

mio dict assomiglia a questo, in cui NPI è solo un identificatore che ho bisogno insieme al valore:

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 

per ottenere un [id, value] lista (non solo un elenco di valori), io uso questo:

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

che produce questo:

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

EDIT

In realtà ho trovato molto semplice anche manipolare la risposta di Raymond, se si tratta di un ditt (o un elenco di elenchi).

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

Questo produrrà lo stesso dell'uscita di cui sopra.

E questo

nsmallest(6, snpis, key=lambda x: abs(x['value']-value)) produrrà invece un dict.