Быстрый байтовый массив - PullRequest
5 голосов
/ 17 ноября 2010

У меня небольшая проблема, и я не могу найти для нее удовлетворительного решения.Есть байтовый массив, и мне нужно, чтобы эти байты были отсортированы по старшим 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

Ответы [ 4 ]

1 голос
/ 18 ноября 2010

Этого можно добиться с помощью относительно простого кода за чуть более чем O (n log n) времени, используя версию радикальной сортировки, которая выполняет устойчивую сортировку для каждого из 7 важных битов, от наименее значимого до наиболее значимого. Преимущество этого метода по сравнению со стабильной сортировкой слиянием на месте заключается в том, что код намного проще, если вы пишете все это самостоятельно.

Вот функция для выполнения стабильной сортировки по месту на один указанный бит. Здесь он написан рекурсивно для простоты с использованием стекового пространства O (lg n) (это использование стекового пространства может быть исключено, если вы хотите использовать цикл for для организации подхода «разделяй и властвуй»):

// 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);
}

Функция isSet проверяет, установлен ли бит, а reverse выполняет инверсию массива на месте. Вышеупомянутая подпрограмма сортировки вызывается для каждого бита следующим образом (как в сортировке по основанию):

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

Общее время работы: «O (7 * n log n)». Дополнительный коэффициент 7 мог бы быть переменным, если бы этот алгоритм был обобщен.

1 голос
/ 17 ноября 2010

Почему бы просто не использовать какой-либо стандартный на месте, стабильный алгоритм сортировки , например, Вставить сортировку и реализовать соответствующую функцию компаратора?

0 голосов
/ 18 ноября 2010

Имея дополнительные 64 КБ, вы можете (как вы заметили) сохранить блок 512 Кбит (за вычетом некоторого фиксированного объема данных индексации) в сжатом виде (сохраняя только самые младшие биты для каждого ключа). Перейдите к большим блокам и преобразуйте их.к их сжато-отсортированным формам, сжимая их по ходу в начале всего массива.

Теперь объедините сжатые формы в одну большую сжатую форму (легко с освобожденным 7M). Затем распакуйте обратно котсортированный массив.

Это O (N), хотя константа выглядит довольно большой с 3 проходами, которые включают некоторые нетривиальные битовые операции.

0 голосов
/ 17 ноября 2010

Возможно реализовать быструю сортировку как стабильную сортировку.С точки зрения big-O, это не лучше, чем сортировка вставкой, но на практике она будет работать на lot лучше.Если вы жестко программируете сети сортировки для листьев размером до 6 или 8, я думаю, что это лучшая производительность, которую вы получите для стабильной сортировки на месте.предположительно, существует такая вещь, как устойчивая сортировка слиянием.С точки зрения идеальных теоретических характеристик, это святой Грааль сортировки - на месте, истинный O(n log n) и стабильный, все одновременно.Но я подозреваю, что это огромная боль в реализации и довольно большие постоянные термины, чтобы идти с этим большим O.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...