Как найти первый объект согласно определенному упорядочиванию с помощью LINQ в O (n)?
Предположим, что у меня есть список объектов (например, Сообщения), и я хочу найти первый объект согласно некоторому нетривиальному упорядочиванию (например, PublishDate и затем CommentsCount как дополнительное время). Естественный способ сделать это с LINQ похоже на это:
posts.OrderBy(post => post.PublishDate).ThenBy(post => post.CommentsCount).First()
Однако микрооптимизатор во мне волнуется, что вызов OrderBy на самом деле стоит мне O (n*lgn) для сортировки всего списка, когда все, в чем я действительно нуждаюсь, является O (n) операция находить-минимума.
Так, LINQ достаточно умный для возврата чего-то из OrderBy (), который знает, как оптимизировать последующий Первый () вызовы? В противном случае, что лучший путь состоит в том, чтобы сделать этот out-of-the-box? (Я могу всегда писать свою собственную реализацию FindMinimumItem, но это походит на излишество).
3 ответа
Сортировка умна тем, что она будет выполнять ThenBy только для первой группы из OrderBy, но OrderBy все равно должен отсортировать все элементы, прежде чем он сможет вернуть первую группу.
Вы можете использовать метод Aggregate, чтобы получить первое сообщение в соответствии с пользовательским сравнением:
Post lowest =
posts.Aggregate((Post)null,
(x, y) =>
x == null
|| y.PublishDate < x.PublishDate
|| (y.PublishDate == x.PublishDate && y.CommentsCount < x.CommentsCount)
? y : x
);
(Предполагая, что вы используете LINQ to Objects, конечно.)
. Это в SQL или LINQ to Objects? В последнем случае вам, вероятно, понадобится MinBy из MoreLINQ ; ваше заявление в том виде, в котором оно написано, действительно отсортирует, а затем возьмет первый элемент.
И да, жаль, что он не включает это (и подобные вещи, такие как DistinctBy ) из коробки.
РЕДАКТИРОВАТЬ: Я вижу, что ваш вопрос теперь изменился; MoreLINQ не поддерживает подобное сложное сравнение. В MiscUtil у меня есть код для создания составного IComparer - вы можете передать его в MinBy , используя функцию идентификации в качестве селектора ключа. Не стесняйтесь добавить запрос функции для MinBy , который принимает источник и IComparer без ключевого селектора :)
Обычно это max или min (я не знаю, как это называется в LinQ), учитывая конкретный ключ; сортировка и получение первого или последнего кажется излишним для любого языка или фреймворка.