số Đếm lần xuất hiện của một mảng mà không chồng chéo lên nhau trong một mảng

Question

Tôi có một ma trận mxnA, nơi m%t = n%t = 0, do đó một nhỏ txt ma trận B gạch ma trận không biên giới hoặc chồng chéo. Tôi muốn kiểm tra xem nếu A bao gồm hoàn toàn các ô từ B mà không tính toán ốp lát như là một bước trung gian càng hiệu quả càng tốt. Hơn nữa đối với trường hợp sử dụng đặc biệt của tôi, không cần phải biết B. Nó là đủ để kiểm tra nếu A lặp lại chính nó mỗi gạch txt theo mọi hướng.

ví dụ Numeric:

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 

Cho đến nay, tôi tính toán một ma trận so sánh C, mà chỉ đơn giản là một ốp lát của B để phù hợp với kích thước của 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ó cách nào nhanh hơn , mà không tính toán C?

Answer 1

Appproach # 1: Dường như chúng tôi đang đếm số lần xuất hiện của B trong A dưới dạng các khối riêng biệt. Vì vậy, chúng ta có thể sử dụng skimage.util.view_as_blocks -

from skimage.util import view_as_blocks as viewW 

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

Appproach # 2: Ở lại với NumPy, chúng ta sẽ phải -

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

mẫu chạy -

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ó thể để có được kết quả mà không tạo ra C. Bạn có thể làm điều đó bằng cách:

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:, :]) 

Tức là, để so sánh các cột y_a-y đầu tiên của A và cột y_a-y cuối cùng của A, sau đó thực hiện những việc tương tự cho các hàng. Tôi đã không kiểm tra mã trên, nhưng nó phải được nhanh hơn, bởi vì với phương pháp này numpy sẽ không phân bổ những kỷ niệm mới.

Tuyên bố cuối cùng có thể được tối ưu hóa để:

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

Bởi vì nếu nhiệm kỳ đầu tiên là True, chúng tôi đã biết rằng cột A của được lặp lại lần t.