python - 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() 可以稍微改善这种情况。