Python Numpy获取2个二维数组之间的差异

Question

好吧，我有一个让我头疼的简单问题，基本上我有两个二维数组，充满了 [x,y] 坐标，我想比较第一个和第二个并生成一个第三个数组包含第一个数组中没有出现在第二个数组中的所有元素。这很简单，但我根本无法让它工作。大小变化很大，第一个数组可以有1000到200万个坐标，而第一个数组有1到1000个坐标。

这个操作会出现多次，第一个数组越大出现次数越多

示例：

arr1 = np.array([[0, 3], [0, 4], [1, 3], [1, 7], ])

arr2 = np.array([[0, 3], [1, 7]])

result = np.array([[0, 4], [1, 3]])

深入：基本上我有一个可变分辨率的二进制图像，它由 0 和 1 (255) 组成，我单独分析每个像素（使用已经优化的算法），但是（有意）每个执行这个函数时，它只分析一小部分像素，当它完成时，它会返回这些像素的所有坐标。问题是当它执行时运行以下代码：

ones = np.argwhere(img == 255) # ones = pixels array

它大约需要 0.02 秒，是迄今为止代码中最慢的部分。我的想法是创建一次这个变量，每次函数结束时，它都会删除已解析的像素并将新数组作为参数传递以继续，直到数组为空

Answer 1

取决于你的阵列有多大。如果他们不是太大（几千），你可以

使用广播将x中的每个点与y
使用any检查最后一个维度的不等式
使用all检查匹配

代码：

idx = (arr1[:,None]!=arr2).any(-1).all(1)

arr1[idx]

输出：

array([[0, 4],
       [1, 3]])

更新：对于更长的数据，你可以尝试设置和for循环：

set_y = set(map(tuple, y))
idx = [tuple(point) not in set_y for point in x]

x[idx]

Answer 2

不确定您打算如何处理额外维度，因为设置差异与任何过滤一样，本质上会丢失形状信息。

不管怎样，NumPy确实提供了np.setdiff1d()来优雅地解决这个问题。

编辑通过提供的说明，您似乎正在寻找一种方法来计算给定轴上的集合差异，即集合的元素实际上是数组。

NumPy 中有专门针对此的 no built-in，但制作一个并不太难。为了简单起见，我们假设操作轴是第一个（因此集合的元素是arr[i]），第一个数组中只出现唯一元素，并且数组是二维的

]

它们都是基于渐近最佳方法是构建第二个数组的 set() 然后使用它从第一个数组中过滤掉条目的想法。

在 Python / NumPy 中构建此类集合的惯用方法是使用：

set(map(tuple, arr))

到 tuple 的映射冻结 arr[i]，允许它们是可散列的，从而使它们可用于 set()。

遗憾的是，由于过滤会产生大小不可预测的结果，因此 NumPy 数组不是结果的理想容器。

要解决这个问题，可以使用：

中级 list

import numpy as np


def setdiff2d_list(arr1, arr2):
    delta = set(map(tuple, arr2))
    return np.array([x for x in arr1 if tuple(x) not in delta])

np.fromiter() followed by np.reshape()

import numpy as np


def setdiff2d_iter(arr1, arr2):
    delta = set(map(tuple, arr2))
    return np.fromiter((x for xs in arr1 if tuple(xs) not in delta for x in xs), dtype=arr1.dtype).reshape(-1, arr1.shape[-1])

NumPy's advanced indexing

def setdiff2d_idx(arr1, arr2):
    delta = set(map(tuple, arr2))
    idx = [tuple(x) not in delta for x in arr1]
    return arr1[idx]

将两个输入都转换为 set()（将强制输出元素的唯一性并将失去排序）：

import numpy as np


def setdiff2d_set(arr1, arr2):
    set1 = set(map(tuple, arr1))
    set2 = set(map(tuple, arr2))
    return np.array(list(set1 - set2))

或者，可以使用 broadcasting, np.any() and np.all():

构建高级索引

