Solved

Find the top N values of a 2D array

Posted on 2013-06-07
7
511 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
The Orion Papers

Are you interested in becoming an AWS Certified Solutions Architect?

Discover a new interactive way of training for the exam.

 
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

Independent Software Vendors: 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!

Question has a verified solution.

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

This article is for Object-Oriented Programming (OOP) beginners. An Interface contains declarations of events, indexers, methods and/or properties. Any class which implements the Interface should provide the concrete implementation for each Inter…
Wouldn’t it be nice if you could test whether an element is contained in an array by using a Contains method just like the one available on List objects? Wouldn’t it be good if you could write code like this? (CODE) In .NET 3.5, this is possible…
Michael from AdRem Software explains how to view the most utilized and worst performing nodes in your network, by accessing the Top Charts view in NetCrunch network monitor (https://www.adremsoft.com/). Top Charts is a view in which you can set seve…
This is my first video review of Microsoft Bookings, I will be doing a part two with a bit more information, but wanted to get this out to you folks.

691 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