발생 횟수를 계산하는 가장 효율적인 방법은 무엇입니까?

Question

저는 성능이 중요한 코드에서 엔트로피와 상호 정보를 엄청나게 계산하려고합니다. 중간 단계로서 각 값의 발생 횟수를 계산해야합니다. 예를 들어 : 물론

uint[] myArray = [1,1,2,1,4,5,2]; 
uint[] occurrences = countOccurrences(myArray); 
// Occurrences == [3, 2, 1, 1] or some permutation of that. 
// 3 occurrences of 1, 2 occurrences of 2, one each of 4 and 5. 

확실한 방법은이 중 하나를 연관 배열을 사용하거나 빠른 정렬과 같은 "표준"정렬 알고리즘을 사용하여 입력 배열을 정렬하여있다 할 수 있습니다. 바이트와 ​​같은 작은 정수의 경우 코드는 현재 보통의 오래된 배열을 사용하는 데 특화되어 있습니다.

해시 테이블보다 효율적으로 수행 할 수있는 똑똑한 알고리즘이 있습니까? 예를 들어 삽입에 비해 업데이트를 선호하는 연관 배열 구현이나 데이터가있을 때 빛나는 정렬 알고리즘과 같은 "표준"정렬 알고리즘이 제공합니다. 많은 관계?

주 : 희소가 아닌 정수는 가능한 데이터 유형의 한 예일뿐입니다. 여기에 합리적으로 일반적인 솔루션을 구현하는 찾고 있어요 비록 정수 및 structs 정수 만 포함 된 일반적인 경우, 나는 매우 효율적인 경우 이러한 특정 솔루션에 관심이있을 거라고.

Answer 1

데이터에 대해 자세히 알려주십시오.

• 몇 개의 아이템이 있습니까?
• 전체 항목에 대한 고유 항목의 예상 비율은 얼마입니까?
• 정수의 실제 값 분포 란 무엇입니까? 그들은 보통 간단한 계산 배열을 사용할만큼 충분히 작습니까? 아니면 합리적으로 좁은 그룹으로 묶여 있습니까? 기타

어쨌든 나는 다음과 같은 생각을 제안합니다 : 중복을 계산하기 위해 수정 된 mergesort.

즉 숫자가 아닌 쌍 (숫자, 빈도)으로 작업합니다 (예 : 쌍으로 된 배열 대신 두 개의 배열 등).

[(x1,1), (x2,1), ...]로 시작하여 평소처럼 mergesort를 수행하지만 동일한 값으로 시작하는 두 목록을 병합하면 값이 그들의 출현의 합계와 출력 목록. 귀하의 예제에서 : 원래보다 훨씬 작은 선두로부터 쌍, 그러나 합계 : 이것은 배열의 초기 감소 할 몇 가지 교묘 한 트릭을 사용하여 크게 개선 될 수

[1:1,1:1,2:1,1:1,4:1,5:1,2:1] 
Split into [1:1, 1:1, 2:1] and [1:1, 4:1, 5:1, 2:1] 
Recursively process them; you get [1:2, 2:1] and [1:1, 2:1, 4:1, 5:1] 
Merge them: (first/second/output) 
[1:2, 2:1]/[1:1, 2:1, 4:1, 5:1]/[] - we add up 1:2 and 1:1 and get 1:3 
[2:1]/[2:1, 4:1, 5:1]/[1:3] - we add up 2:1 and 2:1 and get 2:2 
[]/[4:1, 5:1]/[1:3, 2:2] 
[1:3, 2:2, 4:1, 5:1] 

(값의 배열을 얻을 각 'value'에 대한 'occurence'는 원래 배열에서 'value'의 발생 횟수와 같습니다). 예를 들어 값이 256 또는 65536을 넘지 않는 연속 블록으로 배열을 분할하고 작은 배열을 사용하여 각 블록 내부에서 발생을 계산합니다. 사실이 트릭은 나중의 병합 단계에서도 적용될 수 있습니다.

Answer 2

예제에서와 같이 정수 배열을 사용하면 가장 효과적인 방법은 int의 배열을 사용하고 값을 사용하여 색인을 생성하는 것입니다 (이미 수행 한 것처럼 보임).

할 수 없다면 해시 맵보다 더 좋은 대안을 생각할 수 없습니다. 빠른 해싱 알고리즘 만 있으면됩니다. 모든 데이터를 사용하려는 경우 O (n) 성능보다 향상시킬 수 없습니다. 보유하고있는 데이터의 일부만 사용하는 옵션입니까?

(정렬 및 계산하여 해시 맵 기반 솔루션 (N O를())를 사용하여보다 점근 느린 (O는 (N * 로그 (N))) 인 것에주의).

Answer 3

해싱 다른 같이 일반적으로 더 확장 할 대답은 나타냅니다. 그러나 많은 배포판 (실제 배열의 경우, 전체 배열을 어떻게 결합했는지에 따라 서브 어레이가 자주 정렬되는 경우가 많음)에 대해 timsort은 종종 "선입관 적으로 우수"합니다 (O (N)에 가깝습니다). O (N log N)) - 합리적으로 가까운 미래의 데이터에서 Java의 표준/기본 정렬 알고리즘이 될 것입니다 (Python에서 표준 정렬 알고리즘으로 사용되어 왔습니다).

실제로 발생하는 샘플을 선택할 수있는 명백한 위험으로 인해 발생할 것으로 예상되는 실제 작업 부하를 나타내는 사례를 벤치 마크하는 경우를 제외하고는 이러한 문제를 해결할 수있는 좋은 방법이 없습니다. 편향된/비 대표성을 지녀야합니다. 컨트롤 외부의 많은 외부 사용자가 사용할 라이브러리를 구축하려는 경우 작은 위험이 아닙니다.