6
인덱싱되지 않은 데이터 세트에 대한 GroupBy 조작의 점근 복잡성 (big O)에 관심이 있습니다. 가장 잘 알려진 알고리즘의 복잡성과 SQL 서버와 LINQ가 사용하는 알고리즘의 복잡성은 무엇입니까?GroupBy 작동의 점근 적 복잡성은 무엇입니까?
A
답변
3
GROUP BY 작업 자체에 표시 될 때 그룹 별 작업을 수행하는 기본 SQL을 무시하면 데이터가 행당 스캔되어 한 번에 집계되므로 복잡성은 O (n)입니다. 선형 적으로 n (데이터 세트의 크기)으로 확장됩니다.
그룹 쿼리를 복잡한 쿼리에 추가하면 O (n)은 그룹 이 전체 수식에을 더하는 상한이됩니다. 내부 쿼리가 기본 쿼리의 해결에서 데이터가 이미 정렬 된 경우와 같이 더 작을 수 있습니다.
+1
인덱스가 없기 때문에 데이터를 정렬 할 때 이미 O (N 로그 N)을 사용하여 정렬했습니다. (nitpick : n에 선형 적으로 비례하여 n의 크기가 아닌 데이터 집합의 크기로 조정됩니다.) –
+0
@Martinho - 영어 구문 오류가 수정되었습니다. – RichardTheKiwi
+0
죄송하지만이 것은 잘못되었습니다. 데이터 집합을 반복 할 때 주어진 행/개체에 넣을 그룹을 결정해야합니다. 나는 그룹 선택이 일정한 시간에 어떻게 이루어질 수 있는지를 볼 수 없다. –
0
Linq에 관해서는 Linq-to-object 그룹에 대해 복잡성 (Enumerable.GroupBy)을 알고 싶습니다.
ILSpy를 사용하여 구현을 확인하면 O (n) 인 것처럼 보입니다. (.Net Framework 4 시리즈)
소스 컬렉션을 한 번 나열합니다. 각 요소에 대해 그룹화 키를 계산합니다. 다음에, 키가 벌써 요소리스트에의 해시 테이블에 매핑되어 있는지 어떤지를 확인해, 해시 테이블에 키가없는 경우는 거기에 추가합니다. 다음에, 해시 테이블의 대응하는 엔트리리스트에 요소를 추가합니다.
SQL 및 LINQ의 GroupBy는 매우 다른 두 가지 작업입니다. –