Быстрое размещение типа байтового массива

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 

Но эти блоки достаточно велики (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, просто делают то, что я хочу, , но они намного медленнее, и скорость тоже проблема.

Так в настоящее время я сортирую меньшие блоков через временный буфер, затем использовать таблицу индекса для доступа частично отсортированных кусков в порядке:

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

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

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

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

Answer 2

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

Answer 3

Можно реализовать quicksort как стабильный вид. Что касается big-O, то это не лучше, чем сортировка вставки, но на практике он будет выполнять лот лучше. Если вы сортируете жесткие коды для листов размером до 6 или 8, я думаю, что это будет самая лучшая производительность, которую вы получите для стабильной, на месте сортировки.

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

Answer 4

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

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

// 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 * п § п)». Дополнительный коэффициент 7 может быть переменным, если этот алгоритм был обобщен.