NumPy: bulanık/toleranslı karşılaştırmalar ile np.lexsort

Question

Üç boyutta N puanlık bir koleksiyona sahibim. Bunlar, (N,3) biçiminde np.array olarak depolanır. Tüm noktalar, iki nokta arasındaki minimum mesafe ~1e-5 olarak farklıdır. np.array'daki mevcut siparişlerinden bağımsız olan ve tek tek bileşenlerin küçük pertürbasyonlarına karşı dayanıklı olan bu noktalar üzerinden yineleme yapılacak bir sipariş alma aracı arıyorum. bu olayda görebiliriz nerede

In [6]: my_array = np.array([[-0.5, 0, 2**0.5], [0.5, 0, 2**0.5 - 1e-15]]) 

In [7]: my_array[np.lexsort(my_array.T)] 
Out[7]: 
array([[ 0.5  , 0.  , 1.41421356], 
     [-0.5  , 0.  , 1.41421356]]) 

sipariş son derece geçerli:

ilk gereksinimi karşılayacak en basit araçları

np.lexsort(my_array.T) 

ancak bu sağlamlık bölümünde başarısız olan np.lexsort ile pertürbasyonlara duyarlı. Bu nedenle np.lexsort no'lu bulanık bir varyant arıyoruz, eğer bir eksende iki değer epsilon toleransının içinde ise bir sonraki eksene hareket edecektir. (Ya da sipariş vermeme izin verecek herhangi bir alternatif mekanizma.)

Uygulamamın hepsinin sipariş vermesi gereken birkaç milyonu bu koleksiyonlara sahip olduğundan, performans endişe verici bir şeydir (bu yüzden körü körüne denemedim) kendi hoşgörülü np.lexsort'umu ilk önce yapmanın daha iyi bir yolu olup olmadığını görmeden döndürmek için).

Answer 1

Benim nihai çözümün oldu:

def fuzzysort(arr, idx, dim=0, tol=1e-6): 
    # Extract our dimension and argsort 
    arrd = arr[dim] 
    srtdidx = sorted(idx, key=arrd.__getitem__) 

    i, ix = 0, srtdidx[0] 
    for j, jx in enumerate(srtdidx[1:], start=1): 
     if arrd[jx] - arrd[ix] >= tol: 
      if j - i > 1: 
       srtdidx[i:j] = fuzzysort(arr, srtdidx[i:j], dim + 1, tol) 
      i, ix = j, jx 

    if i != j: 
     srtdidx[i:] = fuzzysort(arr, srtdidx[i:], dim + 1, tol) 

    return srtdidx 

Bu biraz aşırı mühendislik yukarıda anlatılan sorunu için olduğunu unutmayın. np.lexsort ile olduğu gibi dizi translated formda geçirilmelidir. idx parametresi, hangi endekslerin göz önünde bulundurulduğunu kontrol etmeyi sağlar (öğelerin kaba bir şekilde maskelenmesine izin verir). Aksi halde list(xrange(0, N)) yapacaktır.

Performans harika değil. Bununla birlikte, bu, çoğunlukla kötü davranan NumPy skaler tiplerinin bir sonucudur. Dizide tolist() aranması durumu biraz iyileştirir.

Answer 2

Aynı problemde, sadece 2B'de, bir toleransla sıralamak için ihtiyacım olan x, y koordinatlarının listesiyle tökezledim. Ben genelleme için zaman yoktu

array([[ 0. , 0.1 ], 
     [ 1. , 0. ], 
     [ 1. , 0. ], 
     [ 2. , 0.06], 
     [ 1. , 2. ], 
     [ 5. , 4. ], 
     [ 11. , 4. ], 
     [ 2. , 9. ], 
     [ 9. , 9. ], 
     [ 7. , 10. ]]) 

: bu işe

array([[ 11. , 4. ], 
     [ 1. , 0. ], 
     [ 7. , 10. ], 
     [ 2. , 9. ], 
     [ 9. , 9. ], 
     [ 5. , 4. ], 
     [ 1. , 2. ], 
     [ 1. , 0. ], 
     [ 0. , 0.1 ], 
     [ 2. , 0.06]]) 

(tolerance = 0.1): Bu sıralar hangi

def tolerance_sort(array, tolerance): 
    array_sorted = np.copy(array[np.lexsort((array[:, 0], array[:, 1]))]) 
    sort_range = [0] 
    for i in range(array.shape[0] - 1): 
     if array_sorted[i + 1, 1] - array_sorted[i, 1] <= tolerance: 
      sort_range.append(i + 1) 
      continue 
     else: 
      sub_arr = np.take(array_sorted, sort_range, axis=0) 
      sub_arr_ord = np.copy(
       sub_arr[np.lexsort((sub_arr[:, 1], sub_arr[:, 0]))]) 
      array_sorted[slice(sort_range[0], sort_range[-1] + 
           1)] = sub_arr_ord 
      sort_range = [i + 1] 
    return array_sorted 

: Ben numpy.lexsort dayalı bu çözüm yazma sona erdi Yani bu sadece 2B'de çalışır ve şu anda sıralama sırasına göre kontrolünüz yoktur (ilk önce ikinci sütuna göre ve sonra ilk olarak).