1. Introducción a la clasificación de cubos
Bucket Sort es un algoritmo de clasificación basado en recuentos. El principio de trabajo es dividir los datos en un número limitado de cubos, y luego cada cubo se clasifica por separado (es posible usar otros algoritmos de clasificación o continuar clasificando de manera recurrente). Cuando los valores en los datos a ordenar se distribuyen uniformemente, la complejidad del tiempo de clasificación de cubos es θ (n). La clasificación de cubos es diferente de la clasificación rápida, no es una clasificación de comparación y no se ve afectada por el límite inferior de la complejidad del tiempo O (NLOGN).
La clasificación de cubos se lleva a cabo en los siguientes 4 pasos:
(1) Establezca un número fijo de cubos vacíos.
(2) Coloque los datos en el cubo correspondiente.
(3) Ordene los datos en cada cubo no vacío.
(4) empalme los datos del cubo no vacío para obtener el resultado.
La clasificación de cubos es principalmente adecuada para datos enteros de pequeña gama, y se distribuye de forma independiente y uniforme. La cantidad de datos que se pueden calcular es grande y cumple con el tiempo lineal esperado.
2. Demostración de algoritmo de clasificación de cubos
Por ejemplo, ahora hay un conjunto de datos [7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101]. ¿Cómo ordenarlo de pequeño a grande?
Pasos de operación:
(1) Establezca el número de cubos en 5 cubos vacíos, encuentre el valor máximo de 110 y el valor mínimo de 7, y el rango de cada cubo es 20.8 = (110-7+1)/5.
(2) atravesar los datos originales, colóquelo en el cubo correspondiente con una estructura de lista vinculada. El número 7, el valor del índice de cubo es 0, la fórmula de cálculo es el piso ((7 7) / 20.8), el número 36, el valor del índice de cubo es 1, el piso de la fórmula de cálculo ((36 7) / 20.8).
(3) Al insertar datos en el cubo con el mismo índice la segunda vez, determine el tamaño de los números existentes y los números recién insertados en el cubo, e insértelos en orden de izquierda a derecha, de pequeño a grande. Por ejemplo: cuando se inserta el cubo con el índice 2, al insertar 63, ya hay 4 números 56, 59, 60 y 65 en el cubo, y luego el número 63 se inserta a la izquierda de 65.
(4) Fusionar cubos no vacíos, fusionar 0, 1, 2, 3 y 4 cubos en orden de izquierda a derecha.
(5) Obtenga la estructura del tipo de cubo
3. Implementación del programa NodeJS
No es difícil implementar algoritmos maduros como la clasificación de cubos. Según las ideas anteriores, escribí un programa simple para implementarlas. Siento que la parte más problemática es usar JavaScript para manipular la lista vinculada.
El código real es el siguiente:
'usar estricto';//////////////////////////////////////////////////////// //////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////// Ordena ([1,4,1,1,5,3,2,3,3,2,5,2,8,9,2,1], 5) * Sort ([1,4,1,5,3,2,3,3,2,2,5,2,8,9,9,2,1], 5,0,5) */Exports.sort = function (arr, count) {if (arr.Llength == 0) Returns []; Count = Count || (contar> 1? Cuenta: 10); // juzga los valores máximos y mínimos var min = arr [0], max = arr [0]; para (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); // Inicializar cubos var buckets = []; // Datos de almacenamiento para cubrir para (var i = 0; i <arr.length; i ++) {var idx = math.floor ((arr [i] - min) /delta); // Índice de bucket if (buckets [idx]) {// bucket var no vacío bucket = buckets [idx]; var insert = false; // Inserte la piedra de la bandera l.retRaversal (bucket, function (item, done) {if (arr [i] <= item.v) {// más pequeño que, insertar l.append (item, _val (arr [i])); insertar = true; don (); // exit traversal}}); if (! insert) {// mayor que, insertar l.append (bucket, _val (arr [i])); }} else {// Bucket Var Bucket = l.init (); L.Append (Bucket, _val (arr [i])); cubos [idx] = bucket; // Implementación de la lista de enlaces}} var result = []; for (var i = 0, j = 0; i <count; i ++) {l.retRaversal (buckets [i], function (item) {// console.log (i+":"+item.v); resultado [j ++] = item.v;}); } resultado de retorno;} // Función de objeto de almacenamiento de lista vinculada _val (v) {return {v: v}}Ejecute el 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 (datos); console.log (algo.bucketsort.sort (datos, 5); console.log (algo.bucketsort.sort (datos, 10)); // 10 cubosProducción:
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, 94, 101, 110] [7, 22, 33, 36, 36, 42, 42, 56, 56, 59, 60, 63, 63, 65, 67, 77, 83, 84, 84, 94, 101, 110] [7, 22, 33, 36, 36, 42, 42, 56, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 94, 101, 101, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 94, 94, 114, 110, 110, 110, 110, 110, 110, 110, 110, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114.
Lo que debe explicarse es:
(1) clasificar en el cubo se puede implementar durante el proceso de inserción como se describe en el programa; o se puede insertar sin clasificar, y luego se ordene durante el proceso de fusión, y se puede llamar a una clasificación rápida.
(2) Lista vinculada. En la API subyacente del nodo, hay una implementación de la lista vinculada. No lo usé directamente, pero lo llamé a través del paquete Linklist: https://github.com/nodejs/node-v0.x-archive/blob/master/lib/_linklist.js
4. Caso: estadísticas de clasificación de cubos en puntajes de examen de ingreso a la universidad
Uno de los escenarios de aplicación más famosos para la clasificación de cubos es contar los puntajes del examen de ingreso a la universidad. El número de candidatos al examen de ingreso a la universidad nacional en un año es de 9 millones, y los puntajes son estándar, con un mínimo de 200 y un máximo de 900. No hay decimales. Si estos 9 millones de números están ordenados, ¿qué debemos hacer?
Análisis de algoritmo:
(1) Si usa clasificación basada en comparación, clasificación rápida, la complejidad promedio de tiempo es O (NLOGN) = O (9000000*LOG9000000) = 144114616 = 144 millones de comparaciones.
(2) Si utiliza la clasificación basada en el conteo, la clasificación de cubos y la complejidad promedio, puede controlar la complejidad lineal. Al crear 700 cubos, un cubo de 200 minutos a 900 minutos, o (n) = o (90000000), es equivalente a escanear 900 W de datos una vez.
Ejecutamos un programa para comparar la clasificación rápida de clasificación y cubo a la vez.
// Cree 100W Pieces de datos en [200,900] Intervalo cerrado var data = algo.data.randomdata (1000*1000,200,900); var s1 = new date (). Gettime (); algo.quicksort.sort (data); // stand rápida var s2 = nueva fecha (). GetTime (); algo.bucketsort.sort (data, 700) s3 = new Date (). GetTime (); console.log ("Tiempo de QuickSort: %SMS", S2-S1); console.log ("Tiempo de cubo: %SMS", S3-S2);Producción:
Tiempo de Quicksort: 14768MSBUCKET TIEMPO: 1089MS
Por lo tanto, para el caso de la puntuación del examen de ingreso a la universidad, ¡la clasificación de deseos es más adecuada! Nuestro uso de algoritmos apropiados en escenarios adecuados traerá mejoras de rendimiento al programa más allá del hardware.
5. Análisis de costos de clasificación de cubos
PERO...
La clasificación de bucket utiliza la relación de mapeo de las funciones, reduciendo casi todos los trabajos de comparación. De hecho, el cálculo del valor F (k) de la clasificación de cubos es equivalente a la división en el orden rápido, y ha dividido una gran cantidad de datos en bloques de datos (cubos) básicamente ordenados. Entonces solo necesita hacer comparaciones avanzadas y clasificación de una pequeña cantidad de datos en el cubo.
La complejidad del tiempo de la clasificación de cubos y las palabras clave se divide en dos partes:
(1) Escripción para calcular la función de mapeo de cubos de cada palabra clave, y este tiempo complejidad es o (n).
(2) Use el algoritmo de clasificación de comparación avanzada para ordenar todos los datos en cada cubo, con una complejidad de tiempo de ∑O (Ni*Logni). donde Ni es el monto de los datos del cubo i-th.
Obviamente, la parte (2) es el determinante del rendimiento de la clasificación de cubos. Minimizar la cantidad de datos en el cubo es la única forma de mejorar la eficiencia (porque la mejor complejidad promedio de tiempo basada en la clasificación de comparación solo puede alcanzar O (N*logn)). Por lo tanto, necesitamos hacer todo lo posible para hacer los siguientes dos puntos:
(1) La función de mapeo f (k) puede asignar n datos a cubos m de manera uniforme, de modo que cada cubo tenga volúmenes de datos [n/m].
(2) Intente aumentar el número de barriles. En el caso extremo, cada cubo solo puede obtener un datos, lo que evita completamente la operación de clasificación de "comparación" de datos en el cubo. Por supuesto, no es fácil hacer esto. Cuando la cantidad de datos es enorme, la función F (k) hará que el número de colecciones de cubos sea enorme y los desechos espaciales son graves. Esta es una compensación entre el costo del tiempo y el espacio.
Para que se clasifiquen los datos de N, la complejidad promedio del tiempo de clasificación de cubos de cada cubo [N/M] es:
O (n)+o (m*(n/m)*log (n/m)) = o (n+n*(logn-logm)) = o (n+n*logn-n*logm)
Cuando n = m, es decir, cuando solo hay un datos por cubo debajo del límite. La mejor eficiencia de la clasificación de cubos puede alcanzar O (N).
6. Resumen
La complejidad promedio de tiempo de la clasificación de cubos es lineal O (n+c), donde c = n*(logn-logm). Si el número de barriles M es mayor en relación con la misma N, cuanto mayor sea su eficiencia y la mejor complejidad del tiempo alcanza O (N). Por supuesto, la complejidad espacial de la clasificación de cubos es O (N+M). Si los datos de entrada son muy grandes y el número de cubos es muy grande, el costo de espacio es indudablemente costoso. Además, el tipo de cubo es estable.
En realidad, tengo otro sentimiento: entre los algoritmos de búsqueda, la mejor complejidad del tiempo del algoritmo de búsqueda basado en comparación es O (Logn). Por ejemplo, la búsqueda de medio fin, los árboles binarios equilibrados, los árboles rojos y negros, etc. Sin embargo, la tabla hash tiene o (c) eficiencia de búsqueda de nivel lineal (la eficiencia de búsqueda alcanza o (1) en caso de ningún conflicto). Veamos bien: ¿Son los pensamientos y la clasificación de cubos de las mesas hash la misma canción?