2010-02-14 8 views
7

Załóżmy, że mam listę elementów (np. Posty) i chcę znaleźć pierwszy element zgodnie z niektórymi niebanalnymi zamówieniami (np. PublishDate, a następnie CommentCount jako łamacz). Naturalny sposób to zrobić z LINQ jest tak:Jak znaleźć pierwszy element zgodnie z konkretnym zamówieniem przy użyciu LINQ w O (n)?

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

jednak mikro-optymalizator we mnie martwi, że nazywając orderby faktycznie kosztuje mnie O (n * LGN) do sortowania całą listę, gdy wszystkie Naprawdę potrzebuję operacji minimum O (n) find.

Czy LINQ jest wystarczająco inteligentny, aby zwrócić coś od OrderBy(), który wie, jak zoptymalizować kolejne wywołania First()? Jeśli nie, jaki jest lepszy sposób na zrobienie tego po wyjęciu z pudełka? (Zawsze mogę napisać własną implementację FindMinimumItem, ale to wydaje się przesadą).

+0

jeśli klucz jest faktycznie jak wydrukowano, że nie potrzebujesz elementu ThenBy, ale możesz zamiast tego utworzyć klucz coumpund z dwóch. Co byłoby łatwe, ponieważ pierwsza z nich to długa (tyka) lub ustalona z ciągiem. a to może być O (n), o które prosisz, ale potem znowu nie ma garanty, że O (n) jest szybsze niż O (nlogn) –

Odpowiedz

2

Sortowanie jest silny w taki sposób, że będzie to zrobić tylko ThenBy na pierwszej grupy z OrderBy, ale OrderBy musi jeszcze posortować wszystkie elementy, zanim będzie mogła zwrócić pierwszą grupę.

Można użyć metody zbiorczej uzyskać pierwszy post zgodnie z porównania niestandardowe: (. Zakładając, że używasz LINQ to Objects oczywiście)

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

+0

Dzięki, to dobre rozwiązanie, choć trochę gadatliwe. – Avish

0

Zwykle jest to max lub min (nie wiem jak się nazywa w LinQ), biorąc pod uwagę określony klucz; sortowanie i otrzymywanie pierwszego lub ostatniego wydaje się przesadą w dowolnym języku lub strukturze.

+0

Metody, które biorą klucze w LINQ, niestety zwracają sam klucz maksimum/minimum zamiast obiektu zawierające ten klucz. –

+0

czy nie można wtedy wykonać skomponowanego klucza? W Pythonie bardzo typowe jest ustawienie tymczasowej krotki, która zawiera klucz i cały rekord, ponieważ są one porównywane leksykograficznie. – fortran

+1

Chociaż .NET 4.0 ma typ krotki, system .NET 3.5 nie. Możliwe, że to podejście zadziała w .NET 4.0, ale nie jestem pewien, czy jest to bardzo idiomatyczne. –

2

Czy jest to w SQL lub LINQ do obiektów? Jeśli jest to drugie, prawdopodobnie chcesz MinBy z MoreLINQ; twoje oświadczenie w formie pisemnej będzie rzeczywiście sortować, a następnie wziąć pierwszy przedmiot.

I tak, szkoda, że ​​nie obejmuje tego (i podobnych rzeczy, takich jak DistinctBy) po wyjęciu z pudełka.

EDYCJA: Widzę, że twoje pytanie się zmieniło; MoreLINQ nie obsługuje takiego złożonego porównania. W MiscUtil Mam kod do utworzenia związku IComparer<T> - można go przekazać do MinBy, używając funkcji tożsamości jako selektora klawiszy. Zapraszam do dodawania żądania funkcji dla MinBy który bierze źródło oraz IComparer<T> bez klucza selektora :)

+0

Dzięki, popatrzę na te. Naprawdę szkoda, że ​​nie ma gotowego sposobu na konwersję między zestawami wyrażeń kluczowych (np. W przypadku użycia polecenia OrderBy ... ThenBy) i programu IComparer. – Avish

+1

Alternatywą dla 'ThenBy' może być zwrot krotki:' Tuple.Create (post.PublishData, post.CommentsCount) '. –