NumPy: np.lexsort z rozmytymi/tolerancyjnymi porównaniami

Question

Mam kolekcję N punktów w trzech wymiarach. Są one przechowywane jako np.array o kształcie (N,3). Wszystkie punkty są różne, z minimalną odległością między dowolnymi dwoma punktami będącymi ~1e-5. Szukam sposobu na uzyskanie zamówienia, w którym można powtórzyć te punkty, co jest zarówno niezależne od ich obecnego porządku w np.array i odporne na małe zakłócenia poszczególnych składników.

Najprostsze sposoby zaspokajania pierwszy warunek jest z np.lexsort z

np.lexsort(my_array.T) 

jednak to się nie powiedzie w dziale solidność:

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

gdzie możemy zobaczyć, że w tym przypadku zamawiania jest niezwykle wrażliwy na perturbacje. Dlatego szukam rozmytego wariantu np.lexsort, który przeniesie się na następną oś, jeśli dwie wartości w jednej osi mieszczą się w granicach tolerancji epsilon. (Lub dowolny alternatywny mechanizm, który pozwoli mi uzyskać zamówienie).

Ponieważ moja aplikacja ma kilka milionów takich kolekcji, z których wszystkie wymagają zamówienia, wydajność jest czymś niepokojącym (dlatego nie ślepo próbowałam przetasować mój własny tolerancyjny np.lexsort bez uprzedniego sprawdzenia, czy jest lepszy sposób na zrobienie tego).

Answer 1

Moje ewentualne rozwiązanie było:

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 

Pragnę zauważyć, że jest to nieco ponad zaprojektowane dla problemu opisanego powyżej. Podobnie jak w przypadku np.lexsort, tablica musi zostać przekazana w transponowanej postaci. Parametr idx pozwala kontrolować, które wskaźniki są brane pod uwagę (pozwalając na proste zamaskowanie elementów). W przeciwnym razie zrobi to list(xrange(0, N)).

Wydajność nie jest dobra. Jest to jednak głównie konsekwencja typów skalarnych NumPy zachowujących się źle. Wywołanie wcześniejszej tablicy tolist() poprawia nieco sytuację.

Answer 2

Natknąłem się na ten sam problem, tylko w 2D z listą współrzędnych x, y, które musiałem posortować z tolerancją. Skończyło się na piśmie, to rozwiązanie oparte na numpy.lexsort:

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 

który sortuje to:

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

do tego (tolerance = 0.1):

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

nie mam czasu na uogólnienia, więc działa to tylko w 2D i obecnie nie masz kontroli nad kolejnością sortowania (najpierw przez drugą kolumnę, a potem przez pierwszą).