Find Max/Min element without using IComparable<T>

Question

Say I have the following:

public Class BooClass
{
   public int field1;
   public double field2;
   public DateTime field3;
}

public List<BooClass> booList;

So for example how do I get the element with the earliest time in field3 using booList.Find()

Edit Apologies, I meant to make all the fields public for simplicity of the example. I know can do it in linq, I wondered if there is a simple single line condition for the Find method.

Violation

Answer 1

F# has handy minBy and maxBy operators, which I like to implement as C# extension methods, since the Linq library omits them. It's a bit of work, but only a bit, and it allows you to avoid complex expressions such as

var earliest = booList.First(b => b.Field3 == booList.Min(e => e.Field3));

Instead, you can type this:

var earliest = booList.MinBy(b => b.Field3);

A simple implementation:

static T MinBy<T, C>(this IEnumerable<T> sequence, Func<T, C> keySelector)
{
    bool first = true;
    T result = default(T);
    C minKey = default(C);
    IComparer<C> comparer = Comparer<C>.Default; //or you can pass this in as a parameter

    foreach (var item in sequence)
    {
        if (first)
        {
            result = item;
            minKey = keySelector.Invoke(item);
            first = false;
            continue;
        }

        C key = keySelector.Invoke(item);
        if (comparer.Compare(key, minKey) < 0)
        {
            result = item;
            minKey = key;
        }
    }

    return result;
}

This is also somewhat more efficient than the complex expression at the top, since MinBy iterates the sequence exactly once, while the expression iterates more than once and less than or equal to twice. And, of course, sorting and then taking the first item requires sorting, which is O(n log n), while this is just O(n).

As noted by Saeed Amiri, this approach doesn't work if you are relying on Linq to SQL or any other IQueryable<> provider. (More precisely, it works inefficiently because it pulls the objects from the database and works on them locally.) For a solution that doesn't do this, see Saeed's answer.

You could also make an extension method based on that approach, but as I am on my phone at the moment I'll leave the implementation as the proverbial "exercise for the reader."

Ioyal

Excellent! And if you use a particular field a few times for Min or Max, just adding a property would be simpler than implementing IComparable<T>, which of course can only be implemented for one value. – Violation

For such a simple problem offering n lines of code is not good, it's not optimum, readable also it's not related to problem complexity. – Amnion

@SaeedAmiri but the MinBy method is intended as a library method, in another class, simplifying lots of client code at the expense of creating a separate, more complex method. That's why we have methods in the first place. They allows decomposition, reduced duplication/code reuse, and the hiding of implementation details, among other advantages. How is var earliest = booList.MinBy(b => b.Field3); not readable? – Ioyal

@SaeedAmiri also, the implementation as given has some shortcomings as a library method, and would require, for example, null checks and so forth. On the other hand, if one wished to implement it as a private method, one might have a stronger contract (for example, it might be known that the sequence will never be empty, or that T will always -- or never -- be a class type, or that it implements IComparable<T>). In that case, the method could comprise fewer lines of code. – Ioyal

For this purpose may be library doesn't have one line solution, but still it has short answer like my answer, which is O(n), and there is no need to creating the wheel, Also your method doesn't work in linq2sql so it's not extendable solution. – Amnion

@SaeedAmiri I came back to this answer because of an upvote. You're right that the lack of support in a query provider such as Linq to SQL could be significant. I'll edit add a link to your answer. – Ioyal

Cool to receive such a comment after nearly 10 years :-) Since then I did not answer many questions at SO and only sometimes was updating my answers because of comments or upvotes. – Amnion

Answer 2

You'll need to expose field3 through through a public property (we'll call it Field3), but you could use this:

var earliest = booList.First(b => b.Field3 == booList.Min(e => e.Field3));

Take a look at Enumerable.First and Enumerable.Min

NOTE: That this has a time complexity of O(n^2) (quadratic time) because it is traversing the list via Min each iteration. A large enough collection will see serious performance issues compared to Saeed Amiri's answer, which runs in O(n) (linear time).

Antecedency

Oops, jumped the gun. I'll fix that now. – Antecedency

Sorry that was an oversight not making the fields public. – Violation

Answer 3

The O(n) approach is as follows. First find min date (for field3), then find first object with this min date:

var minDate = booList.Min(x=>x.field3);
var item = booList.First(x=>x.field3 == minDate);

Just make your property public.

Amnion

BooClass earliest = booList.First(i => i.field3 == booList.Min(j => j.field3)); //I think this is the shortest syntax but does it take longer than the Linq methods? – Violation

@RichOliver, what's the benefit of shorter syntax? my code runs in O(n) your syntax or Jason answer runs in O(n^2) so why I should offer slower answer? Also I can write this in just one query, but for making it more readable I wrote it in two line. – Amnion

I do prefer your method over mine @SaeedAmiri . My answer will have pretty poor performance once the size of the collection increases enough. – Antecedency

@SaeedAmiri Personally I like strong typing but minimal ceremony. I'd prefer it if C# allowed a field as a method parameter then, Phoog's syntax could be slimmed to: BooClass earliest = booList.Min(field3); – Violation

@RichOliver, If you want write your own extension method this can be done with available linq library and there is no need to re invent the wheel, Also by using let you can convert my 2 query to one query (but is not very readable), Also as I wrote phoog answer extendable in linq2sql, but you are free to accept answer which you like it more. is not – Amnion

@SaeedAmiri don't these statements evaluate to O(n + m)? – Actress

@CoffeeMuncher, I supposed whole input is of size n. – Amnion

Answer 4

Use OrderBy Then get the first element

var result = booList.OrderBy(p => p.field3).FirstOrDefault();

Convertible

dknaack answered in similar way, why you add this after a 10 minutes? – Amnion

Sorry , I donnt know the time limit . I just see it now... :( – Convertible

Similar, but not the same. I like this syntax better better. – Built

Answer 5

As far as I can tell, there is no way to retrieve the BooClass object with the minimal date by just using List<T>.Find. Of course you can do this:

void Main()
{
    List<BooClass> booList = new List<BooClass> { 
                        new BooClass { field3 = DateTime.MaxValue}, 
                        new BooClass { field3 = DateTime.Now },
                        new BooClass { field3 = DateTime.MinValue }};
    var pred = GetPredicate(booList);
    var result = booList.Find(pred);
}

public Predicate<BooClass> GetPredicate(List<BooClass> boos)
{
    var minDate = boos.Min(boo => boo.field3);   
    return bc => bc.field3 == minDate;
}

(which - just like Saeed's solution - also has O(n) time complexity), but I guess that would be considered cheating...

Mantel

Answer 6

If you don't want to define a MinBy method, you can use aggregate like so:

booList.Aggregate((currMin, test) => currMin < test ? currMin : test);

To support empty lists, seed the aggregate with null, like so:

booList.Aggregate(null, (currMin, test) => null == currMin || currMin > test ? test : currMin);

This solution is O(n)

Weakness