NumPy:具有模糊/容忍比较的np.lexsort

Question

我有一个N三维点的集合.这些存储为np.array具有的形状(N,3).所有点都是不同的,任何两点之间的最小距离~1e-5.我正在寻找一种获得迭代这些点的顺序的方法,这些顺序既与它们当前的顺序无关,np.array又与单个组件的小扰动无关.

满足第一个要求的最简单方法是np.lexsort使用

np.lexsort(my_array.T)

但是在健壮性部门失败了:

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如果一个轴中的两个值在公差范围内,它将移动到下一个轴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()数组可以在一定程度上改善这种情况。