알려진 통계 분포의 데이터 정렬 알고리즘?

알려진 통계 분포의 데이터 정렬 알고리즘?

---

정렬 할 데이터의 분포 (통계적 의미)에 대해 알고 있다면 해당 정보를 고려하면 정렬 알고리즘의 성능에 도움이 될 수 있습니다.

제 질문은 그런 종류의 정보를 고려한 정렬 알고리즘이 있습니까? 얼마나 좋은가요?

편집 : 명확히 할 예 : 데이터 분포가 가우시안 인 경우 데이터를 처리 할 때 즉석에서 평균과 평균을 추정 할 수 있습니다. 이렇게하면 각 숫자의 최종 위치를 추정하여 최종 위치에 가깝게 배치 할 수 있습니다.

편집 # 2 : 대답이이 문제를 논의하는 거친 페이지에 대한 위키 링크가 아니라는 점에 꽤 놀랐습니다. 이것은 매우 일반적인 경우가 아닙니까 (예를 들어 가우시안 경우)?

편집 # 3 :이 질문에 현상금을 추가하고 있습니다. 왜냐하면 추측이 아닌 출처를 통해 명확한 답변을 찾고 있기 때문입니다. "가우시안 분산 데이터의 경우 XYZ 알고리즘이 평균적으로 가장 빠릅니다. Smith et al. [1]에 의해 입증되었습니다." 그러나 추가 정보는 환영합니다.

참고 : 가장 많이 뽑은 답변에 현상금을 수여합니다. 현명하게 투표하십시오!

---

정렬중인 데이터에 알려진 분포가있는 경우 버킷 정렬 알고리즘을 사용합니다 . 분포의 속성을 기반으로 다양한 버킷의 크기 및 / 또는 위치를 계산하도록 추가 논리를 추가 할 수 있습니다 (예 : Gaussian의 경우 평균에서 떨어진 모든 버킷 (sigma / k), 여기서 시그마는 분포의 표준 편차입니다.)

알려진 분포를 갖고 이러한 방식으로 표준 버킷 정렬 알고리즘을 수정하면 히스토그램 정렬 알고리즘 또는 이와 유사한 알고리즘을 얻을 수 있습니다. 물론 이미 분포를 알고 있기 때문에 첫 번째 패스 (링크에 설명 됨)를 수행 할 필요가 없기 때문에 알고리즘이 히스토그램 정렬 알고리즘보다 계산적으로 더 빠릅니다.

편집 : 귀하의 질문에 대한 새로운 기준이 주어지면 (히스토그램 정렬에 관한 이전 답변은 존경받는 NIST에 연결되고 성능 정보가 포함되어 있지만) 다음은 병렬 처리에 관한 국제 회의의 피어 리뷰 저널 기사입니다.

확률 분포를 사용한 정렬을위한 적응 형 데이터 파티션

저자는이 알고리즘이 인기있는 Quick-Sort 알고리즘보다 더 나은 성능 (최대 30 % 더 좋음)을 가지고 있다고 주장합니다.

---

Self-Improving Algorithms 를 읽고 싶은 것처럼 들립니다 . 임의 입력 분포에 대해 궁극적으로 최적의 예상 실행 시간을 달성합니다 .

우리는 (i) 일련의 숫자 정렬 및 (ii) 평면 점 집합의 Delaunay 삼각 분할 계산이라는 두 가지 문제에 대해 이러한 자체 개선 알고리즘을 제공합니다. 두 알고리즘 모두 최적의 예상 제한 복잡성을 달성합니다. 알고리즘은 입력 분포에 대한 정보를 수집하는 훈련 단계로 시작하여 알고리즘이 최적화 된 구현에 정착하는 고정 체제가 뒤 따릅니다.

입력 분포가 대략 가우시안이라는 것을 이미 알고 있다면 공간 복잡성 측면에서 다른 접근 방식이 더 효율적일 수 있지만 예상 실행 시간 측면에서 이것은 다소 멋진 결과입니다.

---

데이터 소스 분포를 알면 좋은 해시 함수를 만들 수 있습니다. 분포를 잘 알고 있으면 해시 함수가 완벽한 해시 함수이거나 많은 입력 벡터에 대해 완벽에 가까운 것으로 입증 될 수 있습니다.

이러한 함수는 크기 n의 입력을 n 개의 빈으로 분할하여 가장 작은 항목이 첫 번째 빈에 매핑되고 가장 큰 항목이 마지막 빈에 매핑되도록합니다. 해시가 완벽 할 때 모든 항목을 저장소에 삽입하는 것만으로도 정렬을 수행 할 수 있습니다.

모든 항목을 해시 테이블에 삽입 한 다음 순서대로 추출하면 해시가 완벽 할 때 O (n)이됩니다 (해시 함수 계산 비용이 O (1)이고 밑줄 해시 데이터 구조 작업이 O (1)이라고 가정). ).

해시 테이블을 구현하기 위해 피보나치 힙 배열을 사용합니다.

