• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 531
  • Last Modified:

Find the top N values of a 2D array

Dear experts:
Basically I would like to implement the following method:
public List<SearchResults> FindTopValues(int[,] data, int howManyTops)
{
    List<SearchResults> results = new List<SearchResults>();
    //Your code goes here.
    return results;
}

Open in new window

where
public class SearchResults
    {
        public int Row { get; set; }
        public int Col { get; set; }
        public int Value { get; set; }
    }

Open in new window

For example given the data array
[ 0 3 2 1
  4 2 1 5
  1 6 2 1 ]

If I want to find the top 3 values, the method call will be:
FindTopValues(data, 3)
and the results will be: (row,col, value)
2,1,6
1,3,5
1,0,4

Further array details:
- Number of rows >= 5* Number of rows
- Values in array between 0 and 10000.

Thanks,
MAS
Code is in C# , but VB.NET/C++ answers are OK.
0
Miguel Oz
Asked:
Miguel Oz
  • 3
  • 2
2 Solutions
 
käµfm³d 👽Commented:
Using a LINQ approach you could do:

public List<SearchResults> FindTopValues(int[,] data, int howManyTops)
{
    List<SearchResults> results = new List<SearchResults>();
    int r = 0;
    int c = 0;
    int rowSize = data.GetUpperBound(1) + 1;    // 1 is 2nd dimension (i.e. column count); + 1 since GetUpperBound returns highest index, not # of items

    var rowColQuery = from int item in data
                      let row = (r / rowSize)
                      let column = (r++ % rowSize)    // Increment "r" here since it's the last place r is used, per iteration
                      select new SearchResults()
                      {
                          Row = row,
                          Col = column,
                          Value = item,
                      };

    var maxQuery = rowColQuery.OrderByDescending(sr => sr.Value)
                              .Take(howManyTops);

    results = maxQuery.ToList();

    return results;
}

Open in new window

0
 
Fernando SotoRetiredCommented:
Hi mas_oz2003;

Here is another solution.

public List<SearchResults> FindTopValues(int[,] data, int howManyTops)
{
    List<SearchResults> results = new List<SearchResults>();
    
    for(int i = 0; i < data.GetUpperBound(1); i++ ){
        for(int j = 0; j <= data.GetUpperBound(1); j++ ){
            results.Add(new SearchResults() { Col = j, Row = i, Value = data[i,j]});
        }
    }    
    
    return results.OrderByDescending(r => r.Value).Take(howManyTops).ToList();
}

Open in new window

0
 
käµfm³d 👽Commented:
@FenandoSoto

Shouldn't your first GetUpperBound call be looking at the first dimension (i.e. zero)?
0
Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
käµfm³d 👽Commented:
Here's a variation of FernandoSoto's approach that appears to run faster than either approach mentioned thus far:

public List<SearchResults> FindTopValues(int[,] data, int howManyTops)
{
    List<SearchResults> results = new List<SearchResults>(howManyTops);

    for (int i = 0; i < data.GetUpperBound(0); i++)
    {
        for (int j = 0; j <= data.GetUpperBound(1); j++)
        {
            if (results.Count == howManyTops)
            {
                for (int k = 0; k < results.Count; k++)
                {
                    if (results[k].Value < data[i, j])
                    {
                        results.RemoveAt(results.Count - 1);
                        results.Insert(k, new SearchResults() { Row = i, Col = j, Value = data[i, j] });
                        break;
                    }
                }
            }
            else
            {
                results.Add(new SearchResults() { Row = i, Col = j, Value = data[i, j] });
                results.Sort();
            }
        }
    }

    return results;
}

Open in new window


For it to work properly, you would need to implement IComparable on your SearchResults class:

public class SearchResults : IComparable<SearchResults>
{
    public int Row { get; set; }
    public int Col { get; set; }
    public int Value { get; set; }

    public int CompareTo(SearchResults other)
    {
        return other.Value.CompareTo(this.Value);   // Sort reverse order
    }
}

Open in new window


You could instead create a new IComparer instance, but the above is a bit quicker to implement.
0
 
Fernando SotoRetiredCommented:
Thanks @kaufmed;

@mas_oz2003;

Updated version from my last post. This should work better.

public List<SearchResults> FindTopValues(int[,] data, int howManyTops)
{
    List<SearchResults> results = new List<SearchResults>();

    for (int i = 0; i < data.GetLength(0); i++)
    {
        for (int j = 0; j < data.GetLength(1); j++)
        {
            results.Add(new SearchResults() { Col = j, Row = i, Value = data[i, j] });
        }
    }

    return results.OrderByDescending(r => r.Value).Take(howManyTops).ToList();
}

Open in new window

0
 
Miguel OzSoftware EngineerAuthor Commented:
Both solutions work OK, but Kaufmed code has a better performance for big arrays
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Introducing Cloud Class® training courses

Tech changes fast. You can learn faster. That’s why we’re bringing professional training courses to Experts Exchange. With a subscription, you can access all the Cloud Class® courses to expand your education, prep for certifications, and get top-notch instructions.

  • 3
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now