c - 快速就地排序字节数组

Question

我遇到了一个小问题，找不到满意的解决方案。 有一个字节数组，我需要这些字节按高 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

但是这些 block 足够大(目前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 );
    }
  }
}

但是它改变了这些低位的顺序并且变得不可用。

其实一些更简单的方法，比如bubblesort，按我的意思做就行了， 但它们要慢得多，而且速度也是一个问题。

所以目前我通过临时缓冲区对较小的 block 进行排序，然后使用 按顺序访问部分排序的 block 的索引表:

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

Answer 1

为什么不就地使用任何标准，稳定 sorting algorithm ，例如Insertion Sort , 并实现适当的比较器功能 ?