Tipo de arreglo de byte rápido in situ

Question

Tengo un pequeño problema y no puedo encontrar una solución satisfactoria para él. Hay una matriz de bytes y necesito estos bytes ordenados por 7 bits altos, mientras que conserva el orden de los bits bajos.

Así que originalmente era la siguiente:

// sort buf[N] to tmp[N] 
uint offs[128+1]; uint c,i,s; 
for(i=0; i<128; i++) offs[i]=0; 
for(i=0; i<l; i++) offs[buf[i]>>1]++; 
for(i=0,s=0; i<128; i++) c=offs[i], offs[i]=s, s+=c; offs[i]=s; 

byte* tmp = new byte[N]; 
for(i=0; i<N; i++) c=buf[i], tmp[offs[c>>1]++]=c; // sort 

Pero estos bloques son lo suficientemente grandes (8M en la actualidad), y quiero utilizar múltiples hilos, 8M y un extra por hilo es notable.

así que he intentado utilizar algunos simples Radix sort:

void radix(byte* buf, uint h, uint l, uint mask) { 
    uint p = (h+l)>>1, q = h; 
    uint i = offs[h], j = offs[l]-1; h = offs[p]; 
    if((i<h) && (j>=h)) { 
    byte c = buf[i], d = buf[j]; 
    while((i<h) && (j>=h)) { 
     while((c&mask)==0) c = buf[++i]; // find value with bit 1 
     while((d&mask)!=0) d = buf[--j]; // find value with bit 0 
     buf[i]=d; buf[j]=c; // swap 1-0 -> 0-1 
     c = buf[++i]; d = buf[--j]; 
    } 
    if(mask>=4) { 
     radix(buf, q,p, mask>>1); 
     radix(buf, p,l, mask>>1); 
    } 
    } 
} 

pero cambia el orden de estos bits de baja y se vuelve inutilizable.

En realidad, algunos métodos más simples, como bubblesort, simplemente haz lo que yo quiero, pero son mucho más lentos, y la velocidad también es un problema.

Así actualmente en cierto modo me bloques más pequeños a través de una memoria intermedia temporal, a continuación, utilizar una tabla de índice para acceder a trozos parcialmente ordenados en orden:

struct tmpsort { 

    enum{ blocksize = (1<<16)-1 }; 

    unsigned short ofs[(max_quants+blocksize-1)/blocksize][probN]; 

    tmpsort(byte* buf, uint f_len) { 
    uint i,j,k; 
    uint freq[2*probN]; // prob freqs 
    byte tmp[blocksize+1]; 

    for(k=0,j=0; k<f_len; k+=blocksize,j++) { 
     uint l = Min(k+blocksize,f_len)-k; 
     byte* p = &buf[k]; 

     // compute offsets of sorted chunks 
     for(i=0; i<2*probN; i++) freq[i]=0; 
     for(i=0; i<l; i++) freq[p[i]]++; 
     for(i=0; i<probN; i++) freq[i+1]=freq[2*i+0]+freq[2*i+1]; // 1=0+1, 2=2+3, 3=4+5 
     freq[0] = 0; 
     for(i=0; i<probN; i++) freq[i+1]+=freq[i]; 
     for(i=0; i<probN; i++) ofs[j][i]=freq[i+1]; 

     // sort the block via tmp 
     for(i=0; i<l; i++) { byte c=p[i]; tmp[freq[c>>1]++]=c; } 
     for(i=0; i<l; i++) p[i]=tmp[i]; 
    } 
    } 

}; 

[...] 

tmpsort ts(buf, f_len); 
for(i=0; i<probN; i++) { 
    for(k=0,j=0; k<f_len; k+=ts.blocksize,j++) { 
    uint x = i>0 ? ts.ofs[j][i-1] : 0; 
    for(; x<ts.ofs[j][i]; x++) putc(buf[k+x],g); 
    } 
} 

Pero tmp [] y OFS [] matrices utilizan demasiado espacio pila , y su no es un tipo completo, así que sigo preguntándome si hay alguna solución clara para esto.

Una muestra de datos y mis implementaciones están disponibles aquí: http://nishi.dreamhosters.com/u/tmpsort_v0.rar

Answer 1

Al tener 64kB adicionales, puedes (como habrás notado) almacenar un bloque de 512 kbit (menos una cantidad fija de datos de indexación) en forma comprimida (almacenando solo los bits más bajos para cada clave) Repasa los bloques grandes y conviértelos ellos a sus formas clasificadas comprimidas, compactándolos sobre la marcha al comienzo de toda la matriz.

Ahora combine las formas comprimidas en una gran forma comprimida (fácil con la liberación de 7M). A continuación, vuelva a descomprimir la matriz ordenada.

Esto es O (N), aunque la constante parece bastante grande con 3 pasadas que implican algunas operaciones de bits no triviales.

Answer 2

¿Por qué no utiliza ninguna norma en el lugar, establesorting algorithm, por ejemplo, Insertion Sort, e implementar una función de comparador adecuada?

Answer 3

Es posible implementar quicksort como un tipo estable. En términos de big-O, no es mejor que la ordenación de inserción, pero en la práctica realizará un lote mejor. Si codifica las redes de ordenamiento para las hojas de tamaño hasta 6 u 8, creo que se trata del mejor rendimiento que obtendrá para una ordenación estable e in situ.

En realidad ... supuestamente existe algo así como un tipo de fusión in situ y estable. En términos de características teóricas ideales, es el santo grial de la clasificación en el lugar, verdadero O(n log n), y estable, todo al mismo tiempo. Pero sospecho que es un gran esfuerzo implementarlo y tiene términos bastante grandes y constantes para ir con ese gran O.

Answer 4

Esto se puede lograr con un código relativamente simple en poco más de O (n log n) usando una versión de radix que realiza una clasificación estable en cada uno de los 7 bits importantes, desde el menos significativo hasta el más significativo. La ventaja de esta técnica en relación con una clasificación de fusión in situ estable es que el código es mucho más simple si lo está escribiendo todo usted mismo.

Esta es la función para realizar una ordenación in situ estable en un bit especificado. A continuación, se escribe de forma recursiva por simplicidad utilizando O (lg n) espacio de pila (este uso del espacio de pila se puede eliminar si se desea usando un bucle for para organizar el divide y vencerás):

// sort array x from i to j by bit b 
sort(x, i, j, b) { 
    if (i >= j - 1) return; 
    mid = (i + j)/2; 
    sort(x, i, mid, b); 
    sort(x, mid, j, b); 
    first1 = -1; 
    last0 = -1; 
    for (k = i; k < j; k++) { 
    if (first1 < 0 && isSet(x[k], b)) first1 = k; 
    if (!isSet(x[k], b)) last0 = k; 
    } 
    if (last0 < first1) return; 

    // the sequence of bit b generally looks something like 0000011100000111111 
    // so we reverse from the first 1 to the last 0 
    reverse(x, first1, last0afterfirst1); 
    newlast0 = first1; 
    while (!isSet(x[++newlast0], b)); 
    newlast0--; 

    // the elements in the range first1..last0 are in the wrong order, so reverse 
    reverse(x, first1, newlast0); 
    reverse(x, newlast0 + 1, last0); 
} 

La función isSet comprueba si se ha establecido un bit y reverse realiza una inversión de matriz in situ. La subrutina de clasificación arriba se llama en cada bit de la siguiente manera (como en radix especie):

sort(x) { 
    for (b = 1; b < 8; b++) { 
    sort(x, 0, n, b); 
    } 
} 

El tiempo total de ejecución es "O (7 * n log n)". El factor extra de 7 podría ser variable si este algoritmo se generalizara.