计算一个数组在另一个数组中不重叠的出现次数

Question

我有一个mxn矩阵A，其中m%t = n%t = 0，因此一个较小的txt矩阵B平铺矩阵，没有边界或重叠。我想检查A是否完全由B的tile组成，而不将tiling作为一个尽可能有效的中间步骤来计算。此外，对于我的特殊用例，不需要知道B。测试A是否在每个方向上的每个txt瓷砖上严格地重复它自己就足够了。你知道吗

数值示例：

A = [[1, 0, 1, 0],
     [0, 1, 0, 1],
     [1, 0, 1, 0],
     [0, 1, 0, 1]]
B.shape = [2,2]
--> True
B.shape = [1,1]
--> False

到目前为止，我计算了一个比较矩阵C，它只是一个B的平铺，以适应A的大小：

import numpy as np
x,y      = B.shape
x_a, y_a = A.shape
x_t = x_a/x
y_t = y_a/y
B_dash = A[:x, :y]
C = np.tile(B_dash,(x_t, y_t))
np.count_nonzero(A-C)

有没有更快的方法，不用计算C？你知道吗

Answer 1

应用方法1:似乎我们把B在A中出现的次数计算为不同的块。所以，我们可以用^{}-

from skimage.util import view_as_blocks as viewW

out = np.count_nonzero((viewW(A, B.shape) == B).all((2,3)))

方法2:和NumPy在一起，我们会-

m1,n1 = A.shape
m2,n2 = B.shape
out = np.count_nonzero((A.reshape(m1//m2,m2,n1//n2,n2) == B[:,None]).all((1,3)))

示例运行-

In [274]: A
Out[274]: 
array([[2, 0, 2, 0],
       [5, 3, 5, 1],
       [3, 3, 2, 6],
       [1, 0, 3, 1]])

In [275]: B
Out[275]: 
array([[3, 3],
       [1, 0]])

In [276]: np.count_nonzero((viewW(A, B.shape) == B).all((2,3)))
Out[276]: 1



In [278]: A
Out[278]: 
array([[2, 0, 3, 3],
       [5, 3, 1, 0],
       [3, 3, 2, 6],
       [1, 0, 3, 1]])

In [279]: B
Out[279]: 
array([[3, 3],
       [1, 0]])

In [280]: np.count_nonzero((viewW(A, B.shape) == B).all((2,3)))
Out[280]: 2

Answer 2

不生成C就可以得到结果。您可以通过以下方法来实现：

x,y      = B.shape
x_a, y_a = A.shape
np.array_equal(A[:, :y_a-y], A[:, y:]) and np.array_equal(A[:x_a-x, :], A[x:, :])

也就是说，比较A的第一个y_a-y列和最后一个y_a-y列，然后对行执行类似的操作。我没有测试上面的代码，但是应该更快，因为使用这个方法numpy不会分配新的内存。你知道吗

最后一条语句可以优化为：

np.array_equal(A[:, :y_a-y], A[:, y:]) and np.array_equal(A[:x_a-x, :y_a], A[x:, :y_a])

因为如果第一项是True，我们已经知道A的列是t次重复的。你知道吗