Найти элемент Max / Min без использования IComparable <T> - PullRequest
Новая
       34

Найти элемент Max / Min без использования IComparable <T>

5 голосов
/ 06 января 2012

Скажем, у меня есть следующее: 

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

public List<BooClass> booList;

Так, например, как мне получить элемент с самым ранним временем в поле 3, используя booList.Find ()

Править Извинения, я имел в видусделать все поля общедоступными для простоты примера.Я знаю, что это можно сделать в linq. Интересно, существует ли простое однострочное условие для метода Find.

Ответы [ 6 ]

8 голосов
/ 06 января 2012

F # имеет удобные операторы minBy и maxBy, которые я хотел бы реализовать как методы расширения C #, поскольку библиотека Linq их опускает.Это немного работы, но только немного, и это позволяет вам избегать сложных выражений, таких как 

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

Вместо этого вы можете ввести следующее: 

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

Простая реализация:

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;
}

Это также несколько более эффективно, чем сложное выражение в верхней части, поскольку MinBy выполняет итерацию последовательности ровно один раз, в то время как выражение выполняет итерацию более одного раза и меньше или равно двум.И, конечно же, для сортировки и последующего выбора первого элемента требуется сортировка, то есть O (n log n), а это всего лишь O (n).

5 голосов
/ 06 января 2012

Вам нужно будет выставить field3 через публичное свойство (назовем его Field3), но вы можете использовать это: 

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

Взгляните на Enumerable.First и Enumerable.Min

ПРИМЕЧАНИЕ. Это имеет временную сложность O (n ^ 2) (квадратичное время), потому что он пересекает список через Min каждую итерацию. Достаточно большая коллекция увидит серьезные проблемы с производительностью по сравнению с ответом Саида Амири , который работает за O (n) (линейное время).

3 голосов
/ 06 января 2012

Используйте OrderBy, затем получите первый элемент 

var result = booList.OrderBy(p => p.field3).FirstOrDefault();
2 голосов
/ 06 января 2012

Подход O (n) заключается в следующем. Сначала найдите минимальную дату (для поля 3), затем найдите первый объект с этой минимальной датой: 

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

Просто сделайте вашу собственность публичной.

0 голосов
/ 20 сентября 2018

Если вы не хотите определять метод MinBy, вы можете использовать агрегат следующим образом: 

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

Чтобы поддерживать пустые списки, заполните агрегат нулем, например: 

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

Это решение O (n)

0 голосов
/ 06 января 2012

Насколько я могу судить, нет способа извлечь объект BooClass с минимальной датой, просто используя List<T>.Find.Конечно, вы можете сделать это: 

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;
}

(что, как и решение Саида, также имеет O (n) сложность по времени), но я думаю, это будет считаться обманом ...

...