Soru tamsayıların listesinden belirli bir değere en yakın sayıyı al


Tam sayıların bir listesi verildiğinde, girişte verdiğim sayıya en yakın sayıyı bulmak istiyorum:

>>> myList = [4, 1, 88, 44, 3]
>>> myNumber = 5
>>> takeClosest(myList, myNumber)
...
4

Bunu yapmanın hızlı bir yolu var mı?


108
2017-08-27 11:32


Menşei


Listede bunun gerçekleştiğine dair indekse ne dersiniz? - Charlie Parker
Olası kopya Tamamen sıralamayan bir listedeki değere en yakın bir öğenin dizinini bulma - sancho.s
@ sancho.s Güzelce lekeli. Bu sorunun cevabı, diğer sorudakilerden çok daha iyi. Bu yüzden diğerini kapatmak için oy kullanacağım. - Jean-François Corbett


Cevaplar:


Listenin sıralandığından emin olmazsak, gömme min() fonksiyonBelirtilen numaradan minimum mesafeye sahip elemanı bulmak için.

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

Ayrıca, int anahtarlarıyla dicts ile çalıştığını unutmayın. {1: "a", 2: "b"}. Bu yöntem O (n) zamanını alır.


Liste zaten sıralıysa veya diziyi sıralama fiyatını sadece bir kez ödeyebilirseniz, görüntülenen ikiye ayırma yöntemini kullanın. @ Lauritz'in cevabı sadece O (log n) zamanını alır (bir listenin zaten sıralı olup olmadığını kontrol etmek O (n) ve sıralama O (n log n) olduğunu unutmayın.)


227
2017-08-27 11:37



Karmaşıklıkta konuşmak, bu O(n), nerede küçük bir hack bisect size büyük bir iyileştirme verecek O(log n) (giriş diziniz sıralanırsa). - mic_e
@mic_e: Bu sadece Lauritz'in cevabı. - kennytm
Listede bunun gerçekleştiği endeksi de geri döndürmeye ne dersiniz? - Charlie Parker
@CharlieParker Kendi uygulamanızı oluşturun min, bir sözlük üzerinde çalıştırın (items()) bir liste yerine ve sonunda değer yerine anahtarı döndür. - Dustin Oprea
Veya kullan numpy.argmin yerine min değeri yerine indeksi almak için. - MPath


Yazmaya çabuk davranacak şekilde hızlıca yürütmeyi kastediyorsanız, min meli değil Çok dar bir kullanım durumunda hariç, seçiminizdeki silahınız olun. min çözüm listede her sayıyı incelemek gerekiyor ve her sayı için bir hesaplama yapın. kullanma bisect.bisect_left bunun yerine neredeyse her zaman daha hızlıdır.

"Hemen hemen" aslında bisect_left listenin çalışacak şekilde sıralanmasını gerektirir. Umarız, kullanım durumunuz, listeyi bir kez sıralayabileceğiniz ve daha sonra yalnız bırakabileceğiniz bir durumdur. Aramasanız bile, her aramanızdan önce sıralamanız gerekmediği sürece takeClosest, bisect modül muhtemelen üstte çıkacaktır. Şüpheniz varsa, ikisini de deneyin ve gerçek dünyadaki farklılığa bakın.

from bisect import bisect_left

def takeClosest(myList, myNumber):
    """
    Assumes myList is sorted. Returns closest value to myNumber.

    If two numbers are equally close, return the smallest number.
    """
    pos = bisect_left(myList, myNumber)
    if pos == 0:
        return myList[0]
    if pos == len(myList):
        return myList[-1]
    before = myList[pos - 1]
    after = myList[pos]
    if after - myNumber < myNumber - before:
       return after
    else:
       return before

Bisect, bir listeyi tekrar tekrar yarı yarıya azaltarak ve hangi yarıyı buldukça çalışır myNumber orta değere bakarak içeride olmak zorunda. Bu, onun bir çalışma süresine sahip olduğu anlamına gelir O (log n) aksine O (n) çalışma süresi en yüksek oylanan cevap. İki yöntemi karşılaştırırsak ve her ikisi de bir sıralı olarak tedarik edersek myList, bunlar sonuçlar:

$ python -m timeit -s "
en yakın ithalattan takeClosest
rastgele içe aktarma
a = aralık (-1000, 1000, 10) "" takeClosest (bir, randint (-1100, 1100)) "

100000 döngü, en iyi 3: döngü başına 2,22 usec

$ python -m timeit -s "
en yakın içe aktarma ile
rastgele içe aktarma
a = aralık (-1000, 1000, 10) "" with_min (a, randint (-1100, 1100)) "

Döngü başına 10000 döngü, en iyi 3: 43,9 usec

Yani bu özel testte, bisect neredeyse 20 kat daha hızlıdır. Daha uzun listeler için fark daha büyük olacaktır.

Eğer önkoşulları kaldırarak oyun alanını düzeltirsek myList sıralanmalı mı? Diyelim ki listenin bir kopyasını sıraladık her zaman  takeClosest denilirken min Çözüm değiştirilmemiş. Yukarıdaki testte 200 maddelik listeyi kullanarak bisect çözüm hala en hızlı, ancak yaklaşık% 30'dur.

