I have a boolean matrix with 1.5E6
rows and 20E3
columns, similar to this example:
M = [[ True, True, False, True, ...],
[False, True, True, True, ...],
[False, False, False, False, ...],
[False, True, False, False, ...],
...
[ True, True, False, False, ...]
]
Also, I have another matrix N
( 1.5E6
rows, 1
column):
N = [[ True],
[False],
[ True],
[ True],
...
[ True]
]
What I need to do, is to go through each column pair from matrix M
(1&1, 1&2, 1&3, 1&N, 2&1, 2&2 etc) combined by the AND
operator, and count how many overlaps there are between the result and matrix N
.
My Python/Numpy code would look like this:
for i in range(M.shape[1]):
for j in range(M.shape[1]):
result = M[:,i] & M[:,j] # Combine the columns with AND operator
count = np.sum(result & N.ravel()) # Counts the True occurrences
... # Save the count for the i and j pair
The problem is, going through 20E3 x 20E3
combinations with two for loops is computationally expensive (takes around 5-10 days to compute). A better option I tried is comparing each column to the whole matrix M:
for i in range(M.shape[1]):
result = M[:,i]*M.shape[1] & M # np.tile or np.repeat is used to horizontally repeat the column
counts = np.sum(result & N*M.shape[1], axis=0)
... # Save the counts
This reduces overhead and calculation time to around 10%, but it's still taking 1 day or so to compute.
My question would be :
what is the fastest way (non Python maybe?) to make these calculations (basically just AND
and SUM
)?
I was thinking about low level languages, GPU processing, quantum computing etc.. but I don't know much about any of these so any advice regarding the direction is appreciated!
Additional thoughts: Currently thinking if there is a fast way using the dot product (as Davikar proposed) for computing triplets of combinations:
def compute(M, N):
out = np.zeros((M.shape[1], M.shape[1], M.shape[1]), np.int32)
for i in range(M.shape[1]):
for j in range(M.shape[1]):
for k in range(M.shape[1]):
result = M[:, i] & M[:, j] & M[:, k]
out[i, j, k] = np.sum(result & N.ravel())
return out
tensorflow
tag in the question? When you say "1.5mm", is that 1.5 million rows? Just to clarify. Also, what do you do withcount
? Are you accumulating the total sum, or eachcount
is stored individually, or something else?count
values should be summed into a global total, or thecount
for each pair of columns should be stored separately? (in your loops, you are just replacing the value ofcount
in each iteration, so I'm not sure if you do something else with it later or just accumulate it).