Solved

Find the top N values of a 2D array

Posted on 2013-06-07
7
503 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
  • 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 62

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
DevOps Toolchain Recommendations

Read this Gartner Research Note and discover how your IT organization can automate and optimize DevOps processes using a toolchain architecture.

 
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 62

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 35

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

DevOps Toolchain Recommendations

Read this Gartner Research Note and discover how your IT organization can automate and optimize DevOps processes using a toolchain architecture.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Video Player 11 23
application restarter  - for an exe that hangs 9 26
VB.NET 1 22
Help with preventing selection from a combobox 11 25
Calculating holidays and working days is a function that is often needed yet it is not one found within the Framework. This article presents one approach to building a working-day calculator for use in .NET.
It was really hard time for me to get the understanding of Delegates in C#. I went through many websites and articles but I found them very clumsy. After going through those sites, I noted down the points in a easy way so here I am sharing that unde…
This Micro Tutorial will teach you how to censor certain areas of your screen. The example in this video will show a little boy's face being blurred. This will be demonstrated using Adobe Premiere Pro CS6.
The Email Laundry PDF encryption service allows companies to send confidential encrypted  emails to anybody. The PDF document can also contain attachments that are embedded in the encrypted PDF. The password is randomly generated by The Email Laundr…

773 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