Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find Max/Min element without using IComparable<T>

Tags:

c#

.net

list

max

min

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.

like image 350
Rich Oliver Avatar asked Jan 06 '12 13:01

Rich Oliver


3 Answers

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

like image 105
phoog Avatar answered Nov 12 '22 00:11

phoog


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

like image 20
Jason Down Avatar answered Nov 11 '22 22:11

Jason Down


Use OrderBy Then get the first element

var result = booList.OrderBy(p => p.field3).FirstOrDefault();
like image 23
shenhengbin Avatar answered Nov 11 '22 23:11

shenhengbin