Fastest way of finding argmax in 2d array

Question

JavaScript is far from a familiar language to me. I have a piece of logic I am trying to optimise for speed. It consists in finding the argmax, row and columns index, of the a 2d array (rectangular shaped). At the moment, I have a naïve implementation

function argMax2d(arr) {
  var rowMax = 0, colMax = 0;
  for( var rowIndex = 0; rowIndex < arr.length; rowIndex++){
    for( var colIndex = 0; colIndex < arr[rowIndex].length; colIndex++){
      if (arr[rowIndex][colIndex] > arr[rowMax][colMax]){
        rowMax = rowIndex;
        colMax = colIndex;
      }
    }
  }
  return [rowMax, colMax];
}

In Python this would be a really slow way of getting the job done because of making no use of the contiguity of the data.

PS: arr is always rectangular, the number of columns is the same in every row

Unless the array has any pattern (ordered for instance) i don't think there is other algorithm you can do. You may try to use workers to do multithread (one worker for row) — Maxwell s.c, Nov 03 '20 at 14:04
you want to find the index of the max value in the array or the actual max value ? In the 1st case what if the max value is in 2 places, which do you want to return ? — Gabriele Petrioli, Nov 03 '20 at 14:05
The only improvement I would try would be copying the maximum into a variable, so that on future comparisons it is a variable access instead of two array accesses. — Jonas Wilms, Nov 03 '20 at 14:05
@GabrielePetrioli I want the index, the argmax not the max. If there is degeneracy, any of the possibles is good. — Learning is a mess, Nov 03 '20 at 14:28
@JonasWilms Between argMax2d calls the array will change and most probably the max value will. I don't think it's relevant to cache it here. — Learning is a mess, Nov 03 '20 at 14:28
If there is no cell value patter within the matrix you have to check all cells. You say this would be slow in Python, could you provide an example in Python that would be faster? — 3limin4t0r, Nov 03 '20 at 14:33
@3limin4t0r I don't have an example immediately available, but in Python I would use numpy which will make use of cache, contiguity and compiled code. — Learning is a mess, Nov 03 '20 at 14:42
What size arrays are we talking about here? 10s, 100s, 1000s — epascarello, Nov 03 '20 at 15:54

Gabriele Petrioli · Accepted Answer · 2020-11-03T14:48:09.170

Based on the comments in the question, the only minimal optimizations i can think are to cache the length of the arrays to avoid accessing them in each iteration, and the same for the maxValue used for the comparisons.

    function argMax2d(arr) {
      var rowMax = 0,
          colMax = 0,
          vLength = arr.length,
          hLength = arr[0].length,
          maxValue = -Infinity;
          
      for (var rowIndex = 0; rowIndex < vLength; rowIndex++) {
        for (var colIndex = 0; colIndex < hLength; colIndex++) {
          if (arr[rowIndex][colIndex] > maxValue) {
            maxValue = arr[rowIndex][colIndex];
            rowMax = rowIndex;
            colMax = colIndex;
          }
        }
      }
      
      return [rowMax, colMax];
    }

JS performance comparison

Thanks for the input. I really like the immediate benchmark, it's nice to quantify how much things are getting sped up. — Learning is a mess, Nov 03 '20 at 20:17

Fastest way of finding argmax in 2d array

1 Answers1