Python/Numpy - Dizini, Bir Değere En Yakın Dizide Bul Bazı Değerlere En Yakın

Question

Her zaman artan sırada (ama her zaman eşit aralıklı değil) bir dizi değer var. Başka bir tek değere sahibim, x İndeksi t [index] x'e en yakın olacak şekilde bulmam gerekiyor. Işlev x < t.min() için sıfır ve x> t.max() için maksimum dizin (veya -1) döndürmelidir.

Bunu yapmak için iki işlev yazdım. Birincisi, f1, bu basit zamanlama testinde daha hızlıdır. Ama ikincisinin nasıl sadece bir satır olduğunu seviyorum. Bu hesaplama, potansiyel olarak saniyede birçok kez büyük bir dizi üzerinde yapılacaktır.

Herkes, bir başkasıyla karşılaştırılabilir zamanlama ile başka bir işleve gelebilir mi, ancak daha temiz görünümlü bir kodla? İlk önce daha hızlı bir şey ne dersiniz (hız en önemlisidir)?

Teşekkürler!

Kodu:

import numpy as np 
import timeit 

t = np.arange(10,100000)   # Not always uniform, but in increasing order 
x = np.random.uniform(10,100000) # Some value to find within t 

def f1(t, x): 
    ind = np.searchsorted(t, x) # Get index to preserve order 
    ind = min(len(t)-1, ind)  # In case x > max(t) 
    ind = max(1, ind)    # In case x < min(t) 
    if x < (t[ind-1] + t[ind])/2.0: # Closer to the smaller number 
     ind = ind-1 
    return ind 

def f2(t, x): 
    return np.abs(t-x).argmin() 

print t,   '\n', x,   '\n' 
print f1(t, x), '\n', f2(t, x), '\n' 
print t[f1(t, x)], '\n', t[f2(t, x)], '\n' 

runs = 1000 
time = timeit.Timer('f1(t, x)', 'from __main__ import f1, t, x') 
print round(time.timeit(runs), 6) 

time = timeit.Timer('f2(t, x)', 'from __main__ import f2, t, x') 
print round(time.timeit(runs), 6) 

Answer 1

Bu, Python 3.2-win32, numpy 1.6.0 benim için (çok daha hızlı göründüğünden daha yavaş olabilir):

from bisect import bisect_left 
def f3(t, x): 
    i = bisect_left(t, x) 
    if t[i] - x > 0.5: 
     i-=1 
    return i 

---

Çıktı:

diziniz sıralanır yana

[ 10 11 12 ..., 99997 99998 99999] 
37854.22200356027 
37844 
37844 
37844 
37854 
37854 
37854 
f1 0.332725 
f2 1.387974 
f3 0.085864 

Answer 2

Kullanım searchsorted:

t = np.arange(10,100000)   # Not always uniform, but in increasing order 
x = np.random.uniform(10,100000) 

print t.searchsorted(x) 

Düzenleme:

Ah evet, sen olduğunu f1 böyle yapıyorlarsa görüyoruz. Belki f3'ün altında okumak f1'den daha kolaydır.

def f3(t, x): 
    ind = t.searchsorted(x) 
    if ind == len(t): 
     return ind - 1 # x > max(t) 
    elif ind == 0: 
     return 0 
    before = ind-1 
    if x-t[before] < t[ind]-x: 
     ind -= 1 
    return ind 

Answer 3

np.searchsorted ikili arama (yarım içinde her zaman bir dizi bölünmüş) 'dir. Bu yüzden, sıfır döndürmek yerine x'den daha küçük olan son değeri döndürecek şekilde uygulamanız gerekir. (here itibaren) bu algoritmanın en

Görünüş:

def binary_search(a, x): 
    lo=0 
    hi = len(a) 
    while lo < hi: 
     mid = (lo+hi)//2 
     midval = a[mid] 
     if midval < x: 
      lo = mid+1 
     elif midval > x: 
      hi = mid 
     else: 
      return mid 
    return lo-1 if lo > 0 else 0 

sadece son satırı yerini ( return -1 idi). Ayrıca argümanlar değiştirildi.

döngüler Python yazılır gibi, (Not benchmarked) ilki ...