Ho un piccolo problema e non riesco a trovare una soluzione soddisfacente per questo. C'è un array di byte e ho bisogno di questi byte ordinati per 7 bit alti mentre preservando l'ordine dei bit bassi.Ordinamento di tipo di matrice di byte rapido
Così in origine si presentava così:
// 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
Ma questi blocchi sono abbastanza grandi (8M attualmente), e voglio usare più thread, ed un 8M extra per filo è evidente.
così ho cercato di utilizzare alcuni semplici 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);
}
}
}
ma cambia l'ordine di questi bit bassi e diventa inutilizzabile.
In realtà alcuni metodi più semplici, come bubblesort, fanno semplicemente ciò che voglio, ma sono molto più lenti e anche la velocità è un problema.
Così attualmente I sorta blocchi più piccoli tramite un buffer temporaneo, quindi utilizzare una tabella indice per accedere blocchi parzialmente ordinati in ordine:
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);
}
}
Ma tmp [] e OFS [] array utilizzano troppo spazio di stack e il suo non è un tipo completo, quindi continuo a chiedermi se c'è qualche soluzione pulita per questo.
Un campione di dati e le mie realizzazioni sono disponibili qui: http://nishi.dreamhosters.com/u/tmpsort_v0.rar
Grazie, ho davvero perso questo approccio, potrebbe valere la pena provare. – Shelwien