1. 버킷 분류 소개
버킷 정렬은 카운트 기반 분류 알고리즘입니다. 작동 원리는 데이터를 제한된 수의 버킷으로 나눈 다음 각 버킷을 별도로 정렬하는 것입니다 (다른 정렬 알고리즘을 사용하거나 반복되는 방식으로 계속 정렬 할 수 있습니다). 정렬 할 데이터의 값이 균등하게 분포되면 버킷 분류 시간 복잡성은 θ (n)입니다. 버킷 분류는 빠른 분류와 다르며 비교 분류가 아니며 시간 복잡성 O (NLOGN)의 하한에 영향을받지 않습니다.
버킷 분류는 다음 4 단계에서 수행됩니다.
(1) 고정 된 수의 빈 버킷을 설정합니다.
(2) 데이터를 해당 버킷에 넣습니다.
(3) 비어있는 버킷에 데이터를 정렬하십시오.
(4) 비어 있지 않은 버킷의 데이터를 스플릿하여 결과를 얻습니다.
버킷 분류는 주로 소규모 정수 데이터에 적합하며 독립적이고 균등하게 배포됩니다. 계산할 수있는 데이터의 양은 크며 선형 예상 시간을 충족합니다.
2. 버킷 분류 알고리즘 데모
예를 들어, 이제 데이터 세트가 있습니다 [7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101]. 작은 것에서 큰 것으로 정렬하는 방법은 무엇입니까?
작동 단계 :
(1) 버킷 수를 5 개의 빈 버킷으로 설정하고 최대 값 110과 최소값 7을 찾으십시오. 각 버킷의 범위는 20.8 = (110-7+1)/5입니다.
(2) 원래 데이터를 가로 지르고 연결된 목록 구조와 함께 해당 버킷에 넣으십시오. 숫자 7, 버킷 인덱스 값은 0이고 계산 공식은 바닥 (7 7) / 20.8), 숫자 36, 버킷 인덱스 값은 1, 계산 공식 바닥 ((36 7) / 20.8)입니다.
(3) 두 번째로 동일한 인덱스로 버킷에 데이터를 삽입 할 때, 기존 숫자의 크기와 버킷에 새로 삽입 된 숫자를 결정하고 왼쪽에서 오른쪽으로, 작은 것부터 순서대로 삽입하십시오. 예를 들어, 인덱스 2가있는 버킷이 삽입되면 63을 삽입하면 이미 4 숫자 56, 59, 60 및 65가 있고 63은 65의 왼쪽에 삽입됩니다.
(4) 비어 있지 않은 버킷을 병합하고 왼쪽에서 오른쪽으로 순서대로 0, 1, 2, 3 및 4 버킷을 병합합니다.
(5) 버킷 정렬의 구조를 얻으십시오
3. Nodejs 프로그램 구현
버킷 분류와 같은 성숙한 알고리즘을 구현하는 것은 어렵지 않습니다. 위의 아이디어에 따르면, 나는 그것들을 구현하기위한 간단한 프로그램을 썼습니다. 가장 귀찮은 부분은 JavaScript를 사용하여 링크 된 목록을 조작하는 것입니다.
실제 코드는 다음과 같습니다.
'사용 엄격한';//////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////4 //////////////////////////////////////////////////////////////////4 //////////////////////////////////////////////////////////////////4 //////////////////////////////////////////////////////////////////4 //////////////////////////////////////////////////////////////////4 //////////////////////////////////////////////////////////////////4 /////////////////////////////////////////////////////////// 정렬 ([1,4,1,5,3,3,3,3,2,5,2,8,9,2,1], 5) * 정렬 ([1,4,4,4,4,4,4,1,3,3,3,2,2,8,9,2,1], 5,0,5) */Exports.sort = 함수 (ARR, COUNT) {IF (rength = return) []; count = count || (count> 1? count : 10); // 최대 및 최소값 판단 var min = arr [0], max = arr [0]; for (var i = 1; i <arr.length; i ++) {min = min <arr [i]? 최소 : ARR [i]; max = max> arr [i]? MAX : ARR [i]; } var delta = (max -min + 1) / count; // console.log (min+","+max+","+delta); // 버킷 var 버킷 초기화 = []; // 버킷에 대한 저장 데이터 (var i = 0; i <arr.length; i ++) {var idx = math.floor ((arr [i] -min) /delta); // 버킷 인덱스 if (버킷 [idx]) {// 비어 있지 않은 버킷 var 버킷 = 버킷 [idx]; var insert = false; // 플래그 스톤 l.retraversal (버킷, 함수 (항목, 완료) {if (arr [i] <= item.v) {// 작은 것, insert l.append (item, _val (arr [i])) if (! insert) {// 더 큰, l.append (bucet, _val (arr [i])); }} else {// 빈 버킷 var 버킷 = l.init (); l.append (Bucket, _val (arr [i])); 버킷 [idx] = 버킷; // 링크 목록 구현}} var result = []; for (var i = 0, j = 0; i <count; i ++) {l.retraversal (버킷 [i], function (item) {// console.log (i+":"+item.v); 결과 [j ++] = item.v;}); } return result;} // 링크 된 목록 저장소 개체 함수 _val (v) {return {v : v}}프로그램 실행 :
var algo = require ( './ index.js'); var data = [7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101]; console.log (data); console.log (algo.bucketsort.sort (데이터, 5)); console.log (algo.bucketsort.sort (data, 10)); // 10 버킷
산출:
7, 22, 22, 33, 36, 42, 42, 56, 67, 67, 77, 83, 84, 94, 101, 110] [7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 83, 84, 94, 101, 110] [7, 22, 33, 36, 42, 42, 56 63, 65, 67, 77, 83, 84, 94, 101, 110] [7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110] [7, 22, 33, 36, 42, 42, 56, 59, 60, 65, 67, 77 84, 94, 101, 110] [7, 22, 33, 36, 42, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110] [7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 94, 101, 84, 101, 110
설명해야 할 것은 다음과 같습니다.
(1) 버킷의 정렬은 프로그램에 설명 된 바와 같이 삽입 프로세스 중에 구현 될 수있다. 또는 정렬없이 삽입 한 다음 병합 프로세스 중에 정렬 할 수 있으며 빠른 정렬을 호출 할 수 있습니다.
(2) 링크 된 목록. 노드의 기본 API에는 링크 된 목록의 구현이 있습니다. 직접 사용하지는 않았지만 링크리스트 패키지를 통해 호출했습니다.
4. 사례 : 대학 입학 시험 점수에 대한 버킷 분류 통계
버킷 분류의 가장 유명한 응용 시나리오 중 하나는 대학 입학 시험의 점수를 계산하는 것입니다. 1 년 동안 National College Entrance 시험 후보자의 수는 9 백만이며 점수는 표준이며 최소 200 명, 최대 900입니다. 소수점은 없습니다. 이 9 백만 개의 숫자가 정렬되면 어떻게해야합니까?
알고리즘 분석 :
(1) 비교 기반 분류, 빠른 분류를 사용하는 경우 평균 시간 복잡성은 O (nogn) = O (9000000*log9000000) = 144114616 = 144 million 비교입니다.
(2) 카운트 기반 분류, 버킷 분류 및 평균 복잡성을 사용하는 경우 선형 복잡성을 제어 할 수 있습니다. 200 분에서 900 분까지 1 개의 버킷, O (n) = O (90000000) 700 개의 버킷을 만들 때 900W 데이터를 한 번 스캔하는 것과 같습니다.
빠른 정렬 및 버킷 분류를 한 번에 비교하는 프로그램을 실행합니다.
// [200,900] 폐쇄 간격 var data = algo.data.randomdata (1000*1000,200,900)에서 100W 데이터를 생성합니다. var s1 = new date (). gettime (); algo.quicksort.sort (data); // Quick Sort var S2 = new Date (); getGo.bucketsort.sort (700); s3 = new date (). gettime (); console.log ( "QuickSort Time : %SMS", S2-S1); console.log ( "버킷 시간 : %sms", s3-s2);
산출:
QuickSort 시간 : 14768msbucket 시간 : 1089ms
따라서 대학 입학 시험 점수의 경우 버킷 분류가 더 적합합니다! 적절한 시나리오에서 적절한 알고리즘을 사용하면 하드웨어 이외의 프로그램에 대한 성능 향상이 가능합니다.
5. 버킷 분류 비용 분석
하지만...
버킷 분류는 함수의 매핑 관계를 사용하여 거의 모든 비교 작업을 줄입니다. 실제로, 버킷 분류의 F (k) 값의 계산은 빠른 순서의 부서와 동일하며 많은 양의 데이터를 기본적으로 주문한 데이터 블록 (버킷)으로 나누었습니다. 그런 다음 버킷에서 소량의 데이터를 고급 비교와 정렬하면됩니다.
버킷 정렬 N 키워드의 시간 복잡성은 두 부분으로 나뉩니다.
(1) 각 키워드의 버킷 매핑 함수를 계산하기위한 루핑,이 시간 복잡성은 O (n)입니다.
(2) 고급 비교 정렬 알고리즘을 사용하여 각 버킷의 모든 데이터를 ∑o (ni*logni)의 시간 복잡성으로 정렬하십시오. 여기서 Ni는 I-th 버킷의 데이터 금액입니다.
분명히, 파트 (2)는 버킷 분류의 성능을 결정하는 요인입니다. 버킷의 데이터 양을 최소화하는 것은 효율을 향상시키는 유일한 방법입니다 (비교 분류를 기반으로 한 평균 시간 복잡성은 O (n*logn)에만 도달 할 수 있기 때문에). 따라서 다음 두 가지 점을 수행하기 위해 최선을 다해야합니다.
(1) 매핑 함수 F (k)는 N 데이터를 M 버킷에 고르게 할당하여 각 버킷에 [N/M] 데이터 볼륨을 갖도록 할 수 있습니다.
(2) 배럴 수를 늘리십시오. 극단적 인 경우, 각 버킷은 하나의 데이터 만 얻을 수 있으며,이 데이터는 버킷에서 데이터의 "비교"분류 작업을 완전히 피할 수 있습니다. 물론, 이것을하기는 쉽지 않습니다. 데이터의 양이 크면 F (k) 함수는 버킷 컬렉션의 수를 크게 만들고 우주 폐기물이 심각합니다. 이것은 시간과 공간 비용 사이의 상충 관계입니다.
N 데이터를 정렬하고 M 버킷을 사용하려면 각 버킷 [N/M] 데이터의 평균 버킷 분류 시간 복잡성은 다음과 같습니다.
o (n)+o (m*(n/m)*log (n/m)) = o (n+n*(logn-logm)) = o (n+n*logn-n*logm)
n = m 일 때, 즉, 한계에 따라 버킷 당 하나의 데이터 만있는 경우. 버킷 분류의 최상의 효율은 O (n)에 도달 할 수 있습니다.
6. 요약
버킷 분류의 평균 시간 복잡성은 선형 O (n+C)이며, 여기서 c = n*(logn-logm). 배럴 M의 수가 동일한 n에 비해 더 큰 경우, 효율이 높고 가장 좋은 시간 복잡성은 O (n)에 도달합니다. 물론, 버킷 분류의 공간 복잡성은 O (n+m)입니다. 입력 데이터가 매우 크고 버킷 수가 매우 크면 공간 비용이 의심 할 여지없이 비쌉니다. 또한 버킷 정렬은 안정적입니다.
실제로, 나는 또 다른 느낌이 있습니다 : 검색 알고리즘 중에서 비교 기반 검색 알고리즘의 가장 좋은 시간 복잡성은 O (logn)입니다. 예를 들어, 반 마감 검색, 균형 이진 나무, 빨간색 및 검은 나무 등. 그러나 해시 테이블에는 O (C) 선형 레벨 검색 효율이 있습니다 (검색 효율은 충돌이없는 경우 O (1)에 도달합니다). 해시 테이블의 생각과 버킷 분류가 같은 노래입니까?