Come trovare il primo elemento in base a un ordine specifico utilizzando LINQ in O (n)?

Question

Supponiamo di avere un elenco di elementi (ad esempio, Post) e voglio trovare il primo elemento in base ad alcuni ordinamenti non banali (ad esempio, PublishDate e quindi CommentiCount come tie-breaker). Il modo naturale per fare questo con LINQ è come questo:

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

Tuttavia, il micro-ottimizzatore in me, è preoccupato che chiama OrderBy mi O (n * LGN) costa in realtà per l'ordinamento l'intero elenco, quando tutti Ho davvero bisogno di un'operazione di ricerca O (n) minima.

Quindi, LINQ è abbastanza intelligente da restituire qualcosa da OrderBy() che sa come ottimizzare le chiamate First() successive? In caso contrario, qual è il modo migliore per farlo subito? (Posso sempre scrivere la mia implementazione su FindMinimumItem ma sembra eccessivo).

Answer 1

L'ordinamento è intelligente nel modo in cui sarà solo fare il ThenBy sul primo gruppo dal OrderBy, ma lo OrderBy deve ancora ordinare tutti gli elementi prima che possa restituire il primo gruppo.

È possibile utilizzare il metodo di aggregazione per ottenere il primo post in base ad un confronto personalizzato: (. Supponendo che si sta utilizzando LINQ to Objects, naturalmente)

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

Solitamente quello è un max o min (non so come viene chiamato in LinQ), data una chiave specifica; ordinare e ottenere il primo o l'ultimo sembra eccessivo in qualsiasi lingua o struttura.

Answer 3

Si tratta di SQL o LINQ su oggetti? Se è il secondo, probabilmente vuoi MinBy da MoreLINQ; la tua affermazione scritta scriverà davvero e poi prenderà il primo oggetto.

E sì, è un peccato che non includa questo (e cose simili come DistinctBy) fuori dalla scatola.

EDIT: Vedo che la tua domanda è ora cambiata; MoreLINQ non supporta un confronto composto come quello. In MiscUtil ho codice per creare un composto IComparer<T> - è possibile passare questo in MinBy utilizzando la funzione di identità come selettore di chiave. Sentitevi liberi di aggiungere una richiesta di funzionalità per un MinBy che prende una fonte ed un IComparer<T> senza un selettore a chiave :)