У меня небольшая проблема, и я не могу найти для нее удовлетворительного решения.Есть байтовый массив, и мне нужно, чтобы эти байты были отсортированы по старшим 7 битам при сохранении порядка младших битов.
Итак, изначально это выглядело так:
// 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
Но эти блоки достаточно велики(8M в настоящее время), и я хочу использовать несколько потоков, и дополнительные 8M на поток заметны.
Поэтому я попытался использовать некоторую простую сортировку по основанию:
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 );
}
}
}
Но это меняетсяпорядок этих младших битов, и он становится непригодным для использования.
На самом деле некоторые более простые методы, такие как сортировка пузырьков, просто делают то, что я хочу, но они намного медленнее, и скорость тоже является проблемой.
В настоящее время я сортирую меньшие блоки через временный буфер, затем использую таблицу индексов для доступа к частично отсортированным чанам в следующем порядке:
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 );
}
}
Но массивы tmp [] и ofs [] используют слишком много стекового пространства, иэто не полная сортировка, поэтому я продолжаю задаваться вопросом, есть ли какое-нибудь изящное решение для этого.
Образец данных и мои реализации доступны здесь: http://nishi.dreamhosters.com/u/tmpsort_v0.rar