해시 함수가 완벽하지는 않지만 (하지만 여전히 완벽에 가까운) 입력 벡터의 경우 O (nlogn)보다 훨씬 낫습니다. 그것이 완벽 할 때-그것은 O (n)이 될 것입니다. 평균 복잡도를 계산하는 방법을 잘 모르겠지만 강제하면 O (nloglogn)에 베팅합니다.

---

컴퓨터 정렬 알고리즘은 비교 기반 정렬과 비 비교 기반 정렬의 두 가지 범주로 분류 할 수 있습니다. 비교 기반 정렬의 경우 최상의 성능에서 정렬 시간은 Ω (nlogn)이고 최악의 성능에서는 정렬 시간이 O (n2)까지 올라갈 수 있습니다. 최근에는 데이터 분포 특성에 따른 고급 퀵 정렬과 같이 비교 기반 정렬 속도를 높이기 위해 개선 된 알고리즘이 제안되었습니다. 그러나 이러한 알고리즘의 평균 정렬 시간은 Ω (nlog2n)에 불과하며 최상의 경우에만 O (n)에 도달 할 수 있습니다. 비교 기반 정렬과 달리 개수 정렬, 버킷 정렬 및 기수 정렬과 같은 비 비교 기반 정렬은 주로 키 및 주소 계산에 의존합니다. 키 값이 1에서 m까지 유한 한 경우 비 비교 기반 정렬의 계산 복잡성은 O (m + n)입니다. 특히 m = O (n) 일 때 정렬 시간은 O (n)에 도달 할 수 있습니다. 그러나 m = n2, n3,…. 일 때는 선형 정렬 시간의 상한을 얻을 수 없습니다. 비 비교 기반 정렬 중에서 버킷 정렬은 유사한 키를 가진 레코드 그룹을 적절한 "버킷"에 배포 한 다음 다른 정렬 알고리즘이 각 버킷의 레코드에 적용됩니다. 버킷 정렬을 사용하면 레코드를 m 개의 버킷으로 분할하는 데 시간이 덜 걸리고 각 버킷에 몇 개의 레코드 만 포함되므로 "정리 정렬"알고리즘을 매우 빠르게 적용 할 수 있습니다. 따라서 버킷 정렬은 Ω (nlogn) 알고리즘에 비해 정렬 시간을 점근 적으로 절약 할 수 있습니다. 분명히 모든 레코드를 버킷에 균일하게 배포하는 방법은 버킷 정렬에서 중요한 역할을합니다. 따라서 필요한 것은 데이터 분포에 따라 해시 함수를 구성하는 방법으로, 각 레코드의 키를 기준으로 n 개의 레코드를 n 개의 버킷에 균일하게 배포하는 데 사용됩니다. 따라서 제안 된 버킷 정렬 알고리즘의 정렬 시간은 어떤 상황에서도 O (n)에 도달합니다.

이 문서를 확인하십시오 : http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5170434&tag=1

---

버킷 정렬은 O (1) 시간에서 각 포인트의 CDF를 계산할 수있는 한 선형 시간 정렬 알고리즘을 제공합니다.

다른 곳에서도 조회 할 수있는 알고리즘은 다음과 같습니다.

a = array(0, n - 1, [])          // create an empty list for each bucket
for x in input:
  a[floor(n * cdf(x))].append(x) // O(1) time for each x
input.clear()
for i in {0,...,n - 1}:
  // this sorting step costs O(|a[i]|^2) time for each bucket
  // but most buckets are small and the cost is O(1) per bucket in expectation
  insertion_sort(a[i])
  input.concatenate(a[i])

x와 y가 동일한 버킷에 속하도록 O (n) 쌍 (x, y)이 있고 삽입 정렬의 실행 시간이 정확히 O (n + #)이기 때문에 실행 시간은 O (n)입니다. 동일한 버킷의 쌍). 분석은 FKS 정적 완전 해싱 의 분석과 유사합니다 .

편집 : 분포를 모르지만 어떤 계열인지 알고 있다면 평균과 분산을 계산하여 가우스의 경우 O (n)의 분포를 추정 한 다음 동일한 알고리즘을 사용할 수 있습니다 (부수적으로 ,이 경우 cdf를 계산하는 것은 중요하지 않습니다).

---

빠른 정렬에서 해당 정보를 사용하여 피벗 값을 선택할 수 있습니다. 나는 그것이 알고리즘이 O (N ** 2) 최악의 복잡성에서 벗어나는 확률을 향상시킬 것이라고 생각한다.

---

사이클 정렬 이이 범주에 속 한다고 생각 합니다 . 각 요소가 끝날 정확한 위치를 알고있을 때 사용합니다.

Cyclesort에는 몇 가지 멋진 속성이 있습니다. 제한된 특정 유형의 데이터에 대해 선형 시간에 안정적이고 제자리 정렬을 수행 할 수 있으며 각 요소가 최대 한 번만 이동되도록 보장합니다.

참고URL : https://stackoverflow.com/questions/6166546/sorting-algorithms-for-data-of-known-statistical-distribution