Как найти первый элемент в соответствии с определенным порядком, используя LINQ в O (n)? - PullRequest
Новая
       12

Как найти первый элемент в соответствии с определенным порядком, используя LINQ в O (n)?

7 голосов
/ 14 февраля 2010

Предположим, у меня есть список элементов (например, сообщений), и я хочу найти первый элемент согласно некоторому нетривиальному порядку (например, PublishDate и затем CommentsCount в качестве тай-брейка). Естественный способ сделать это с помощью LINQ выглядит следующим образом: 

posts.OrderBy(post => post.PublishDate).ThenBy(post => post.CommentsCount).First()

Однако мой микрооптимизатор обеспокоен тем, что вызов OrderBy на самом деле стоит мне O (n * lgn) за сортировку всего списка, когда все, что мне действительно нужно, - это операция O (n) с минимальным поиском.

Итак, достаточно ли LINQ для того, чтобы возвращать что-то из OrderBy (), которое знает, как оптимизировать последующие вызовы First ()? Если нет, то какой лучший способ сделать это из коробки? (Я всегда могу написать свою собственную реализацию FindMinimumItem, но это кажется излишним).

Ответы [ 3 ]

2 голосов
/ 14 февраля 2010

Это в SQL или LINQ to Objects? Если это последнее, вы, вероятно, хотите MinBy из MoreLINQ ; Ваше заявление в том виде, в котором оно написано, действительно отсортирует, а затем возьмет первый пункт.

И да, это позор, что он не включает это (и подобные вещи, как DistinctBy) из коробки.

РЕДАКТИРОВАТЬ: я вижу, ваш вопрос теперь изменился; MoreLINQ не поддерживает такое сложное сравнение. В MiscUtil у меня есть код для создания соединения IComparer<T> - вы можете передать его в MinBy, используя функцию идентификации в качестве селектора ключа. Не стесняйтесь добавлять запрос функции для MinBy, который принимает источник, и IComparer<T> без ключевого селектора:)

2 голосов
/ 14 февраля 2010

Сортировка разумна в том смысле, что она будет выполнять 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.)

0 голосов
/ 14 февраля 2010

Обычно это max или min (я не знаю, как это называется в LinQ), учитывая конкретный ключ; сортировка и получение первого или последнего кажется излишним на любом языке или в любой структуре.

...