NumPy: np.lexsort con confronti sfocati/tolleranti

Question

Ho una raccolta di punti N in tre dimensioni. Questi sono memorizzati come np.array con una forma di (N,3). Tutti i punti sono distinti con la distanza minima tra due punti qualsiasi ~1e-5. Sto cercando un modo per ottenere un ordine in cui iterare su questi punti che è sia indipendente dal loro ordine corrente nel np.array che da perturbazioni da robuste a piccole dei singoli componenti.

I mezzi più semplici per soddisfare il primo requisito è con np.lexsort con

np.lexsort(my_array.T) 

tuttavia questo non riesce nel reparto robustezza:

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

dove possiamo vedere che in questo caso l'ordine è estremamente sensibile alle perturbazioni. Pertanto, sto cercando una variante fuzzy di np.lexsort che si sposterà sull'asse successivo se due valori in un asse rientrano nella tolleranza di epsilon. (O qualsiasi altro meccanismo alternativo che mi permetta di ottenere un ordinamento.)

Poiché la mia applicazione ha diversi milioni di queste raccolte, che devono essere ordinate, le prestazioni sono una preoccupazione (motivo per cui non ho provato ciecamente rotolare il mio np.lexsort tollerante senza prima vedere se c'è un modo migliore per farlo).

Answer 1

mio eventuale soluzione era:

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 

faccio notare che questo è un po 'sovra-ingegnerizzato per il problema descritto in precedenza. Come con np.lexsort, la matrice deve essere passata in forma trasposta. Il parametro idx consente di controllare quali indici sono considerati (tenendo conto che gli elementi vengono mascherati in modo rozzo). Altrimenti lo farà list(xrange(0, N)).

Le prestazioni non sono eccezionali. Tuttavia, questo è principalmente una conseguenza dei tipi scalari di NumPy che si comportano male. Chiamando in anticipo lo tolist() sulla matrice, la situazione migliora leggermente.

Answer 2

Mi sono imbattuto nello stesso problema, solo in 2D con un elenco di coordinate x, che avevo bisogno di ordinare con una tolleranza. Ho finito per scrivere questa soluzione basata su 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 

che ordina questo:

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

in questo (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. ]]) 

non ho avuto il tempo per la generalizzazione, quindi funziona solo in 2D e al momento non si ha alcun controllo sull'ordine dell'ordinamento (prima dalla seconda colonna e poi dal primo).