NumPy：ファジー/耐性比較付きのnp.lexsort

Question

私はNのコレクションを3次元で持っています。これらは(N,3)の形のnp.arrayとして保存されます。すべての点は、任意の2点間の最小距離が~1e-5であり、別個である。私はnp.arrayの現在の注文とは独立しており、個々のコンポーネントの小さな摂動に対して堅牢であるこれらのポイントを反復するための注文を得る手段を探しています。

最初の要件を満たす最も簡単な手段は

np.lexsort(my_array.T) 

とnp.lexsortであるが、これは堅牢性部門で失敗します。私たちは、このインスタンスでは順序が非常にあることがわかります

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

を摂動に敏感です。私はnp.lexsortのファジィ変種を探しています。これは、ある軸の2つの値がepsilonの許容値内にある場合、次の軸に移動します。 （あるいは私が注文を得ることを可能にする任意の代替メカニズム）

私のアプリケーションは、これらのコレクションのすべてが注文を必要とするものであり、パフォーマンスは何かが懸念されています最初にそれを行うよりよい方法があるかどうかを見ずに、自分の寛容なnp.lexsortを動かす）。

Answer 1

私の最終的な解決策をした

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 

私は、これは、上述の問題のために設計上、わずかであることに注意してください。 np.lexsortと同様に、配列は転置された形式で渡されなければなりません。 idxパラメータは、どのインデックスが考慮されるかを制御することを可能にする（要素を厳密にマスクすることを可能にする）。それ以外の場合はlist(xrange(0, N))となります。

パフォーマンスはあまり良くありません。しかし、これは主に、NumPyスカラー型がひどく振る舞う結果です。あらかじめ配列上にtolist()を呼び出すと、状況が多少改善されます。

Answer 2

私は公差でソートする必要があったx、y座標のリストを持つ2Dでのみ、同じ問題に遭遇しました。 、私は一般化のための時間を持っていなかった

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

：この中

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）：これをソートした

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 

：私はnumpy.lexsortに基づいて、このソリューションを書き終わりましたこれは2Dでのみ機能し、現在はソートの順序を制御することはできません（最初は2番目の列、次に1番目の列）。