algorithm - son - tags en wordpress
Tipo de clasificación frente a clasificación de conteo frente a clasificación de categoría. ¿Cual es la diferencia? (7)
Estoy leyendo las definiciones de radix, conteo y tipos de cubo y parece que todos ellos son solo el siguiente código:
public static void sort(int[] a, int maxVal){
int [] bucket=new int[maxVal+1];
for (int i=0; i<bucket.length; i++){
bucket[i]=0;
}
for (int i=0; i<a.length; i++){
bucket[a[i]]++;
}
int outPos=0;
for (int i=0; i<bucket.length; i++){
for (int j=0; j<bucket[i]; j++){
a[outPos++]=i;
}
}
}
Sé que no puedo estar en lo cierto, entonces ¿qué me estoy perdiendo? Muestre el código si cree que puede ayudar a explicarlo en Java o C.
Tipo de clasificación frente a clasificación de conteo frente a clasificación de categoría. ¿Cual es la diferencia?
El ordenamiento del cubo coloca las llaves o los elementos que se ordenarán en cubetas. Cómo son lugares en cubos es arbitrario y pueden ser partes de una clave compuesta y cualquier distribución que desee. Es posible que las cubetas individuales tengan que clasificarse más.
Ordenar en la memoria es más rápido que ordenar en el disco. Sin embargo, si tiene más datos de los que caben en la memoria, necesita otra opción. Lo que puedes hacer es ordenar por cubo, donde los cubos son lo suficientemente pequeños como para caber en la memoria. es decir, hay una gran cantidad de entradas en cada segmento. Estos pueden ordenar rápidamente de forma individual.
El ordenamiento de radix es un tipo específico de clasificación de cubeta. Comienza con la parte superior de n bits o n dígitos y puede ordenar esos depósitos utilizando una clasificación de radix, etc., hasta que cada entrada se clasifique.
El recuento de ordenación es como usar ordenación de raíz, excepto que está utilizando el valor completo. En lugar de registrar cada objeto, tiene una cubeta para cada objeto y solo cuenta el número de ocurrencias. Esto funciona bien cuando tiene un número limitado de claves posibles y tiene muchos duplicados.
Comencemos reescribiendo su código en C, porque C me resulta más familiar. Así que vamos a recordar su código con algunos comentarios:
int
counting_sort(int a[], int a_len, int maxVal)
{
int i, j, outPos = 0;
int bucket_len = maxVal+1;
int bucket[bucket_len]; /* simple bucket structure */
memset(bucket, 0, sizeof(int) * bucket_len);
/* one loop bucket processing */
for (i = 0; i < a_len; i++)
{
bucket[a[i]]++; /* simple work with buckets */
}
for (i=0; i < bucket_len; i++)
{
for (j = 0; j < bucket[i]; j++)
{
a[outPos++] = i;
}
}
return 0;
}
Ahora ofrezcamos a este tipo algunos datos realistas:
[126, 348, 343, 432, 316, 171, 556, 223, 670, 201]
En salida tenemos
[126, 171, 201, 223, 316, 343, 348, 432, 556, 670]
Parece que todo está bien? Aún no. Veamos maxVal. Es 670 (!) Para ordenar una matriz de 10 elementos aquí utilizamos una matriz de 670 elementos, principalmente ceros. Muy. Para manejar este problema de clasificación de conteo, tenemos dos formas posibles de generalización:
1) Primera forma: hacer una ordenación por dígitos. Esto se llama radix-sort. Vamos a mostrar un código, tratando de hacerlo lo más parecido posible al código de recuento. De nuevo mira los comentarios:
int
radix_sort(int a[], int a_len, int ndigits)
{
int i;
int b[a_len];
int expn = 1;
/* additional loop for digits */
for (i = 0; i != ndigits; ++i)
{
int j;
int bucket[10] = {0}; /* still simple buckets */
/* bucket processing becomes tricky */
for (j = 0; j != a_len; ++j)
bucket[ a[j] / expn % 10 ]++;
for (j = 1; j != 10; ++j)
bucket[j] += bucket[j - 1];
for (j = a_len - 1; j >= 0; --j)
b[--bucket[a[j] / expn % 10]] = a[j];
for (j = 0; j != a_len; ++j)
a[j] = b[j];
expn *= 10;
}
}
Estamos intercambiando multiplicadores cerca de N para memoria. ¿Lucro? Tal vez. Pero en algunos casos el multiplicador cerca de N es muy importante. El programa, que trabaja un día y trabaja una semana, es muy diferente de la vista de los usuarios, incluso si ambos funcionan 1 * O (N) y 7 * O (N) respectivamente. Y entonces estamos llegando a una segunda generalización:
2) Segunda forma: hacer cubos más sofisticados. Esto se llama clasificación por cubo.
Vamos a comenzar de nuevo con un código. Prefiero más código antes de los argumentos filosóficos. Todavía mira los comentarios, son esenciales.
int
bucket_sort(int a[], int a_len, int maxVal)
{
int i, aidx;
typedef struct tag_list {
int elem;
struct tag_list *next;
} list_t, *list_p;
list_p bucket[10] = {0}; /* sophisticated buckets */
/* one loop simple processing with one more inner loop
to get sorted buckets (insert-sort on lists, Cormen-style) */
for (i = 0; i != a_len; ++i)
{
int bnum = (10 * a[i]) / maxVal;
list_p bptr = bucket[bnum];
list_p belem = malloc(sizeof(list_t));
belem->elem = a[i];
if (bptr == 0)
{
bucket[bnum] = belem;
belem->next = 0;
continue;
}
else if (a[i] <= bptr->elem)
{
belem->next = bptr;
bucket[bnum] = belem;
continue;
}
else
{
while (bptr != 0)
{
if ((bptr->elem <= a[i]) && ((bptr->next == 0) || (bptr->next->elem > a[i])))
{
belem->next = bptr->next;
bptr->next = belem;
break;
}
}
}
}
/* one loop (looks as two) to get all back */
aidx = 0;
for (i = 0; i != 10; ++i)
{
list_p bptr = bucket[i];
while (bptr)
{
list_p optr = bptr;
a[aidx] = bptr->elem;
aidx += 1;
bptr = bptr->next;
free(optr);
}
}
return 0;
}
entonces que tenemos aqui? Estamos intercambiando una estructura y un requisito de cubo sofisticados para la memoria asignada dinámicamente pero ganando la memoria estática, y el multiplicador cerca de N en promedio.
Ahora recordemos qué vimos en el código:
- Clasificación de conteo: cubos simples, procesamiento simple, sobrecarga de memoria
- Clasificación de radix: cubos simples, procesamiento sofisticado, sobrecarga de velocidad (y aún necesita memoria estática adicional)
- Clasificación del cubo: cubos sofisticados, procesamiento simple, requiere memoria dinámica, buena en promedio
Por lo tanto, los tipos de radix y de cubo son dos generalizaciones útiles del tipo de recuento. Tienen mucho en común con el recuento de ordenaciones y entre ellos, pero en todos los casos estamos perdiendo algo y ganando algo. La ingeniería de software se trata de un equilibrio entre estas oportunidades.
De acuerdo con Geekviewpoint:
Radix: http://www.geekviewpoint.com/java/sorting/radixsort
El ordenamiento de radix, al igual que la ordenación de conteo y ordenación de depósitos, es un algoritmo basado en enteros (es decir, se supone que los valores de la matriz de entrada son enteros). Por lo tanto, el género radix se encuentra entre los algoritmos de clasificación más rápidos que existen, en teoría. La distinción particular para el género radix es que crea un depósito para cada cifra (es decir, un dígito); como tal, de forma similar a la ordenación del cubo, cada depósito en orden de radix debe ser una lista viable que pueda admitir claves diferentes.
Cubo: http://www.geekviewpoint.com/java/sorting/bucketsort
El tipo de ordenamiento es realmente muy bueno teniendo en cuenta que el tipo de conteo es razonablemente su límite superior. Y contar es muy rápido. La distinción particular para la ordenación de depósitos es que usa una función de hash para dividir las teclas de la matriz de entrada, de modo que varias teclas pueden intercambiarse al mismo cubo. Por lo tanto, cada cubo debe ser efectivamente una lista creíble; similar al tipo de raíz.
Contando: http://www.geekviewpoint.com/java/sorting/countingsort
La distinción particular para el tipo de conteo es que crea un cubo para cada valor y mantiene un contador en cada cubo. Luego, cada vez que se encuentra un valor en la colección de entrada, se incrementa el contador apropiado. Debido a que el ordenamiento de conteo crea un depósito para cada valor, una restricción impositiva es que el valor máximo en el conjunto de entrada se conozca de antemano.
Lo explican con más detalles en su sitio.
Editar:
Si usa radix sort y sus números son decimales, necesita 10 cubos, uno para cada dígito, de 0 a 9.
Si está utilizando la ordenación por conteo, entonces necesita una cubeta para cada valor único en la entrada (en realidad, necesita una cubeta para cada valor entre 0 y máximo).
Si está utilizando bucketsort, no sabe cuántos cubos usará. Cualquiera que sea la función hash que esté utilizando determinará la cantidad de cubetas.
En primer lugar, veamos la diferencia entre Ordenar radix y Ordenar cubo, porque generalmente es algo confuso porque la idea parece ser la misma. Luego observamos Counting Sort que es como una versión primaria de estos dos y qué problemas con el recuento de ordenamiento hacen que los otros dos sean utilizados
El pase inicial de ambos tipos de Radix y Bucket es el mismo. Los elementos se colocan en ''Cubos'', es decir, 0-10, 11-20, ... y así sucesivamente, dependiendo de la cantidad de dígitos en el no más grande, es decir, el base. Sin embargo, en la siguiente pasada, el ordenamiento del cubo ordena estos ''cubos'' y los agrega a una matriz. Sin embargo, el método de clasificación de radix agrega los depósitos sin una clasificación adicional, y los ''recoloca'' basándose en el segundo dígito (el lugar de las diez) de los números. Por lo tanto, el ordenamiento del cubo es más eficiente para los arrays ''densos'', mientras que el ordenamiento del núcleo puede manejar bien las matrices dispersas. Bueno, piense en el tipo de cubo como este
Supongamos que tiene una lista de n registros, cada uno con una clave que es un número del 1 al k (generalizamos el problema un poco, por lo que k no es necesariamente igual a n).
Podemos resolver esto haciendo una variedad de listas enlazadas. Movemos cada registro de entrada en la lista en la posición apropiada de la matriz y luego concatenamos todas las listas juntas en orden.
bucket sort(L)
{
list Y[k+1]
for (i = 0; i <= k; i++) Y[i] = empty
while L nonempty
{
let X = first record in L
move X to Y[key(X)]
}
for (i = 0; i <= k; i++)
concatenate Y[i] onto end of L
}
¿Qué hacer cuando k es grande? Piense en la representación decimal de un número x = a + 10 b + 100 c + 1000 d + ... donde a, b, c, etc., todo en el rango 0..9. Estos dígitos son lo suficientemente pequeños como para hacer una clasificación de cubo.
radix sort(L):
{
bucket sort by a
bucket sort by b
bucket sort by c
...
}
o más simplemente
radix sort(L):
{
while (some key is nonzero)
{
bucket sort(keys mod 10)
keys = keys / 10
}
}
¿Por qué hacemos primero el dígito menos importante? Para el caso, ¿por qué hacemos más de un cubo, ya que el último es el que pone todo en su lugar? Respuesta: Si estamos tratando de ordenar cosas a mano, tendemos a hacer algo diferente: primero hagamos una ordenación por cubetas, luego clasifiquemos recursivamente los valores que comparten un primer dígito común. Esto funciona, pero es menos eficiente ya que divide el problema en muchos subproblemas. Por el contrario, la clasificación de radix nunca divide la lista; simplemente aplica la ordenación de cubos varias veces a la misma lista. En la ordenación de radix, el último paso de clasificación de cubo es el que tiene el mayor efecto en el orden general. Entonces queremos que sea el que use los dígitos más importantes. Los pases de clasificación de canas anteriores se usan solo para ocuparse del caso en el que dos objetos tienen la misma llave (mod 10) en la última pasada.
Ahora que tenemos todo eso fuera del camino todo lo que hace el conteo es mantener una matriz auxiliar C con elementos k, todos inicializados a 0.
Hacemos una pasada a través de la matriz de entrada A y para cada elemento i en A que vemos, incrementamos C [i] en 1. Después de iterar a través de los n elementos de A y actualizar C, el valor en el índice j de C corresponde cuántas veces apareció j en A. Este paso toma O (n) tiempo para iterar por A. Una vez que tenemos C, podemos construir la versión ordenada de A iterando por C e insertando cada elemento ja total de C [j] veces en una nueva lista (o A sí mismo). Iterar a través de C toma el tiempo O (k). El resultado final es una A ordenada y en total tomó O (n + k) tiempo para hacerlo.
La caída del tipo de conteo es que puede no ser demasiado práctico si el rango de elementos es demasiado grande. Por ejemplo, si el rango de los n elementos que debemos ordenar es de 1 a n 3, entonces simplemente crear la matriz auxiliar C tomará O (n ^ 3) tiempo y la clasificación de conteo asintóticamente será peor que la ordenación por inserción. Esto también toma O (n ^ 3) espacio que es significativamente más grande que cualquier espacio utilizado por cualquier otro algoritmo de clasificación que hayamos aprendido hasta ahora. La ordenación de radix ayuda a resolver este problema clasificando los elementos dígito a dígito
Nota: Fuentes para la respuesta y lectura adicional:
http://htmltolatex.sourceforge.net/samples/sample4.html
La primera respuesta a: ¿Cuál es la diferencia entre ordenar por cubo y ordenar por radix?
La clase de ordenamiento utiliza una forma de conteo como subrutina (vale, puede usar, pero la mayoría de las veces será de tipo de conteo).
Countingsort es una forma especial de clasificar por cubo, como respondió kasavbere.
Y Bucketsort divide las llaves en cubos y luego ordena los cubos individualmente.
Para ordenar una matriz usando count sort:
#define MAX_INPUT 1000
void sort(int arr[100], int n)
{
static int hash[MAX_INPUT], i, j;
memset(hash, 0, sizeof hash);
for (i = 0; i < n; ++i) ++hash[arr[i]];
j = 0;
for (i = 0; i < MAX_INPUT; ++i)
while (hash[i]--)
arr[j++] = i;
}
Esto es solo O(MAX_INPUT) , ordenando así en tiempo lineal. Para ordenar por cubo, es muy diferente. Aquí hay una implementación
Su código es una variante simple de conteo ordenado sin datos, solo claves.
La clasificación de radix se basa en este método. El problema con la clasificación de conteo es el requisito de memoria: int [] bucket=new int[maxVal+1]; . El género Radix resuelve este problema. La idea es usar la clasificación de conteo varias veces, primero para dígitos más bajos y luego para valores más altos. Por ejemplo, para ordenar enteros de 32 bits puede usar:
sort(a, 65535) using lower half as key
sort(a, 65535) using higher half as key
Funciona, porque el ordenamiento de conteo es estable: mantiene el orden de los datos con las mismas claves. Es como ordenar en hoja de cálculo: sort by B; sort by A sort by B; sort by A le da elementos ordenados por A, y por B cuando son iguales.
El ordenamiento del cubo es una generalización del tipo de conteo. Puede usarlo para ordenar números reales de alguna distribución de probabilidad predecible (por ej., Uniforme (0,1) ). La idea es usar el tipo de conteo (usando el floor(x*N_BUCKETS) como clave) y luego solo ordenar cada cubo de forma independiente.