Jestem zainteresowany złożonością asymptotyczną (duże O) operacji GroupBy na niezweryfikowanych zestawach danych. Jaka jest złożoność najbardziej znanego algorytmu i jaka jest złożoność algorytmów używanych przez serwery SQL i LINQ?Jaka jest asymptotyczna złożoność operacji GroupBy?
Zignorowanie podstawowego kodu SQL, nad którym pracuje grupa, gdy jest prezentowane samej operacji GROUP BY, złożoność jest po prostu O (n), ponieważ dane są skanowane w wierszu i agregowane w jednym przebiegu. Skala liniowo do n (rozmiar zbioru danych).
Po dodaniu grupy do złożonego zapytania równanie ulega zmianie, O (n) staje się górną granicą, którą grupa według dodaje do ogólnego równania; może być mniej, jeśli wewnętrzne zapytanie złożone jest takie, że w rozdzielczości podstawowego zapytania dane są już posortowane.
A ponieważ nie ma indeksu, kiedy dane są posortowane, już wydałeś O (N log N), sortując je. (nitpick: skaluje się liniowo do n, tj. do rozmiaru zbioru danych, a nie do rozmiaru n) –
@Martinho - Naprawiłem błąd składni angielskiej. – RichardTheKiwi
Przepraszam, ale to jest złe. Podczas iteracji przez zbiór danych musisz zdecydować, którą grupę chcesz umieścić w danym wierszu/obiekcie. Nie widzę, jak można dokonać selekcji grupowej w stałym czasie. –
O Linq, Chyba chcesz wiedzieć o złożoności Linq-to-object (Enumerable.GroupBy).
Sprawdzając implementację za pomocą programu ILSpy, wydaje mi się, że jest to O (n). (.Net Framework 4 series.)
Wylicza kolekcję źródłową jeden raz. Dla każdego elementu oblicza swój klucz grupujący. Następnie sprawdza, czy ma już klucz w mapowaniu hashtable na listy elementów, dodając klucz do tablicy, jeśli jej nie ma. Następnie dodaje element do odpowiedniej listy wpisów w hashtable.
Należy pamiętać, że GroupBy w SQL i LINQ to dwie bardzo różne operacje. –