Mam;Złożoność przestrzeni prostej zapytania linq (do obiektów)
var maxVal = l.TakeWhile(x=>x < val).Where(x=>Matches(x)).Max();
Ile miejsca potrzeba? Czy linq tworzy listę powyższego warunku Where(), czy też Max() po prostu iteruje przez IEnumerable, śledząc bieżący Max()?
A gdzie mogę znaleźć więcej informacji na ten temat, poza pytaniem na SO f
Zostały zweryfikowane z reflektorem, że każdy z Enumerable.TakeWhile, Enumerable.Where i Enumerable.Max prowadzonym w stałym miejscu. W związku z tym całe to zapytanie powinno działać w stałej przestrzeni. Nic dziwnego, biorąc pod uwagę TakeWhile i Gdzie są speced do korzystania z odroczonego wykonania + streaming. Max nie używa odroczonego wykonywania, ale musi tylko przechowywać "maksimum do tej pory", a moduł wyliczający na źródłowym wyliczalnym.
Zgodnie z metodą ReflectorMax() iteruje przez przeliczalne.
A gdzie mogę znaleźć więcej informacji na ten temat, poza pytaniem na SO f
Można użyć Reflector patrzeć na realizację dowolnego zestawu .NET.
Reflector jest twoim przyjacielem.
W szczególności można rzucić okiem na metody Linq do Objects w klasie Enumerable w System.Linq.
Powyższe używają iteracji, więc używają one dowolnej przestrzeni zajmowanej przez moduły wyliczające - zwykle O (1). Max() to O (1) spacja.
Należy jednak pamiętać, że nic nie powstrzymuje programisty przed napisaniem modułu wyliczającego, który zajmuje więcej niż stałą przestrzeń. Na przykład. przechodzenie przez drzewo może wymagać przestrzeni O (log n). Tak jest w przypadku np. dla SortedDictionary<K,V> i SortedSet<K,V>.
Częściowo zależy to od kodu l.
Jedyną rzeczą oferowaną przez Enumerable, którą znalazłem, nie działa w stałej przestrzeni, jest ToList(), z oczywistych powodów.
Przy niektórych wyliczeniach jest to nieefektywne, ponieważ masz już złożoność przestrzeni powyżej stałej (zwykle O (n) podczas przechowywania elementów) i że dana kolekcja oferuje mechanizm o mniejszej złożoności czasu. Jeśli sam tworzysz taką kolekcję, warto oferować własne wersje rozszerzeń oferowanych przez Enumerable. Na przykład, jeśli masz kolekcję, która jest nieodłącznie posortowana, powinieneś być w stanie zaoferować Min() i Max() w stopniu lepszym od złożoności O (n) (bez względu na to, czy jest to O (1), O (ln) czy coś innego zależy od tego, w jaki sposób przechowywano sortowanie). Ponieważ metody instancji zastępują metody rozszerzeń (gdy wywoływane jest wyrażenie typu obiektu, a nie typ instancji), to bez żadnej różnicy od kodera korzystającego z obiektu, zapewnisz lepszą wydajność.
Według mojej wiedzy, żadne z metod ToArray(), ToList(), ToDictionary(), ToLookup(), OrderBy(), OrderByDescending(), GroupBy(), Distinct() działają w stałej przestrzeni. Może być ich więcej. Masz jednak rację co do wydajności; Nie nazwałbym SortedList.Values.Max(), ale kto wie, jakie optymalizacje stwardnienie rozsiane wprowadzi w przyszłości. – Ani
Gah! Tak, ci, o których wspomniałeś, są ponad stałą przestrzenią, po prostu wsunęli mi się do głowy, komentując. Jedna z optymalizacji, którą już wprowadzono, polega na tym, że Count() sprawdza, czy wyliczenie to ICollection, a jeśli tak, zwraca wartość jego właściwości Count. –
Ma to sens, że Max nie używa odroczonego wykonywania, ponieważ zwraca wartość T nie jest liczbą. Innym sposobem patrzenia na to, jest to, że żaden z nich naprawdę nie odłożył wykonania; wszystkie natychmiast zwracają obiekt, który będzie się zachowywał na różne sposoby, gdy zostanie wyliczony przez.Wynik Max() nie jest jednak wyliczany przez. Chociaż nie jest to najlepszy sposób myślenia o rzeczach przez większość czasu, może pomóc, gdy próbuje zapamiętać, co jest i nie jest odroczone. –