Linq – optymalizacja Single oraz Last

Ostatnimi czasy zamiast siedzieć nad moim gitWebem, grzebie w kodzie źródłowym .NET. W dzisiejszym wpisie chciałem opisać dwie bardzo przydatne oraz często wykorzystywane metody LinqSingle oraz Last.

Ale dlaczego opisywać tak proste i powszechnie wykorzystywane metody?

Ano dlatego:

Single

Widzicie?  Warunek jest weryfikowany na każdym elemencie kolekcji. Pytanie brzmi dlaczego na każdym?! Czy sprawdzanie nie powinno być przerwane na drugim elemencie spełniającym warunek? Moja implementacja pętli:

To teraz benchmark:

Jak widać wyniki mówią same za siebie.

Ciekawa implementacja znajduje się w CoreFx. Sprytnie zlikwidowano zamieniono zliczanie powtórzeń i warunek sprawdzający na dodatkową wewnętrzną pętlę, iterującą od momentu spełnienia warunku.

 

Pierwsze wzmianki nt. tego błędu/niedoskonałości można znaleźć już w 2013 roku, póki co w obecnej wersji .NET nie zostało to jeszcze poprawione. Jak dobrze zauważył kolega Szymon brak poprawy w implementacji mógł być spowodowany koniecznością zachowania wstecznej kompatybilności. Ale dalej uważam, że stosowne by było dodanie chociaż w komentarzu wzmianki.

Last

Obecna implementacja:

Jaki tu jest problem? Metoda Last, która ma pobrać ostatni pasujący element iteruje od początku! W przypadku list gdzie mamy dostęp do elementu poprzez indeks, aż się prosi aby iterować od tyłu. Lepsza wersja mogła by wyglądać tak:

 

Tak jak w metodzie Single, trudno mi zrozumieć, dlaczego to jeszcze nie zostało naprawione. Wydaje się, że było to najwidoczniej przeoczenie bo w implementacji .NET Core obie dwie metody zostały poprawione (last, single)

Podsumowanie

Mam nadzieje, że po przeczytaniu tego posta nie zaczniecie przepisywać Waszych aplikacji na nowo. Nie o to chodzi. Prawdopodobnie w 99% przypadków ten błąd nie będzie miał większego znaczenia na działanie Waszej aplikacji. Ważne jest to aby widzieć, że coś takiego występuje.

Po raz kolejny chciałem pokazać, że wiedza o narzędziach/bibliotekach jest szalenie istotna. Może w tej aplikacji nie będzie Ci potrzebna optymalizacja na tym poziome, no ale w następnej?

Ps. Pisząc tego posta szukałem materiałów i natrafiłem na post Jona na ten sam temat.

 

  • suvroc

    Ciekawy temat. Jednak jak się głębiej zastanowić to zarówno Single jak i Last nie mogą być zaimplementowane inaczej.
    Single – opisujesz Single, ale w swoim kodzie zaimplementowałeś First. Jeżeli chcemy wiedzieć, czy wybieramy rzeczywiście unikalny element ze zbioru to musimy sprawdzić wszystkie elementy.
    Last – sam napisałeś w poście o indexach. Rzeczywiście mając możliwość iterowania od końca dużo łatwiej jest odnaleźć ostatni element. Jednak zauważ, ze Last operuje na IEnumerable, który nie implementuje indeksatorów.

    Moja jedyna sugestia w tym przypadku to po prostu warto znać wszystkie metody LINQ i wiedzieć jak one działają.

    • Norek

      No i właśnie w mojej implementacji dokładnie to wiemy. W przypadku gdy mamy unikalny element i tak predykat jest weryfikowany na każdym elemencie. Jedyne co poprawiłem to warunek stopu. Bo po co iterować dalej jeżeli wiemy że Nasz element się powtarza?

      Co do Last, faktycznie do dorzuciłem reszty implementacji, poprawię to. Ale napisałem, jeżeli sprawdzamy kolekcję implementującą indeksy, a więc np IList. Więc wewnątrz metody powinno być sprawdzenie czy Source nie jest typu IList. Dodatkowo dodam że takie sprawdzenie jak nie patrzeć jest powszechnie stosowane w Linq. Jeżeli chodzi o czysty IEnumerable, tak masz rację.
      Dodatkowo na potwierdzenie tego co napisałem, możesz zobaczyć implementację tych metod w .net core, corefx. Dokładnie stosują tam ten sam koncept który przedstawiłem.
      Dzięki za uwagi

  • Nienaprawienie błędu mogę wytłumaczyć kompatybilnością wsteczną. Jeżeli z kodu, który iteruje po całej kolekcji i przechodzi przez każdy element, zmieniłbyś to na kod, który kończy wykonanie po k-tym elemencie, to jeżeli miałeś kod, który wyrzuca wyjątek przy dojściu do ostatniego to już tego nie robi, a wyrzucany jest wyjątek związany z Single. Innymi słowy, każdy kod, który ma side-effecty związane z iterowaniem, mógłby być złamany przez taką zmianę.

    • Norek

      Kurde wiesz, że zupełnie o tym nie pomyślałem? Faktycznie to może być to. Kurde to tylko pokazuje jak trudne jest tworzenie frameworka tej klasy.

  • Pingback: dotnetomaniak.pl()