Можно быстро установить разницу с плавающей точкой, используя numpy, если элементы равны некоторому допуску

Question

У меня есть два списка чисел с плавающей точкой, и я хочу рассчитать разницу между ними.

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

Но есть ли способ написать это с пустяком и вернуть скорость?

Обратите внимание, что я хочу, чтобы оставшиеся точки все еще имели свою полную точность, поэтому сначала округлите числа, а затем выполните разность наборов, вероятно, не путь вперед (или это так?:))

Отредактировано, чтобы добавить решение, основанное на 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,:]

В полученном массиве столько строк, сколько точек во всех точках, и столько же столбцов, сколько точек в удаленных точках. Затем вы можете манипулировать этим любым способом (например, рассчитать абсолютное значение), что дает вам логический массив. Чтобы узнать, какие строки имеют какие-либо совпадения (абсолютная разница <.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 и изменить сравнение, чтобы избавиться от отрицания.)

(Осторожно, в коде могут быть ошибки печати.)