Bir listenin [1,2,3,4,5,6,7] olduğunu varsayalım. 6'ya en yakın 3 numarayı bulmak istiyorum. Ardından döndürülen değer [5,6,7] olur.Belirli bir numaraya en yakın numaraları bulma
biri en yakın sayı bulma
min(myList, key=lambda x:abs(x-myNumber))
kullanılarak yapılabilir Ama yakın numaralar k bulmak için bu etrafında bir döngü koymak için değil çalışıyorum ki, piton o zor değildir. Yukarıdaki görevi yerine getirmenin pythonik bir yolu var mı?
heapq.nsmallest() fonksiyon düzgünce ve verimli yapacak:
>>> 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]
Esasen bu "Bana numara 6.5 itibaren en düşük mutlak farkına sahip üç giriş değerlerini ver" diyor .
nsmallest için algoritma, bu herhangi bir giriş iterasyon ile çalışır anlamına gelir (her zaman bellekte N en iyi değerleri en fazla tutarak, veriler üzerinde tek bir geçiş yapar önbellek etkilidir ve alan etkili).
Algoritma yeni bir "en iyi" değer bulunduğunda yalnızca yığına yeni değerler ekler. Buna göre, yapılan karşılaştırmaların sayısını en aza indirir. Örneğin, 1.000.000 rastgele girdiden 100 en iyi değeri arıyorsanız, genellikle 1.008.000 karşılaştırmadan daha azını yapar (en iyi değeri bulmak için min()'u kullanmanın yaklaşık% 0.8'i daha fazladır).
key functions min(), nsmallest() ve kriteri () tüm önemli fonksiyon girişi iterable tam olarak bir kez değer başına adlandırılır olduğunu garanti eder. Bu, bu tekniğin n-en yakın değer probleminin daha karmaşık ve ilginç örnekleri için (yani, sound the most alike, en yakın colors, smallest diffs, en az genetik mutasyonlar, Öklid mesafesi, vb.) Daha verimli olacağı anlamına gelir.İkisi nsmallest() ve sıralanmış() yakınlık tarafından sipariş listesi sıralaması dönecektir (kravatlar ödendiği tarafından değer birinci görüldü).
İlgilenenler için, beklenen karşılaştırma sayısı here ve here'un biraz ilgili bir analizi vardır.azalan girişler için n + k * log(k, 2)
n + k * (log(k, 2) * log(n/k) + log(k, 2) + log(n/k))n * log(k, 2)sıralayabilir mesafeleri hesaplamak ve olabilir:
[n for d, n in sorted((abs(x-myNumber), x) for x in myList)[:k]]
Bu
aşağıdakileri yapar:d
(d, x) dizisi oluşturma k bu listenin öğeleri'sorted', bir anahtar işlevi kabul eder. – DSM
Oh, bu doğru ve gerçekten de OP bu yolun en iyisiydi! Her neyse, Raymond'un cevabı daha iyi. –
Her iki cevap iyiydi ve Greg Doğru, Raymond'un cevabı daha yüksek seviyeli ve uygulanması daha kolay, ama Greg'in cevabına dayanarak yaptım çünkü ihtiyacımı karşılamak için manipüle edilmesi daha kolaydı.
durumda herkes dicts listesinden n en yakın değerleri bulmak için bir yol arıyor.Benim dict npi ben değeriyle birlikte gerek sadece bir tanımlayıcı olduğu bu gibi görünüyor:
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
bir [id, value] listesi (değerlerin sadece bir liste) almak için, bunu kullanmaktan:
[[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]]
EDIT
Ben bir dict (veya liste listesi) ile uğraşıyorsanız, Raymond'un cevabını da manipüle etmek oldukça kolay buldum.
from heapq import nsmallest
[[i['npi'], i['value']] for i in nsmallest(6, snpis, key=lambda x: abs(x['value']-value))]
Bu, yukarıdaki çıktı ile aynı sonucu verir.
Ve bu
nsmallest(6, snpis, key=lambda x: abs(x['value']-value)) yerine dicti üretecek. Eğer süslemeleri-sort-undecorate desen gerekmez
Daha sonra, belgelerin durumu şu şekildedir: "Son iki işlev n daha küçük değerler için en iyi sonucu verir. Daha büyük değerler için," sıralanmış() "işlevini kullanmak daha etkilidir? Benim için bu, “en küçük” kelimesinin, asimptotik karmaşıklıkta O'dan (nlogn) daha kötü olduğunu söylemekle eşdeğerdir, fakat bir dizi küçük 'n' için daha verimli olur. Algoritma sizin belirttiğiniz kadar verimli değildir ya da belgeleme bir şekilde yanlıştır. – Bakuriu
@Bakuriu: 'nsmallest()' O zaman karmaşıklığını (_k_ log _N_) sahip olmasıdır, _N_ konteynerin boyutu ve _k_ aradığınız küçük değerler sayısıdır. Sıralanmış() 'ın karmaşıklığı O (_n_ log _n_), ancak daha iyi bir sabit faktöre sahiptir. Yani _k/n_ 1 ile karşılaştırıldığında küçükse, 'nsmallest()' kazanır. _k_ _n_ ile karşılaştırıldığında büyürse, bir noktada 'sort()' daha iyi sabit nedeniyle kazanır. Ne Raymond ne de dokümantasyon yanlıştır, ancak dokümantasyonun “küçük” ile ilgili daha net olması gerçeği, koleksiyonun büyüklüğüne kıyasla daha küçüktür. –
@SvenMarnach: Belgelerin ihmal ettiği doğrusal zaman seçimi de mümkündür. –