LINQ Extensions 2: Minimum/Maximum by key

Last week we talked about LINQ, its usefulness, and how to write our own methods to make it even more powerful. Today, I want to look at another couple methods that I have found handy in a number of different situations. We will look at how to extract the maximum or minimum element of a list by a given key or selector.

Note: Check here for more posts on extending LINQ.

Example

Imagine we have a list of Images, and each has a Width and Height.

What we to be able to get:

1. the image with the largest/smallest width;
2. the image with the largest/smallest area.

And ideally we want to be able to do so with as little – and as clear – code as possible.

LINQ Max()/Min()

LINQ has very useful Max() and Min() methods that can be used to respectively extract the maximum and minimum element of a list.

For example, we could do the following:

var minInteger = listOfIntegers.Min();
// or with images:
var minHeight = images
    .Select(image => image.Height)
    .Min();

Or even easier:

var minHeight = images
    .Min(image => image.Height);

Unfortunately, doing either of these will only return the minimum height of all the images. It will not return the actual image itself.

We could take that height and iterate the list again, to get the appropriate image as follows:

var minHeightImage = images
    .First(image => image.Height == minHeight);

However, this requires us to enumerate the list more than once, which really should not be necessary.

We will write our own methods to implement the same behaviour with only a single enumeration, but keeping allowing it to be used as easily as the existing Min() and Max() methods.

Intended usage

To make our methods as easy to us as possible, let us first see how we actually want to use them, before implementing their behaviour.

We want to:

• call them as a single extension method on our collection;
• give them a method or lambda to select the key we care about (in our case the width, height, or area);
• have the method return the single element that has the largest/least key, as selected by the given selector method/lambda.

In code:

var widestImage = images.MaxBy(image => image.Width);
var smallestAreaImage = images
    .MinBy(image => image.Width * image.Height);
var greenestImage = images.MaxBy(countGreenPixels);
private int countGreenPixels(Image image)
{
    // return number of green pixels
}

Method signature

Clearly, out extension method needs to have a signature like the following.

Note that we will look only at the MaxBy method from now on, since the MinBy is really just the same with an inverted comparrision.

static TItem MaxBy<TItem, TKey>(
    this IEnumerable<TItem> items,
    Func<TSource, TKey> keySelector
    )

Almost.

Unfortunately, since our keys are generic our method will have no way to compare two of them with each other to determine the maximum.

There are two solutions: We can either write several method overloads that specify the type of the key as numeric types like int, double, which can be compared directly, or we can make use of the IComparable interface.

Since it is more flexible, we will go with the second approach. Here we again have two options: There is both a generic and a non-generic version of IComparable.

The non-generic version is slightly simpler, but it is also less efficient, since it will box and unbox in case we are dealing with value-type keys. Since we are likely to do so more often than now, we will go with the generic interface.

This changes our method signature to the following:

static TItem MaxBy<TItem, TKey>(
    this IEnumerable<TItem> items,
    Func<TSource, TKey> keySelector
    )
    where TKey : IComparable<TKey>

Pseudo code

With the intended usage, and the method signature defined as well, let us think about how to make the method do what we want.

Here is some rough pseudo code on how we will proceed:

if list is empty
{
    return default(/null)
}
else if list has single element
{
    return that element
}
else
{
    largest element known = first element
    foreach (element = other elements)
    {
        if keySelector(element) >
           keySelector(largest element known)
        {
            largest element known = element
        }
    }
    return largest element known
}

Note how the second case is already covered by the third one – the foreach loop would simply not enumerate anything – so we can skip it.

First Implementation

With that, let us write some actual code that corresponds to the pseudo code.

if (items.Any())
    return default(TItem);
var largestKnownItem = item.First();
foreach (var item in items.Skip(1))
{
    if (keySelector(item).CompareTo(
        keySelector(largestKnownItem)
        ) > 0)
    {
        largestKnownItem = item;
    }
}
return largestKnownItem;

Note how we used the CompareTo() method of the IComparable interface: It returns a positive value if the instance we call it on – in this case the key of item – follows the parameter, i.e. if it is larger.

This method works exactly as intended.

However, there are some issues with it: Depending on what kind of collection we are looking at, we may now be enumerating the collection three times, instead of just twice, like in our original situation.

Both Any() and First() could – and in many circumstances well – cause the creation (and disposal) of an enumerator. Even though we do not enumerate the entire list, this is still rather wasteful.

Further, we call keySelector() twice as often as we need to: There is no need to recalculate the key of the largest known item for every other item. We can cache the result, which might speed up the method significantly, if the selector is expensive.

Caching keys

Caching the key is by far the easier of the two to fix:

if (items.Any())
    return default(TItem);
