Finding duplicate matrices in Python?

Question

I have a matrix a.shape: (80000, 38, 38). I want to check and see if there are any duplicates or similar (38,38) matrices along the first dimension (in this case, there are 80000 of these matrices).

I could run through two for loops:

for i in range(a.shape[0]):
    for g in range(a.shape[0]):
        if a[i,:,:] - a[g,:,:] < tolerance:
            # save the index here

But that seems incredibly inefficient. I know there is numpy.unique, but I'm not sure I understand how it works when you have a set of 2-dimensional matrices.

Suggestions for an efficient way to do this? Is there a way to get broadcasting to find the differences of all of the elements in all the matrices?

Answer 1

Detect exact duplicate blocks

Here's an approach using lex-sorting -

# Reshape a to a 2D as required in few places later on
ar = a.reshape(a.shape[0],-1)

# Get lex-sorted indices
sortidx = np.lexsort(ar.T)

# Lex-sort reshaped array to bring duplicate rows next to each other.
# Perform differentiation to check for rows that have at least one non-zero
# as those represent unique rows and as such those are unique blocks 
# in axes(1,2) for the original 3D array 
out = a[sortidx][np.append(True,(np.diff(ar[sortidx],axis=0)!=0).any(1))]

---

Here's another approach considering each block of elements in axes=(1,2) as an indexing tuple to find out the uniqueness among other blocks -

# Reshape a to a 2D as required in few places later on
ar = a.reshape(a.shape[0],-1)

# Get dimension shape considering each block in axes(1,2) as an indexing tuple
dims = np.append(1,(ar[:,:-1].max(0)+1).cumprod())

# Finally get unique indexing tuples' indices that represent unique
# indices along first axis for indexing into input array and thus get 
# the desired output of unique blocks along the axes(1,2)
out = a[np.unique(ar.dot(dims),return_index=True)[1]]

---

Sample run -

1] Input :

In [151]: a
Out[151]: 
array([[[12,  4],
        [ 0,  1]],

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

       [[12,  4],
        [ 0,  1]],

       [[ 3,  4],
        [ 1,  3]],

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

       [[ 3,  0],
        [ 2,  1]]])

2] Output:

In [152]: ar = a.reshape(a.shape[0],-1)
     ...: sortidx = np.lexsort(ar.T)
     ...: 

In [153]: a[sortidx][np.append(True,(np.diff(ar[sortidx],axis=0)!=0).any(1))]
Out[153]: 
array([[[12,  4],
        [ 0,  1]],

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

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

       [[ 3,  4],
        [ 1,  3]]])

In [154]: dims = np.append(1,(ar[:,:-1].max(0)+1).cumprod())

In [155]: a[np.unique(ar.dot(dims),return_index=True)[1]]
Out[155]: 
array([[[12,  4],
        [ 0,  1]],

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

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

       [[ 3,  4],
        [ 1,  3]]])

Detect similar blocks

For similarity criteria, assuming you meant absolute values of (a[i,:,:] - a[g,:,:]).all() < tolerance, here's a vectorized approach to get indices of all similar blocks along axes(1,2) in input array -

R,C = np.triu_indices(a.shape[0],1)
mask = (np.abs(a[R] - a[C]) < tolerance).all(axis=(1,2))
I,G = R[mask], C[mask]

Sample run -

In [267]: a
Out[267]: 
array([[[12,  4],
        [ 0,  1]],

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

       [[13,  4],
        [ 0,  1]],

       [[ 3,  4],
        [ 1,  3]],

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

       [[12,  5],
        [ 1,  1]]])

In [268]: tolerance = 2

In [269]: R,C = np.triu_indices(a.shape[0],1)
     ...: mask = (np.abs(a[R] - a[C]) < tolerance).all(axis=(1,2))
     ...: I,G = R[mask], C[mask]
     ...: 

In [270]: I
Out[270]: array([0, 0, 1, 2])

In [271]: G
Out[271]: array([2, 5, 4, 5])