6

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

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

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 而不先看看是否有更好的方法它）。

4

2 回答 2

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()数组可以在一定程度上改善这种情况。

于 2014-06-03T20:58:32.217 回答
0

我偶然发现了同样的问题，只是在 2D 中带有 x、y 坐标列表，我需要用容差进行排序。我最终基于以下内容编写了此解决方案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

对此进行排序：

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）：

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

我没有时间进行概括，所以这只适用于 2D，目前你无法控制排序的顺序（首先是第二列，然后是第一列）。

于 2017-11-30T14:47:49.900 回答