"GROUP BY"를 수학적으로 수행하는 방법은 무엇입니까?

Question

키 값 쌍의 데이터 구조가 있고 "GROUP BY"값을 구현하고 싶습니다. 키와 값은 모두 문자열입니다.

그래서 내가 한 일은 내가 모든 값 (문자열) 고유의 "소수"를 준이었다. 그런 다음 모든 키에 대해 특정 키에있는 다른 값과 관련된 모든 소수의 곱셈을 저장했습니다. "Anirudh"키에 "x", "y", "z"값이 있으면 M (Key) = 2 * 3 * 5 = 30으로 저장합니다. 나중에 특정 값 "x"(말하기)로 그룹을 만들고 싶으면 모든 키를 반복하고 "x"와 연관된 소수로 M (키)을 나눕니다. 그런 다음 나머지가 0인지 확인하고 0 인 경우 특정 "키"는 값 "x"에 대한 그룹의 일부입니다.

이것이 가장 이상한 방법이라고 생각합니다. 어떤 사람들은 키 값 쌍 (값으로 정렬)을 정렬합니다. 이미 "값"으로 그룹화 된 다른 테이블 (해시 테이블)을 만들 수도있었습니다. 그래서 저는 제보다 나은 방법을 알고 싶습니다 (많은 사람들이 있어야합니다). 내 방법에서는 특정 키에 대한 고유 값의 수가 증가함에 따라 소수의 곱도 증가합니다 (즉, 기하 급수적으로 증가합니다). (하지만 훨씬 더 많은 계산) 비트 벡터 또는 2. 먼저 값의 제곱의 합보다 여기에 요구되는 내용 진짜 생각이 없다, 그러나 이것은 비슷한 소리가 나는 경우에

Answer 1

귀하의 방법은 항상 그룹 구성원을 찾기 위해 O (N)를 수행합니다. 또한 많은 수의 소수를 잠재적으로 곱하여 키를 구성하기 때문에 많은 요소가있는 경우 일반 정수 경계 (32, 64 비트)가 오버플로 될 위험이 있습니다.

당신은보다 효율적이고 확실하게 예측이 방법 다음 그룹 구성원을 추적하는 비트 마스크를 사용할 수 있습니다. 16 개의 그룹이있는 경우 비트 마스크를 사용하여 16 비트 단락으로 표현할 수 있습니다. 여러분이 제안한 것과 같이 소수를 사용하면, 32589158477190044730 (처음 16 개의 소수를 곱한 값)을 유지하기에 충분한 비트가있는 정수가 필요합니다. 이는 65 비트가 필요합니다. 그룹핑

다른 방법은 첫 번째 반복에 대한 O (N)이 (결국, 각 요소는 그룹 멤버에 대한 적어도 한번 시험되어야 함)이다. 그러나 동일한 그룹 검사를 반복하는 경향이 있다면 이후 그룹 구성원 테스트가 O (1)이기 때문에 참조하는 다른 방법 (예 : 대상 그룹 당 목록 또는 해시 테이블 유지)이 훨씬 효율적입니다. 그룹 구성원 (일부 그룹을 반복), (당신이 당신의 질문에 제안하는 사람 포함) 그룹을 저장하는 솔루션에 대한 여러 쿼리가있는 경우

가

• 더 나은 수행합니다

  그래서 직접 귀하의 질문에 대답하기 너의 방법보다. 등으로

  • 사용 구조 : 그룹 구성원에 대한 반복 쿼리가없는 경우
  • 는

  반복 쿼리가 가능성이 질문을 기반으로 보인다 감안할 때 그룹 구성원을 저장하는 어떤 이점이 없다 더 빠른 속도를 위해 메모리를 교환하려는 경우 그룹 ID를 키 입력하여 그룹 구성원을 저장합니다.

• 메모리를 줄이기 위해 속도를 바꾸려면 그룹 구성원을 저장하기 위해 적절하게 넓은 비트 배열을 사용하십시오.

Answer 2

는 "1", 두 번째는 "2"입니다 , 세 번째는 "4"입니다. "7"을 얻으면 "첫 번째"+ "두 번째"+ "세 번째"라는 것을 알 수 있습니다. 대상 그룹에 속하는 요소를 찾기 위해 컬렉션의 모든 요소를 ​​반복해야하기 때문에