python - 如果元素等于某个容差，我可以使用 numpy 快速设置 float 差异吗

Question

我有两个 float 列表，我想计算它们之间的集合差。

我最初使用 numpy 编写了以下代码:

aprows = allpoints.view([('',allpoints.dtype)]*allpoints.shape[1])
rprows = toberemovedpoints.view([('',toberemovedpoints.dtype)]*toberemovedpoints.shape[1])
diff = setdiff1d(aprows, rprows).view(allpoints.dtype).reshape(-1, 2)

这对于整数之类的东西很有效。如果二维点的浮点坐标是某些几何计算的结果，则存在有限精度和舍入误差的问题，导致集合差值错过某些等式。现在我采取了慢得多的方法:

diff = []
for a in allpoints: 
    remove = False
    for p in toberemovedpoints:
        if norm(p-a) < 0.1:
            remove = True
    if not remove:
        diff.append(a)
return array(diff)

但是有没有办法用 numpy 编写这个并恢复速度？

请注意，我希望剩余的点仍然具有完整的精度，因此首先对数字进行四舍五入，然后进行设置差异可能不是前进的方向(或者是吗？:))

编辑添加基于 scipy.KDTree 的解决方案，该解决方案似乎有效:

def remove_points_fast(allpoints, toberemovedpoints):
    diff = []
    removed = 0
    # prepare a KDTree
    from scipy.spatial import KDTree
    tree = KDTree(toberemovedpoints,  leafsize=allpoints.shape[0]+1)
    for p in allpoints:
        distance, ndx = tree.query([p], k=1)
        if distance < 0.1:
            removed += 1
        else:
            diff.append(p)
    return array(diff), removed

Answer 1

如果您想使用矩阵形式执行此操作，则较大的数组会消耗大量内存。如果这并不重要，那么您可以通过以下方式获得差异矩阵:

diff_array = allpoints[:,None] - toberemovedpoints[None,:]

生成的数组的行数与 allpoints 中的点数一样多，列数与 toberemovedpoints 中的点数一样多。然后你可以以任何你想要的方式操作它(例如计算绝对值)，这会给你一个 bool 数组。要查找哪些行有任何命中(绝对差 < .1)，请使用 numpy.any:

hits = numpy.any(numpy.abs(diff_array) < .1, axis=1)

现在您有了一个向量，其项目数与差异数组中的行数相同。您可以使用该向量来索引所有点(否定，因为我们想要非匹配点):

return allpoints[-hits]

这是一种很笨拙的方法。但是，正如我上面所说，它需要大量内存。

<小时/>

如果你有更大的数据，那么你最好逐点进行。像这样的事情:

return allpoints[-numpy.array([numpy.any(numpy.abs(a-toberemoved) < .1) for a in allpoints ])]

这在大多数情况下应该表现良好，并且内存使用量比矩阵解决方案低得多。 (出于风格原因，您可能需要使用 numpy.all 而不是 numpy.any，然后翻转比较以消除否定。)

(请注意，代码中可能存在打印错误。)