logo标签列表

高效使用纯NumPy在一个数组中删除每一行，如果它出现在另一个数组中

pythonarraysnumpy
3

我有一个Numpy数组，其中索引以(n, 2)的形式存储。例如:

[[0, 1],
 [2, 3], 
 [1, 2], 
 [4, 2]]

然后我做一些处理，创建一个形状为(m, 2)的数组，其中n > m。例如：

[[2, 3]
 [4, 2]]

现在我想删除第一个数组中可以在第二个数组中找到的每一行。 所以我的目标结果是：

[[0, 1], 
 [1, 2]]

我的当前解决方案如下：

for row in second_array:
        result = np.delete(first_array, np.where(np.all(first_array == second_array, axis=1)), axis=0)

然而，如果第二个参数很大的话，这将非常耗时。有人知道一个只使用numpy的解决方案，不需要循环吗？
你的数组里面是否总是包含非负整数？ - jdehesa
不，它们都是正数，因为它们是索引。我从np.argwhere()创建它们。 - Lau
1
获取两个二维NumPy数组之间相交的行（不是相同的集合操作，但应该给你足够的指针）。 - NPE
3个回答
2
这里有一个利用正数特性的方法，使用矩阵乘法进行降维 - 最初的回答 
def setdiff_nd_positivenums(a,b):
    s = np.maximum(a.max(0)+1,b.max(0)+1)
    return a[~np.isin(a.dot(s),b.dot(s))]

Sample run -

In [82]: a
Out[82]: 
array([[0, 1],
       [2, 3],
       [1, 2],
       [4, 2]])

In [83]: b
Out[83]: 
array([[2, 3],
       [4, 2]])

In [85]: setdiff_nd_positivenums(a,b)
Out[85]: 
array([[0, 1],
       [1, 2]])

此外，似乎第二个数组b是a的一个子集。因此，我们可以利用这种情况来进一步提高性能，使用np.searchsorted，像这样 - "最初的回答"
def setdiff_nd_positivenums_searchsorted(a,b):
    s = np.maximum(a.max(0)+1,b.max(0)+1)
    a1D,b1D = a.dot(s),b.dot(s)
    b1Ds = np.sort(b1D)
    return a[b1Ds[np.searchsorted(b1Ds,a1D)] != a1D]

最初的回答
时间 -
In [146]: np.random.seed(0)
     ...: a = np.random.randint(0,9,(1000000,2))
     ...: b = a[np.random.choice(len(a), 10000, replace=0)]

In [147]: %timeit setdiff_nd_positivenums(a,b)
     ...: %timeit setdiff_nd_positivenums_searchsorted(a,b)
10 loops, best of 3: 101 ms per loop
10 loops, best of 3: 70.9 ms per loop

对于通用数字，这里提供另一种使用views的方法——最初的回答。
# https://dev59.com/tqPia4cB1Zd3GeqP3cEw#45313353/ @Divakar
def view1D(a, b): # a, b are arrays
    a = np.ascontiguousarray(a)
    b = np.ascontiguousarray(b)
    void_dt = np.dtype((np.void, a.dtype.itemsize * a.shape[1]))
    return a.view(void_dt).ravel(),  b.view(void_dt).ravel()

def setdiff_nd(a,b):
    # a,b are the nD input arrays
    A,B = view1D(a,b)    
    return a[~np.isin(A,B)]

最初的回答

示例运行 -

In [94]: a
Out[94]: 
array([[ 0,  1],
       [-2, -3],
       [ 1,  2],
       [-4, -2]])

In [95]: b
Out[95]: 
array([[-2, -3],
       [ 4,  2]])

In [96]: setdiff_nd(a,b)
Out[96]: 
array([[ 0,  1],
       [ 1,  2],
       [-4, -2]])

时间 -

In [158]: np.random.seed(0)
     ...: a = np.random.randint(0,9,(1000000,2))
     ...: b = a[np.random.choice(len(a), 10000, replace=0)]

In [159]: %timeit setdiff_nd(a,b)
1 loop, best of 3: 352 ms per loop
2

numpy-indexed包（免责声明：我是它的作者）旨在高效地在nd-array上执行此类操作。

最初的回答：numpy-indexed包是一个用于在nd-array上高效执行此类操作的软件包，作者为我。
import numpy_indexed as npi
# if the output should consist of unique values and there is no need to preserve ordering
result = npi.difference(first_array, second_array)
# otherwise:
result = first_array[~npi.in_(first_array, second_array)]
听起来很有趣！ - Lau
如果两个数组没有共同的行，npi.difference会出错。第二个选项在这种情况下似乎起作用。 - Alehud
1

这是一个可以处理任何形状的2D整数数组的函数，接受正数和负数：

import numpy as np

# Gets a boolean array of rows of a that are in b
def isin_rows(a, b):
    a = np.asarray(a)
    b = np.asarray(b)
    # Subtract minimum value per column
    min = np.minimum(a.min(0), b.min(0))
    a = a - min
    b = b - min
    # Get maximum value per column
    max = np.maximum(a.max(0), b.max(0))
    # Compute multiplicative base for each column
    base = np.roll(max, 1)
    base[0] = 1
    base = np.cumprod(max)
    # Make flattened version of arrays
    a_flat = (a * base).sum(1)
    b_flat = (b * base).sum(1)
    # Check elements of a in b
    return np.isin(a_flat, b_flat)

# Test
a = np.array([[0, 1],
              [2, 3],
              [1, 2],
              [4, 2]])
b = np.array([[2, 3],
              [4, 2]])
a_in_b_mask = isin_rows(a, b)
a_not_in_b = a[~a_in_b_mask]
print(a_not_in_b)
# [[0 1]
#  [1 2]]

编辑：从考虑b中可能的行数可以得出一种可能的优化。如果b的行数多于可能的组合数量，则可以先找到其唯一元素，这样np.isin会更快：

import numpy as np

def isin_rows_opt(a, b):
    a = np.asarray(a)
    b = np.asarray(b)
    min = np.minimum(a.min(0), b.min(0))
    a = a - min
    b = b - min
    max = np.maximum(a.max(0), b.max(0))
    base = np.roll(max, 1)
    base[0] = 1
    base = np.cumprod(max)
    a_flat = (a * base).sum(1)
    b_flat = (b * base).sum(1)
    # Count number of possible different rows for b
    num_possible_b = np.prod(b.max(0) - b.min(0) + 1)
    if len(b_flat) > num_possible_b:  # May tune this condition
        b_flat = np.unique(b_flat)
    return np.isin(a_flat, b_flat)

条件len(b_flat) > num_possible_b可能需要进行更好的调整，以便仅在真正值得时才查找唯一元素（也许是len(b_flat) > 2 * num_possible_b或len(b_flat) > num_possible_b + CONSTANT）。对于具有较少值的大数组，它似乎会产生一些改进：
import numpy as np

# Test setup from @Divakar
np.random.seed(0)
a = np.random.randint(0, 9, (1000000, 2))
b = a[np.random.choice(len(a), 10000, replace=0)]
print(np.all(isin_rows(a, b) == isin_rows_opt(a, b)))
# True
%timeit isin_rows(a, b)
# 100 ms ± 425 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit isin_rows_opt(a, b)
# 81.2 ms ± 324 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接