What is the most efficient way to find the largest element in a matrix along with position? Also, the largest element in each column with position

Question

I have written the following code but it looks to be far from efficient.

//Find largest in tempRankingData
int largestIntempRankingData = tempRankingData[0, 0];
for (int i = 0; i < count; i++)
{
    for (int j = 0; j < count; j++)
    {
        if (tempRankingData[i, j] > largestIntempRankingData)
        {
            largestIntempRankingData = tempRankingData[i, j];
        }
    }
}

//Find position of largest in tempRankingData
List<string> positionLargestIntempRankingData = new List<string>();
for (int i = 0; i < count; i++)
{
    for (int j = 0; j < count; j++)
    {
        if (tempRankingData[i, j] == largestIntempRankingData)
        {
            positionLargestIntempRankingData.Add(i + "," + j);
        }
    }
}

//Find largest in each column
int largestInColumn = 0;
List<string> positionOfLargestInColumn = new List<string>();
Dictionary<int, List<string>> position = new Dictionary<int, List<string>>();
for (int i = 0; i < count; i++)
{
    largestInColumn = tempRankingData[0, i];
    positionOfLargestInColumn = new List<string>();
    for (int j = 0; j < count; j++)
    {
        if (tempRankingData[j, i] > largestInColumn)
        {
            largestInColumn = tempRankingData[j, i];
        }
    }

    for (int j = 0; j < count; j++)
    {
        if (tempRankingData[j, i] == largestInColumn)
        {
            positionOfLargestInColumn.Add(j + "," + i);
        }
    }
    position.Add(i, positionOfLargestInColumn);
}

So, I wanted to check about the most efficient way to do this.

Are all the values in tempRankingData unique? Is it possible that the largest value might appear more than once? — Martin Brown, Jun 02 '15 at 13:11
Looks pretty efficient to me. It's `O(ij)`, which is a typical matrix scan. — Evan Mulawski, Jun 02 '15 at 13:13
Are you trying to find all these at the same time? Or are these supposed to be separate functions? You can trivially combine the searching for the largest and getting the position of the largest by keeping track of the indexes every time you update the largest value you've found so far. Obviously the best you can do will be `O(nm)` because you *have* to examine *every single cell* to be confident that you've found the largest. You can get the largest in the column too, but it'll be slightly more fiddly to do. — Matt Burland, Jun 02 '15 at 13:13
`looks to be far from efficient` isn't really all that helpful. Is it a performance problem or not? Beware of premature optimization. That said, no need to build a list of the biggest elements - you only care about the last one. So just remember the last value and its position, and if it's smaller than current value and position, update. — Luaan, Jun 02 '15 at 13:17
If performance is an issue, drop the use of multidmensional arrays in favor of jagged arrays or use a single array and emulate the two-dimension with index manipulation. See http://stackoverflow.com/questions/597720/what-are-the-differences-between-a-multidimensional-array-and-an-array-of-arrays — Kryptos, Jun 02 '15 at 13:19
A minor improvement would be to strip out all the string concatenation you are doing in the loop too. Just keep track of the row and column numbers as numbers. You can convert them to a string at the end if you need to. — Matt Burland, Jun 02 '15 at 13:46

Damien_The_Unbeliever · Accepted Answer · 2015-06-02T13:41:09.963

Whilst you're finding the largest in each column, you could also be finding the largest overall. You can also capture the positions as you go:

//Find largest in each column
int largestInColumn = 0;
int largestOverall = int.MinValue;
List<string> positionOfLargestInColumn;
Dictionary<int, List<string>> position = new Dictionary<int, List<string>>();
List<string> positionLargestIntempRankingData = new List<string>();
for (int i = 0; i < count; i++)
{
    largestInColumn = tempRankingData[0, i];
    positionOfLargestInColumn = new List<string>();
    positionOfLargestInColumn.Add("0," + i);
    for (int j = 1; j < count; j++)
    {
        if (tempRankingData[j, i] > largestInColumn)
        {
            largestInColumn = tempRankingData[j, i];
            positionOfLargestInColumn.Clear();
            positionOfLargestInColumn.Add(j + "," + i);
        }
        else if(tempTankingData[j,i] == largestInColumn)
        {
            positionOfLargestInColumn.Add(j + "," + i);
        }
    }
    position.Add(i, positionOfLargestInColumn);
    if(largestInColumn > largestOverall)
    {
      positionLargestIntempRankingData.Clear();
      positionLargestIntempRankingData.AddRange(positionOfLargestInColumn);
      largestOverall = largestInColumn;
    }
    else if(largestInColumn == largestOverall)
    {
      positionLargestIntempRankingData.AddRange(positionOfLargestInColumn);
    }
}

