Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Find the top N values of a 2D array

Posted on 2013-06-07
7
Medium Priority
?
515 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 64

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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 75

Accepted Solution

by:
käµfm³d   👽 earned 1200 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 64

Assisted Solution

by:Fernando Soto
Fernando Soto earned 800 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: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

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.

Question has a verified solution.

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

For those of you who don't follow the news, or just happen to live under rocks, Microsoft Research released a beta SDK (http://www.microsoft.com/en-us/download/details.aspx?id=27876) for the Xbox 360 Kinect. If you don't know what a Kinect is (http:…
Today I had a very interesting conundrum that had to get solved quickly. Needless to say, it wasn't resolved quickly because when we needed it we were very rushed, but as soon as the conference call was over and I took a step back I saw the correct …
Visualize your data even better in Access queries. Given a date and a value, this lesson shows how to compare that value with the previous value, calculate the difference, and display a circle if the value is the same, an up triangle if it increased…
We’ve all felt that sense of false security before—locking down external access to a database or component and feeling like we’ve done all we need to do to secure company data. But that feeling is fleeting. Attacks these days can happen in many w…

610 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