def setdiff2d_bc(arr1, arr2):
    idx = (arr1[:, None] != arr2).any(-1).all(1)
    return arr1[idx]

上述方法的某些形式最初是在中提出的。

类似的方法也可以在 Numba 中实现，遵循与上述相同的想法，但使用散列而不是实际的数组视图 arr[i]（因为 set() by Numba) 并预先计算输出大小（为了速度）：

import numpy as np
import numba as nb


@nb.njit
def mul_xor_hash(arr, init=65537, k=37):
    result = init
    for x in arr.view(np.uint64):
        result = (result * k) ^ x
    return result


@nb.njit
def setdiff2d_nb(arr1, arr2):
    # : build `delta` set using hashes
    delta = {mul_xor_hash(arr2[0])}
    for i in range(1, arr2.shape[0]):
        delta.add(mul_xor_hash(arr2[i]))
    # : compute the size of the result
    n = 0
    for i in range(arr1.shape[0]):
        if mul_xor_hash(arr1[i]) not in delta:
            n += 1
    # : build the result
    result = np.empty((n, arr1.shape[-1]), dtype=arr1.dtype)
    j = 0
    for i in range(arr1.shape[0]):
        if mul_xor_hash(arr1[i]) not in delta:
            result[j] = arr1[i]
            j += 1
    return result

虽然它们都给出相同的结果：

funcs = setdiff2d_iter, setdiff2d_list, setdiff2d_idx, setdiff2d_set, setdiff2d_bc, setdiff2d_nb

arr1 = np.array([[0, 3], [0, 4], [1, 3], [1, 7]])
print(arr1)
# [[0 3]
#  [0 4]
#  [1 3]
#  [1 7]]

arr2 = np.array([[0, 3], [1, 7], [4, 0]])
print(arr2)
# [[0 3]
#  [1 7]
#  [4 0]]

result = funcs[0](arr1, arr2)
print(result)
# [[0 4]
#  [1 3]]

for func in funcs:
    print(f'{func.__name__:>24s}', np.all(result == func(arr1, arr2)))
#           setdiff2d_iter True
#           setdiff2d_list True
#            setdiff2d_idx True
#            setdiff2d_set False  # because of ordering
#             setdiff2d_bc True
#             setdiff2d_nb True

他们的表现似乎有所不同：

for func in funcs:
    print(f'{func.__name__:>24s}', end='  ')
    %timeit func(arr1, arr2)
#           setdiff2d_iter  16.3 µs ± 719 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
#           setdiff2d_list  14.9 µs ± 528 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
#            setdiff2d_idx  17.8 µs ± 1.75 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)
#            setdiff2d_set  17.5 µs ± 1.31 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)
#             setdiff2d_bc  9.45 µs ± 405 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
#             setdiff2d_nb  1.58 µs ± 51.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

提议的基于 Numba 的方法似乎比其他方法有相当大的优势（使用给定输入大约是其他方法的 10 倍）。

使用较大的输入观察到类似的时间：

np.random.seed(42)

arr1 = np.random.randint(0, 100, (1000, 2))
arr2 = np.random.randint(0, 100, (1000, 2))
print(setdiff2d_nb(arr1, arr2).shape)
# (736, 2)


for func in funcs:
    print(f'{func.__name__:>24s}', end='  ')
    %timeit func(arr1, arr2)
#           setdiff2d_iter  3.51 ms ± 75.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
#           setdiff2d_list  2.92 ms ± 32.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
#            setdiff2d_idx  2.61 ms ± 38.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
#            setdiff2d_set  3.52 ms ± 67.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
#             setdiff2d_bc  25.6 ms ± 198 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
#             setdiff2d_nb  192 µs ± 1.66 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

（附带说明，setdiff2d_bc() 受第二个输入的大小的负面影响最大）。

Python Numpy获取2个二维数组之间的差异

Python Numpy get difference between 2 two-dimensional array

python

numpy

multidimensional-array

set-difference