Yes, I could have combined the two operations into one. Thanks for your help. — RKS, Jun 02 '15 at 13:46
If you are using a `Dictonary` where the keys are consecutive numbers starting at `0`, you are better off with a `T[]` since the index of the array will be exactly the same as the keys in your dictionary. — Matt Burland, Jun 02 '15 at 13:48

score 0 · Answer 2 · answered Jun 02 '15 at 13:13

1). You can find largest element and its position in one method and retrieve. Would be caller of your method concerned about position or actual value, is a matter of concrete case.

2) You can use `yield return' technique in your matrix search (for column based search), so do not compute all column's maximas and push them into the dictionary. Dictionaries are not that fast as arrays, if you can avoid use them, do that.

3) You can keep a matrix in single dimension, long array. Have [] access operator overload, to "emulate" matrix access. Why ? If finding maximum is something frequent you might need to do during program run, having one foreach loop is faster then having 2 nested once. In case of a big matrices, single array search can be easily parallelized among different cores.

If big matrices and/or frequent calls are not your concern, just simplify your code like in points (1), (2).

Matt Burland · Answer 3 · 2015-06-02T13:43:13.923

You can get all these pieces of information in a single scan with a little fiddling around. Something like this (converting the rows and columns to a string is trivial and better done at the end anyway):

int? largestSoFar = null;    // you could populate this with myMatrix[0,0]
                             // but it would fail if the matrix is empty
int largestCol = 0;
int largestRow = 0;
int?[] largestPerColumn = new int?[numOfCols];    // You could also populate this with
                                                  // the values from the first row but
                                                  // it would fail if there are no rows
int[] largestColumnRow = new int[numOfCols];

for (int i = 0; i < numOfRows; i++)
{
    for (int j = 0; j < numOfCols; i++)
    {
        if (largestSoFar < myMatrix[i,j]) 
        {
            largestSoFar = myMatrix[i,j];
            largestCol = j;
            largestRow = i;
        }
        if (largestPerColumn[j] < myMatrix[i,j])
        {
            largestPerColumn[j] = myMatix[i,j];
            largestColumnRow[j] = i;
        }
    }
}

// largestSoFar is the biggest value in the whole matrix
// largestCol and largestRow is the column and row of the largest value in the matrix
// largestPerColumn[j] is the largest value in the jth column
// largestColumnRow[j] is the row of the largest value of the jth column

If you do need to capture all the "maxima" (for want of a better word, because that's not really what you are doing) in a column, you could just change the above code to something like this:

int? largestSoFar = null;    // you could populate this with myMatrix[0,0]
                             // but it would fail if the matrix is empty
int largestCol = 0;
int largestRow = 0;
int?[] largestPerColumn = new int?[numOfCols];    // You could also populate this with
                                                  // the values from the first row but
                                                  // it would fail if there are no rows
List<int>[] largestColumnRow = new List<int>[numOfCols];

for (int i = 0; i < numOfRows; i++)
{
    for (int j = 0; j < numOfCols; i++)
    {
        if (largestSoFar < myMatrix[i,j]) 
        {
            largestSoFar = myMatrix[i,j];
            largestCol = j;
            largestRow = i;
        }
        if (largestPerColumn[j] < myMatrix[i,j])
        {
            largestPerColumn[j] = myMatix[i,j];
            largestColumnRow[j].Add(i);
        }
    }
}

// Now largestColumnRow[j] gives you a list of all the places where you found a larger 
// value for the jth column

The current results in the OP's question capture the positions of the largest in lists - which suggested to me that they wanted *all* positions that are tying for "largest in column" and "largest in matrix" rather than just one position. Of course, that may just be an artefact of how they were thinking about the problem. — Damien_The_Unbeliever, Jun 02 '15 at 13:32
@Damien_The_Unbeliever: If that is the case (and it's a rather odd requirement), it's a fairly trivial fix. Just make `largestColumnRow` a `List[]` and push the values into the corresponding list. — Matt Burland, Jun 02 '15 at 13:39

score 0 · Answer 4 · answered Jun 02 '15 at 13:33

For your fist two itterations you could replace with this:

 //Find largest in tempRankingData
int largestIntempRankingData = tempRankingData[0, 0];
List<KeyValuePair<double,string>> list = new List<KeyValuePair<double,string>>();
for (int i = 0; i < count; i++)
{
    for (int j = 0; j < count; j++)
    {
        if (tempRankingData[i, j] > largestIntempRankingData)
        {
            largestIntempRankingData = tempRankingData[i, j];
            list.Add(new KeyValuePair<double, string>(largestIntempRankingData, i + "," + j));   //Add the value and the position;
        }
    }
}

//This gives a list of strings in which hold the position of largestInItemRankingData example "3,3"
            //Only positions where the key is equal to the largestIntempRankingData;
list.Where(w => w.Key == largestIntempRankingData).ToList().Select(s => s.Value).ToList();

What is the most efficient way to find the largest element in a matrix along with position? Also, the largest element in each column with position

4 Answers4