CODEWITHSUNDEEP
c#listperformancelinq
Azeranth
Azeranth

Reputation: 145

Efficiently selecting from subsets of a list

Given a List of Vectors, how can I efficiently Select all of the greatest values of a property, among all members who share other values among different properties.

For example, with the standard Vector3, how would I choose the Vector3s who have the largest Y value relative to all other members with identical X and Z values.

My current working method, is to iterate through the list like so:

Vector3 current = Vector3.Zero;
List<Vector3> out = new List<Vector3>();
foreach(var member in MyList)
{
    current= member;
    foreach(var compare in MyList)
    {
        if(!predicate(current,compare))
            current = compare;
    }
    out.Add(largest);
}

But this doesn't seem particularly efficient, as it performs n squared comparisons, where n is the length of the list.

Any suggestions on cutting this down to a more workable number, as I intend to use this in a performance critical section of my code.

For the predicate of equal X and Z values, the greatest value of Y

Example Input:

(1,1,1)
(1,2,1)
(1,4,1)
(2,3,2)
(2,5,2)
(1,4,2)
(1,2,2)
(1,1,2)
(2,5,1)
(2,4,1)
(2,9,1)

Expected Output:

(1,4,1)
(2,5,2)
(1,4,2)
(2,9,1)

Upvotes: 1

Views: 66

Answers (1)

ProgrammingLlama
ProgrammingLlama

Reputation: 38890

You can use LINQ for this:

var result = vectors
    .GroupBy(v => Tuple.Create(v.X, v.Z))
    .Select(vg => vg.OrderByDescending(v => v.Y).First())
    .ToList();
  • The GroupBy will use a Tuple of X and Z as a key.
  • From each group, we Select the value with the largest Y value.

Try it online

Upvotes: 5

Related Questions