Comment trouver le premier article selon un ordre spécifique en utilisant LINQ dans O (n)?

Question

Supposons que j'ai une liste d'éléments (par exemple, Posts) et que je souhaite trouver le premier élément en fonction d'un ordre non trivial (par exemple, PublishDate et ensuite CommentsCount comme un tie-breaker). La façon naturelle de le faire avec LINQ est comme ceci:

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

Cependant, le micro-optimiseur me craint que l'appel OrderBy me coûte réellement O (n * LGN) pour trier la liste entière, quand tout J'ai vraiment besoin d'une opération O (n) find-minimum. Donc, LINQ est-il assez intelligent pour renvoyer quelque chose de OrderBy() qui sait comment optimiser les appels First() suivants? Si ce n'est pas le cas, quelle est la meilleure façon de le faire dès la sortie de l'emballage? (Je peux toujours écrire ma propre implémentation de FindMinimumItem mais cela semble être trop compliqué).

Answer 1

Le tri est intelligent dans la façon dont il ne le fera que le ThenBy sur le premier groupe de la OrderBy, mais le OrderBy doit encore trier tous les éléments avant de pouvoir renvoyer le premier groupe.

Vous pouvez utiliser la méthode globale pour obtenir le premier poste selon une comparaison personnalisée: (. En supposant que vous utilisez LINQ to Objects bien sûr)

Post lowest = 
    posts.Aggregate((Post)null, 
    (x, y) => 
     x == null 
     || y.PublishDate < x.PublishDate 
     || (y.PublishDate == x.PublishDate && y.CommentsCount < x.CommentsCount) 
     ? y : x 
); 

Answer 2

Habituellement c'est un max ou min (je ne sais pas comment ça s'appelle dans LinQ), donné une clé spécifique; trier et obtenir le premier ou le dernier semble exagéré dans n'importe quel langage ou cadre.

Answer 3

Est-ce dans SQL ou LINQ to Objects? Si c'est le dernier, vous voulez probablement MinBy de MoreLINQ; votre déclaration telle qu'écrite va en effet trier et ensuite prendre le premier article.

Et oui, il est dommage qu'il ne comprend pas cela (et des choses similaires comme DistinctBy) sortie de l'emballage.

EDIT: Je vois que votre question a maintenant changé; MoreLINQ ne supporte pas une comparaison composée comme ça. En MiscUtil j'ai le code pour créer un composé IComparer<T> - vous pouvez passer cela en MinBy en utilisant la fonction d'identité comme le sélecteur de clé. Vous pouvez ajouter une demande de fonctionnalité pour une MinBy qui prend une source et un IComparer<T> sans sélecteur à clé :)