Fastest Way to Get Min from Every Column in a Matrix

fastest way to get Min from every column in a matrix?

Here is one that is faster on square and wide matrices. It uses pmin on the rows of the matrix. (If you know a faster way of splitting the matrix into its rows, please feel free to edit)

do.call(pmin, lapply(1:nrow(mat), function(i)mat[i,]))

Using the same benchmark as @RicardoSaporta:

$`Square Matrix`
          test elapsed relative
3 pmin.on.rows   1.370    1.000
1          apl   1.455    1.062
2         cmin   2.075    1.515

$`Wide Matrix`
      test elapsed relative
3 pmin.on.rows   0.926    1.000
2         cmin   2.302    2.486
1          apl   5.058    5.462

$`Tall Matrix`
          test elapsed relative
1          apl   1.175    1.000
2         cmin   2.126    1.809
3 pmin.on.rows   5.813    4.947

Fastest way to find the maximum minimum value of two 'connected' matrices

Perhaps you could re-evaluate how you look at the problem in context of what min and max actually do. Say you have the following concrete example:

>>> np.random.seed(1)
>>> print(A := np.random.randint(10, size=(4, 5)))
[[5 8 9 5 0]
 [0 1 7 6 9]
 [2 4 5 2 4]
 [2 4 7 7 9]]
>>> print(B := np.random.randint(10, size=(5, 3)))
[[1 7 0]
 [6 9 9]
 [7 6 9]
 [1 0 1]
 [8 8 3]]

You are looking for a pair of numbers in A and B such that the column in A is the same as the row of B, and the you get the maximum smaller number.

For any set of numbers, the largest pairwise minimum happens when you take the two largest numbers. You are therefore looking for the max in each column of A, row of B, the minimum of those pairs, and then the maximum of that. Here is a relatively simple formulation of the solution:

candidate_i = A.argmax(axis=0)
candidate_k = B.argmax(axis=1)
j = np.minimum(A[candidate_i, np.arange(A.shape[1])], B[np.arange(B.shape[0]), candidate_k]).argmax()

i = candidate_i[j]
k = candidate_k[j]

And indeed, you see that

>>> i, j, k
(0, 2, 2)
>>> A[i, j]
9
>>> B[j, k]
9

If there are collisions, argmax will always pick the first option.

Minimum value in each row and each column of a matrix - Python

Use numpy.

>>> import numpy as np
>>> matrix =[[12,34,28,16],
...         [13,32,36,12],
...         [15,32,32,14],
...         [11,33,36,10]]
>>> np.min(matrix, axis=1) # computes minimum in each row 
array([12, 12, 14, 10])
>>> np.min(matrix, axis=0) # computes minimum in each column
array([11, 32, 28, 10])

Fastest way to find the maximum minimum value of three 'connected' matrices

We can either brute force it using numpy broadcasting or try a bit of smart branch cutting:

import numpy as np

def bf(A,B,C):
    I,J = A.shape
    J,K = B.shape
    return np.unravel_index((np.minimum(np.minimum(A[:,:,None],C[:,None,:]),B[None,:,:])).argmax(),(I,J,K))

def cut(A,B,C):
    gmx = min(A.min(),B.min(),C.min())
    I,J = A.shape
    J,K = B.shape
    Y,X = np.unravel_index(A.argsort(axis=None)[::-1],A.shape)
    for y,x in zip(Y,X):
        if A[y,x] <= gmx:
            return gamx
        curr = np.minimum(B[x,:],C[y,:])
        camx = curr.argmax()
        cmx = curr[camx]
        if cmx >= A[y,x]:
            return y,x,camx
        if gmx < cmx:
            gmx = cmx
            gamx = y,x,camx
    return gamx
            
from timeit import timeit

I = 100
J = 150
K = 200

for rep in range(4):
    print("trial",rep+1)
    A = np.random.rand(I, J)
    B = np.random.rand(J, K)
    C = np.random.rand(I, K)

    print("results identical",cut(A,B,C)==bf(A,B,C))
    print("brute force",timeit(lambda:bf(A,B,C),number=2)*500,"ms")
    print("branch cut",timeit(lambda:cut(A,B,C),number=10)*100,"ms")

