CODEWITHSUNDEEP
c#.netlistmaxmin
Rich Oliver
Rich Oliver

Reputation: 6109

Find Max/Min element without using IComparable<T>

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.

Upvotes: 5

Views: 6784

Answers (6)

phoog
phoog

Reputation: 43046

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."

Upvotes: 9

Steven Waterman
Steven Waterman

Reputation: 621

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)

Upvotes: 0

Saeed Amiri
Saeed Amiri

Reputation: 22555

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.

Upvotes: 3

Jason Down
Jason Down

Reputation: 22161

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).

Upvotes: 5

afrischke
afrischke

Reputation: 3866

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...

Upvotes: 0

shenhengbin
shenhengbin

Reputation: 4294

Use OrderBy Then get the first element

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

Upvotes: 3

Related Questions