Solved

Find the top N values of a 2D array

Posted on 2013-06-07
7
508 Views
Last Modified: 2013-06-08
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
Comment
Question by:Miguel Oz
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
7 Comments
 
LVL 75

Expert Comment

by:käµfm³d 👽
ID: 39230983
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
 
LVL 63

Expert Comment

by:Fernando Soto
ID: 39231920
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
 
LVL 75

Expert Comment

by:käµfm³d 👽
ID: 39232010
@FenandoSoto

Shouldn't your first GetUpperBound call be looking at the first dimension (i.e. zero)?
0
Guide to Performance: Optimization & Monitoring

Nowadays, monitoring is a mixture of tools, systems, and codes—making it a very complex process. And with this complexity, comes variables for failure. Get DZone’s new Guide to Performance to learn how to proactively find these variables and solve them before a disruption occurs.

 
LVL 75

Accepted Solution

by:
käµfm³d   👽 earned 300 total points
ID: 39232080
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
 
LVL 63

Assisted Solution

by:Fernando Soto
Fernando Soto earned 200 total points
ID: 39232124
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
 
LVL 36

Author Closing Comment

by:Miguel Oz
ID: 39232373
Both solutions work OK, but Kaufmed code has a better performance for big arrays
0

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Creating an analog clock UserControl seems fairly straight forward.  It is, after all, essentially just a circle with several lines in it!  Two common approaches for rendering an analog clock typically involve either manually calculating points with…
Parsing a CSV file is a task that we are confronted with regularly, and although there are a vast number of means to do this, as a newbie, the field can be confusing and the tools can seem complex. A simple solution to parsing a customized CSV fi…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

749 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question