It turns out that at the given sizes branch cutting is well worth it:

trial 1
results identical True
brute force 169.74265850149095 ms
branch cut 1.951422297861427 ms
trial 2
results identical True
brute force 180.37619898677804 ms
branch cut 2.1000938024371862 ms
trial 3
results identical True
brute force 181.6371419990901 ms
branch cut 1.999850495485589 ms
trial 4
results identical True
brute force 217.75578951928765 ms
branch cut 1.5871295996475965 ms

How does the branch cutting work?

We pick one array (A, say) and sort it from largest to smallest. We then go through the array one by one comparing each value to the appropriate values from the other arrays and keeping track of the running maximum of minima. As soon as the maximum is no smaller than the remaining values in A we are done. As this will typically happen rather soonish we get a huge saving.

Fastest way to find minimum value in each column

If an array of size X is not sorted or structured in some known special way, then cost for finding element y in it must be equal to X, because you cant skip any element in X (the skipped one can be the solution).

The order of searching does not matter either. If you split it and divide and conquer etc., still the element y can be the last one you visit.

Therefore if you have an array of size n*logn, the lowest possible complexity is Omega(n* log n).

Find the maximum and minimum value of every column and then find the maximum and minimum value of every row

Figured it out.

Minimum and maximum of every column:

apply(a,2,min)
apply(a,2,max)

Minimum and maximum of every row:

apply(a,1,min)
apply(a,1,max)

Found the information here http://www.personality-project.org/r/r.commands.html

Fast way to find index of max/min element in Nth column of matrix

A simple solution would be to loop over the array and store the min/max values in a temporary variable.

function minMax (arr, n) {    let min=Infinity, max=0;    for (const _arr of arr) {        const x = _arr[n];        if (x < min) min = x;        if (x > max) max = x;    }    return [min, max];}
function minMaxIndex (arr, n) {    let min=Infinity, max=0, minIndex, maxIndex;    for (let i=0; i < arr.length; i++) {        const x = arr[i][n];        if (x < min) {          min = x;          minIndex = i;        }        if (x > max) {          max = x;          maxIndex = i;        }    }    return [minIndex, maxIndex];}
console.log (minMax(a, 0))console.log (minMaxIndex(a, 0))

<script>a = [  [22,23],  [74,1],  [21,33],  [32,84],  [11,31],  [1,49],  [7,8],  [11,11],  [99,68],  [52,20]];</script>

Find min value and index of the value in a matrix column after column

np.amin or np.min returns the min values along an axis

np.amin(arr2D, axis=0)

Out:

array([ 1,  5,  4, -3])

np.argmin returns the indices

np.argmin(arr2D, axis=0)

Out:

array([4, 3, 4, 5])

To get the desired output you can use np.vstack and transpose the array

np.vstack([np.amin(arr2D, axis=0), np.argmin(arr2D, axis=0)]).T

Out:

array([[ 1,  4],
       [ 5,  3],
       [ 4,  4],
       [-3,  5]])

Return Index of Minimum Row for Each Column of Matrix

If we need column wise index use apply with MARGIN=2 and apply the which.min

apply(m1, 2, which.min)
#[1] 3 3

If 1 column at a time is needed:

apply(as.matrix(m1[,1, drop = FALSE]), 2, which.min)

If we check ?Extract, the default usage is

x[i, j, ... , drop = TRUE]

drop - For matrices and arrays. If TRUE the result is coerced to the lowest possible dimension (see the examples). This only works for extracting elements, not for the replacement. See drop for further details.

To avoid getting dimensions dropped, use drop = FALSE

If we need the min values of each row

do.call(pmin, as.data.frame(m1))

Or

apply(m1, 2, min)

Or

library(matrixStats)
rowMins(m1)

data

m1 <- matrix(6:1,nrow=3,ncol=2)

---

Related Topics