1. Introdução à classificação do balde
O Sorting Bucket é um algoritmo de classificação baseado em contagem. O princípio de trabalho é dividir os dados em um número limitado de baldes e, em seguida, cada balde é classificado separadamente (é possível usar outros algoritmos de classificação ou continuar a classificar de maneira recorrente). Quando os valores nos dados a serem classificados são distribuídos uniformemente, a complexidade do tempo de classificação do balde é θ (n). A classificação do balde é diferente da classificação rápida, não é uma classificação de comparação e não é afetada pelo limite inferior da complexidade do tempo O (nLogn).
A classificação do balde é realizada nas 4 etapas seguintes:
(1) Defina um número fixo de baldes vazios.
(2) Coloque os dados no balde correspondente.
(3) Classifique os dados em cada balde não vazio.
(4) Consiga os dados do balde não vazio para obter o resultado.
A classificação do balde é adequada para dados inteiros de pequeno alcance e é distribuída de forma independente e uniforme. A quantidade de dados que podem ser calculados é grande e atende ao tempo esperado linear.
2. Demonstração do algoritmo de classificação do balde
Por exemplo, agora existe um conjunto de dados [7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101]. Como classificá -lo de pequeno a grande?
Etapas de operação:
(1) Defina o número de baldes para 5 baldes vazios, encontre o valor máximo de 110 e o valor mínimo de 7, e o intervalo de cada balde é 20,8 = (110-7+1)/5.
(2) Travesse os dados originais, coloque -os no balde correspondente com uma estrutura de lista vinculada. O número 7, o valor do índice da caçamba é 0, a fórmula de cálculo é o piso ((7 7) / 20.8), o número 36, o valor do índice da caçamba é 1, o piso da fórmula de cálculo ((36 7) / 20.8).
(3) Ao inserir dados no balde com o mesmo índice na segunda vez, determine o tamanho dos números existentes e os números recém -inseridos no balde e insira -os em ordem da esquerda para a direita, de pequena a grande. Por exemplo: quando o balde com o índice 2 é inserido, ao inserir 63, já existem 4 números 56, 59, 60 e 65 no balde e, em seguida, o número 63 é inserido à esquerda de 65.
(4) Mesclar baldes não vazios, mesclando 0, 1, 2, 3 e 4 baldes em ordem da esquerda para a direita.
(5) Obtenha a estrutura do tipo de balde
3. Implementação do programa NodeJS
Não é difícil implementar algoritmos maduros, como a classificação do balde. De acordo com as idéias acima, escrevi um programa simples para implementá -las. Sinto que a parte mais problemática está usando o JavaScript para manipular a lista vinculada.
O código real é o seguinte:
'usar estrito';//////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////// classificar ([1,4,1,5,3,2,3,3,2,5,2,2,9,2,1], 5) * classificar ([1,4,1,5,2,2,3,3,2,5,2,2,2,9,2,1], 5,0) */exportar.sort = função (ARR, RUNT) {se contagem = contagem || (contagem> 1? contagem: 10); // Juiz valores máximos e mínimos var min = arr [0], max = arr [0]; for (var i = 1; i <arr.length; i ++) {min = min <arr [i]? Min: arr [i]; max = max> arr [i]? Max: arr [i]; } var delta = (max - min + 1) / count; // console.log (min+","+max+","+delta); // Inicialize o balde var buckets = []; // Dados de armazenamento para balde para (var i = 0; i <arr.length; i ++) {var idx = math.floor ((arr [i] - min) /delta); // Índice de balde if (baldes [idx]) {// bucket não vazio var bucket = buckets [idx]; var inser = false; // insira a pedra da bandeira l.retaversal (balde, função (item, feito) {if (arr [i] <= item.v) {// menor do que, insira l.append (item, _val (arr [i])); insert = true; done (); // exit traversal}}); if (! insert) {// maior que, insira l.append (bucket, _val (arr [i])); }} else {// Bucket vazio var bucket = l.init (); L.Append (Bucket, _val (arr [i])); baldes [idx] = bucket; // implementação da lista de links}} var resultado = []; for (var i = 0, j = 0; i <contagem; i ++) {l.retaversal (baldes [i], function (item) {// console.log (i+":"+item.v); resultado [j ++] = item.v;}); } return resultado;} // Função de objeto de armazenamento da lista vinculada _val (v) {return {v: v}}Execute o programa:
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(data,5));//5 buckets console.log (algo.bucketsort.sort (dados, 10)); // 10 baldesSaída:
7, 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, 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, 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, 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
O que precisa ser explicado é:
(1) classificar no balde pode ser implementado durante o processo de inserção, conforme descrito no programa; Ou pode ser inserido sem classificar e depois classificado durante o processo de mesclagem, e a classificação rápida pode ser chamada.
(2) Lista vinculada. Na API subjacente do nó, há uma implementação da lista vinculada. Não o usei diretamente, mas o chamei através do pacote Linklist: https://github.com/nodejs/node-v0.x-archive/blob/master/lib/_linklist.js
4.
Um dos cenários de aplicação mais famosos para a classificação do balde é contar as pontuações do exame de admissão da faculdade. O número de candidatos ao exame de admissão na faculdade nacional em um ano é de 9 milhões e as pontuações são padrão, com um mínimo de 200 e no máximo 900. Não há decimal. Se esses 9 milhões de números forem classificados, o que devemos fazer?
Análise de algoritmo:
(1) Se você usar classificação baseada em comparação, classificação rápida, a complexidade do tempo médio é O (nLogn) = O (9000000*log9000000) = 144114616 = 144 milhões de comparações.
(2) Se você usar classificação, classificação de balde e complexidade média baseada em contagem, poderá controlar a complexidade linear. Ao criar 700 baldes, um balde de 200 minutos a 900 minutos, O (n) = O (90000000), é equivalente a digitalizar dados de 900W uma vez.
Executamos um programa para comparar a classificação rápida e a classificação do balde de uma só vez.
// Crie dados de 100W em [200.900] intervalo fechado var dados = algo.data.randomdata (1000*1000.200.900); var s1 = new Date (). Gettime (); algo.QickSort.Sort (dados); // stay var s2 = new date (). baldes var s3 = new date (). gettime (); console.log ("tempo do chapicador: %sms", s2-s1); console.log ("tempo do balde: %sms", s3-s2);Saída:
Horário do Quicksort: 14768msbucket Tempo: 1089ms
Portanto, para o caso de pontuação no exame de entrada da faculdade, a classificação do balde é mais adequada! Nosso uso de algoritmos apropriados em cenários adequados trará melhorias de desempenho para o programa além do hardware.
5. Análise de custo de classificação do balde
MAS...
A classificação do balde utiliza a relação de mapeamento das funções, reduzindo quase todo o trabalho de comparação. De fato, o cálculo do valor f (k) da classificação do balde é equivalente à divisão na ordem rápida e dividiu uma grande quantidade de dados em blocos de dados basicamente ordenados (baldes). Então você só precisa fazer comparações avançadas e classificação de uma pequena quantidade de dados no balde.
A complexidade do tempo da classificação do balde n -chave é dividida em duas partes:
(1) Looping para calcular a função de mapeamento do balde de cada palavra -chave, e esse tempo a complexidade é O (n).
(2) Use o algoritmo de classificação avançado de comparação para classificar todos os dados em cada balde, com uma complexidade de tempo de ∑o (ni*logni). Onde Ni é o valor dos dados do I-Th Bucket.
Obviamente, a parte (2) é o determinante do desempenho da classificação do balde. Minimizar a quantidade de dados no balde é a única maneira de melhorar a eficiência (porque a melhor complexidade média de tempo com base na classificação de comparação pode atingir apenas o (n*logn)). Portanto, precisamos tentar o nosso melhor para fazer os dois pontos a seguir:
(1) A função de mapeamento F (k) pode alocar dados N para M Buckets uniformemente, para que cada balde tenha [N/M] volumes de dados.
(2) Tente aumentar o número de barris. No caso extremo, cada balde pode obter apenas um dados, o que evita completamente a operação de classificação "compare" dos dados no balde. Claro, não é fácil fazer isso. Quando a quantidade de dados é enorme, a função f (k) tornará o número de coleções de baldes enormes e o desperdício espacial é grave. Esta é uma troca entre o custo do tempo e o espaço.
Para N dados a serem classificados e M baldes, a complexidade média do tempo de classificação do balde de cada bucket [n/m] é:
O (n)+o (m*(n/m)*log (n/m)) = O (n+n*(logn-logm)) = O (n+n*logn-n*logm)
Quando n = m, ou seja, quando há apenas um dados por balde sob o limite. A melhor eficiência da classificação do balde pode atingir o (n).
6. Resumo
A complexidade média do tempo da classificação do balde é linear O (n+c), onde C = n*(logn-logm). Se o número de barris m for maior em relação ao mesmo n, quanto maior sua eficiência e a melhor complexidade do tempo atingirá O (n). Obviamente, a complexidade espacial da classificação do balde é O (n+m). Se os dados de entrada forem muito grandes e o número de baldes for muito grande, o custo do espaço será sem dúvida caro. Além disso, o tipo de balde é estável.
Na verdade, tenho outro sentimento: entre os algoritmos de pesquisa, a melhor complexidade do tempo do algoritmo de pesquisa baseada em comparação é O (logn). Por exemplo, pesquisa semi-acabamento, árvores binárias equilibradas, árvores vermelhas e pretas, etc. No entanto, a tabela de hash possui eficiência de pesquisa de nível linear O (c) (a eficiência da pesquisa atinge o (1) em caso de nenhum conflito). Vamos dar uma boa olhada: os pensamentos e a classificação do balde das tabelas de hash são a mesma música?