var largestKnownItem = item.First();
var largestKnownKey = keySelector(largestKnownItem);
foreach (var item in items.Skip(1))
{
    var key = keySelector(item);
    if (key.CompareTo(largestKnownKey) > 0)
    {
        largestKnownItem = item;
        largestKnownKey = key;
    }
}
return largestKnownItem;

And that is it. I would argue that this change makes the code not only faster, but even more clear and easier to read by getting rid of the nested method calls, and giving proper names to the values we are dealing with.

Enumerating only once

Let us now modify the method to enumerate the list only once. The trick here is to put the entire code into the foreach loop, and call the rights part of it depending on whether we are in the first iteration or not:

bool isFirstItem = true;
var largestKnownItem = default(TItem);
var largestKnownKey = default(TKey);
foreach (var item in items)
{
    var key = keySelector(item);
    if (isFirstItem)
    {
        largestKnownItem = item;
        largestKnownKey = key;
        isFirstItem = false;
    }
    else
    {
        if (key.CompareTo(largestKnownKey) > 0)
        {
            largestKnownItem = item;
            largestKnownKey = key;
        }
    }
}
return largestKnownItem;

Clearly we are now only enumerating the list a single time. Unfortunately, the method has become somewhat less clear – the branching in the loop may be confusing, despite the clear names, and the empty-list case is merely implied and not explicitly stated.

Performance of this method might also not be optimal. However, this is not what I would focus on. For once, the CPU is likely to detect the pattern of the conditional statement, and correctly predict the branching with high accuracy.

In addition, the compiler might even be smart enough to split the method into two, and unroll the first part. In fact, we can do so ourselves easily enough by remembering that a foreach loop translates essentially into the following:

using(var enumerator = items.GetEnumerator())
{
    // TItem item; // before C# 5, the variable was defined here
    while (enumerator.MoveNext())
    {
        TItem item;
        item = enumerator.Current;
        { /* loop body */ }
    }
}

By using this to replace the foreach loop in our method, and simplifying, we get:

using(var enumerator = items.GetEnumerator())
{
    // empty list special case
    if (!enumerator.MoveNext())
        return default(TItem);
    var largestKnownItem = enumerator.Current;
    var largestKnownKey = keySelector(largestKnownItem);
    // by using same enumerator,
    // first element is skipped in loop
    while (enumerator.MoveNext())
    {
        var item = enumerator.Current;
        var key = keySelector(item);
        if (key.CompareTo(largestKnownKey) > 0)
        {
            largestKnownItem = item;
            largestKnownKey = key;
        }
    }
    return largestKnownItem;
}

The only thing left to potentially optimised is that we are still calling keySelector() for a list of a single item.

I think for the purpose of this post, we have gone far enough however.

LINQ Aggregate – returning to simplicity

As we can see above, there is a lot we can do if we want to make micro-optimise our code.

I would argue that the code we created in the meantime – while efficient – might be even less readable than some of the code we had before.

Let us look at an entirely different solution: Instead of trying to reinvent the wheel, we will make use of an already existing LINQ method: Aggregate()

This method

Applies an accumulator function over a sequence

which essentially means that we loop over the collection while also keeping an arbitrary state that we can modify at any step, if we so choose.

In the case where this state is of the same type as the items of the list, using it is very easy: It takes a parameter that takes two items, and returns one. If we simply return the item with the larger key, Aggregate() will handle the rest for us.

This shortens our MaxBy() method body into the following:

return items.Aggregate(
    (a, b) => keySelector(a).CompareTo(keySelector(b)) > 0
        ? a
        : b
    );

A single line of code!

Note that we are again calling the key selector twice as often as we need to. However, the simplicity of the method can probably justify this easily.

For completeness, here are the two full methods, using Aggregate():

static TItem MaxBy<TItem, TKey>(
    this IEnumerable<TItem> items,
    Func<TSource, TKey> keySelector)
    where TKey : IComparable<TKey>
{
    return items.Aggregate(
        (a, b) => keySelector(a).CompareTo(keySelector(b)) > 0
            ? a : b);
}
static TItem MinBy<TItem, TKey>(
    this IEnumerable<TItem> items,
    Func<TSource, TKey> keySelector)
    where TKey : IComparable<TKey>
{
    return items.Aggregate(
        (a, b) => keySelector(a).CompareTo(keySelector(b)) < 0
            ? a : b);
}

We could use a different overload of Aggregate() to prevent the double key selector calls, however that would require us to make the method more complicated again, and requires us to use a tuple, custom or anonymous type to store the accumulating state. I believe this post is long enough.

Conclusion

I hope this post shows that there are usually more than a single solution to a problem – and that it may not always be clear which solution is the best.

In this case, I would recommend the methods presented last for almost every single circumstance, based on their simplicity, and almost obvious correctness.

Note: Check here for more posts on extending LINQ.

Enjoy the pixels!