C#에서 배열의 도수 분포를 계산하는 가장 빠른 방법은 무엇입니까?

Question

나는 그 계산을 위해 가장 좋은 방법이 무엇인지 궁금 할뿐입니다. 입력 배열의 값과 경계 배열이 있다고 가정합니다. 경계 배열의 각 세그먼트에 대한 빈도 분포를 계산/버킷 화하려고합니다.

버켓 검색을 사용하는 것이 좋습니까?

사실 나는 그 질문에 Calculating frequency distribution of a collection with .Net/C#

을 발견하지만 각 버킷의 크기가 내 상황에서 다를 수 있습니다 원인이 그 목적 버킷을 사용하는 방법을 이해하지 않습니다.

편집 : 내부/외부 루프 솔루션을 가지고 있지만, 내가 입력을 해시 할 필요가 제대로 이해하면 아직도 내가,이 경우 O (n)의 퍼포먼스를 얻기 위해 사전에 내부 루프를 제거하려는 모든 토론 후 값을 버킷 인덱스로 변환합니다. 그래서 우리는 O (1) 복잡성을 지닌 일종의 해시 함수가 필요합니까? 어떤 아이디어로 그것을 할 수 있습니까?

Answer 1

버킷 정렬은 이미 O (n^2) 최악의 경우이므로 여기에서 간단한 내부/외부 루프를 수행합니다. 버킷 배열은 입력 배열보다 반드시 짧아야하므로 내부 루프에 보관하십시오. 사용자 정의 버킷 크기를 사용하기 때문에 실제로 내부 루프를 제거 할 수있는 수학적인 트릭이 없습니다.

int[] freq = new int[buckets.length - 1]; 
foreach(int d in input) 
{ 
    for(int i = 0; i < buckets.length - 1; i++) 
    { 
     if(d >= buckets[i] && d < buckets[i+1]) 
     { 
      freq[i]++; 
      break; 
     } 
    } 
} 

최악의 경우이지만 코드 단순성을 이길 수는 없습니다. 나는 그것이 진짜 문제가 될 때까지 최적화에 대해 걱정하지 않을 것이다. 더 큰 버킷 배열을 가지고 있다면, 어떤 종류의 바이너리 검색을 사용할 수 있습니다. 그러나 빈도 분포는 일반적으로 <100 요소이므로 실제 성능에 많은 이점이 있을지는 의문입니다.

Answer 2

사용자의 입력 배열은 (그 패턴) 실제 데이터를 나타내며 경계의 배열은 또 다시 반복하는 내부 루프에서 다음과 같은 방법을 고려할 수 많은 경우 : 모든 종류의

• 먼저 귀하의 입력 배열. 실제 데이터로 작업하는 경우 나는 이것을 Timsort - Wiki으로 생각하는 것이 좋습니다. 은 실제 데이터에서 볼 수있는 패턴에 대해 매우 우수한 성능 보장을 제공합니다. 정렬 된 배열을

• 트래버스와 경계의 배열에서 첫 번째 값과 비교 :

  • 입력 배열의 값이 경계 후 ​​작은 경우
    -이 경계에 대한 증분 주파수 카운터
  • 경우 값 입력 배열이 더 큰 경우 경계 - 경계 배열의 다음 값으로 이동하고 새 경계에 대해 카운터를 증가시킵니다. 그것은 다음과 같이 할 수있는 코드에서

는 :

Timsort(myArray); 
int boundPos; 
boundaries = GetBoundaries(); //assume the boundaries is a Dictionary<int,int>() 

for (int i = 0; i<myArray.Lenght; i++) { 
    if (myArray[i]<boundaries[boundPos]) { 
    boundaries[boubdPos]++; 
    } 
    else { 
    boundPos++; 
    boundaries[boubdPos]++; 
    } 
}