Bu sıralama adımı göz önüne alındığında, bu garip bir sonuçtur O (n log (n))! Tek neden min hala kaybediyor sıralama sıralama, yüksek düzeyde optimize edilmiş c kodunda yapılır minher öğe için bir lambda işlevini çağırmaya devam etmelidir. Gibi myList büyüklükte büyür, min Çözüm sonunda daha hızlı olacaktır. Her şeyi kendi lehine yığmamız gerektiğine dikkat edin. min kazanmak için çözüm.


108
2017-08-27 11:37



Kendini sıralama O (N log N), bu yüzden N büyük hale geldiğinde daha yavaş olacaktır. Örneğin, kullanırsanız a=range(-1000,1000,2);random.shuffle(a) bunu bulacaksın takeClosest(sorted(a), b) daha yavaş olur. - kennytm
@KennyTM Size bunu vereceğim ve cevabımla işaret edeceğim. Ama uzun zaman getClosest her tür için bir kereden fazla çağrılabilir, bu daha hızlı olacak ve bir kez kullanım durumu için, bu bir no-brainer. - Lauritz V. Thaulow
Listede bunun gerçekleştiği endeksi de geri döndürmeye ne dersiniz? - Charlie Parker


>>> takeClosest = lambda num,collection:min(collection,key=lambda x:abs(x-num))
>>> takeClosest(5,[4,1,88,44,3])
4

bir lambda "anonim" bir işlev yazmanın özel bir yoludur (bir adı olmayan bir işlev). İstediğiniz herhangi bir ismi atayabilirsiniz, çünkü bir lambda bir ifadedir.

Yukarıdakileri yazmanın "uzun" yolu şöyle olurdu:

def takeClosest(num,collection):
   return min(collection,key=lambda x:abs(x-num))

8
2017-12-16 14:36



Bununla birlikte, lambda'nın isimlere atanmasının, PEP 8. - evertheylen


def closest(list, Number):
    aux = []
    for valor in list:
        aux.append(abs(Number-valor))

    return aux.index(min(aux))

Bu kod size listedeki en yakın numaraların dizinini verecektir.

KennyTM tarafından verilen çözüm genel olarak en iyisidir, ancak durumlarda kullanamazsınız (brython gibi), bu işlev


6
2017-08-27 11:36





Listede yineleyin ve mevcut en yakın sayıyı abs(currentNumber - myNumber):

def takeClosest(myList, myNumber):
    closest = myList[0]
    for i in range(1, len(myList)):
        if abs(i - myNumber) < closest:
            closest = i
    return closest

3
2018-06-02 18:19



ayrıca indeksi de iade edebilirsiniz. - Charlie Parker
! Yanlış! Olmalı if abs(myList[i] - myNumber) < abs(closest - myNumber): closest = myList[i];. Yine de bu değeri daha iyi saklayın. - lk_vc


Lauritz'in bisect'i kullanma önerisinin aslında MyList'ten MyNumber'e en yakın değeri bulmadığını unutmamak önemlidir. Bunun yerine, bisect bir sonraki değeri bulur. sipariş MyList'de MyList'ten sonra. Yani OP'nin durumunda aslında 4 pozisyonunun yerine 44 pozisyonu elde edecektiniz.

>>> myList = [1, 3, 4, 44, 88] 
>>> myNumber = 5
>>> pos = (bisect_left(myList, myNumber))
>>> myList[pos]
...
44

5'e en yakın değeri elde etmek için listeyi bir diziye dönüştürmeyi ve numpy'den argmin kullanmayı deneyebilirsiniz.

>>> import numpy as np
>>> myNumber = 5   
>>> myList = [1, 3, 4, 44, 88] 
>>> myArray = np.array(myList)
>>> pos = (np.abs(myArray-myNumber)).argmin()
>>> myArray[pos]
...
4

Bunun ne kadar hızlı olduğunu bilmiyorum, tahminim "çok değil" olurdu.


1
2017-07-25 00:36



Lauritz'in işlevi doğru çalışıyor. Sadece bisect_left kullanıyorsunuz, ancak Lauritz ek kontrol sağlayan bir takeClosest (...) fonksiyonunu önerdi. - Kanat
NumPy'yi kullanacaksanız, kullanabilirsiniz np.searchsorted yerine bisect_left. Ve Kakat haklı - Lauritz'in çözümü yapar İki adaydan hangisinin daha yakın olduğunu seçen kodu içerir. - John Y


Gustavo Lima'nın cevabını genişletmek. Aynı şey tamamen yeni bir liste oluşturmadan da yapılabilir. Listedeki değerler, FOR döngü ilerler.

def f_ClosestVal(v_List, v_Number):
"""Takes an unsorted LIST of INTs and RETURNS INDEX of value closest to an INT"""
for _index, i in enumerate(v_List):
    v_List[_index] = abs(v_Number - i)
return v_List.index(min(v_List))

myList = [1, 88, 44, 4, 4, -2, 3]
v_Num = 5
print(f_ClosestVal(myList, v_Num)) ## Gives "3," the index of the first "4" in the list.

0