Fast Inplace Art von Byte-Array

Question

Ich habe ein kleines Problem und kann keine zufriedenstellende Lösung dafür finden. Es gibt ein Byte-Array und ich brauche diese Bytes nach hohen 7 Bits sortiert, während die Reihenfolge der niedrigen Bits erhalten.

So ursprünglich sah es wie folgt aus:

// 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 

Aber diese Blöcke sind groß genug (8M zur Zeit), und ich möchte mehrere Threads verwenden, und ein extra 8M pro Faden bemerkbar. So

Ich habe versucht, einige einfache Radixsort zu verwenden:

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

Aber es ändert sich die Reihenfolge dieser niedrigen Bits und es wird unbrauchbar.

Eigentlich einige einfachere Methoden, wie bubblesort, nur tun, was ich will, aber sie sind viel langsamer, und Geschwindigkeit ist ein Problem zu.

Also ich derzeit sortieren kleinere Blöcke über einen temporären Puffer, dann eine Indextabelle verwenden teilweise sortierten Stücke, um den Zugriff auf:

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

Aber tmp [] und ofs [] Arrays verwenden zu viel Stack-Speicher und seine nicht eine vollständige Art, so frage ich mich, ob es eine saubere Lösung dafür gibt.

Eine Probe von Daten und meine Implementierungen sind hier verfügbar: http://nishi.dreamhosters.com/u/tmpsort_v0.rar

Answer 1

Mit zusätzlichen 64kB können Sie (wie Sie bemerkt haben) einen 512 kbit Block (abzüglich einiger fester Indizierungsdaten) in komprimierter Form speichern (nur die niedrigsten Bits für jeden Schlüssel speichern) Über die großen Blöcke gehen und konvertieren sie zu ihren komprimierten sortierten Formen und verdichten sie, wie Sie am Anfang des ganzen Arrays gehen.

Jetzt die komprimierten Formulare in ein großes komprimiertes Formular zusammenführen (einfach mit dem freigesetzten 7M). Dann dekomprimieren Sie zurück zum sortierten Array.

Dies ist O (N), obwohl die Konstante mit 3 Durchläufen, die einige nichttriviale Bitoperationen beinhalten, ziemlich groß aussieht.

Answer 2

Warum gerade keine Standard-in-place verwenden, stabilsorting algorithm, z.B. Insertion Sort, und implementieren Sie eine entsprechende Komparatorfunktion?

Answer 3

Es ist möglich, Quicksort als stabile Sortierung zu implementieren. In Bezug auf Big-O, ist es nicht besser als Insertion Art, aber in der Praxis wird es eine Los besser durchführen. Wenn Sie Sortiernetze für Blätter mit einer Größe von bis zu 6 oder 8 fest codieren, dann ist das meiner Meinung nach die beste Leistung, die Sie für eine stabile, in-Place-Sortierung erhalten.

Eigentlich ... angeblich gibt es so etwas wie eine In-Place, stabile Merge-Sortierung. In Bezug auf ideale theoretische Eigenschaften, ist es der heilige Gral der Sortierung - an Ort und Stelle, wahr O(n log n), und stabil, alle zur gleichen Zeit. Aber ich vermute, es ist ein großer Schmerz zu implementieren und hat ziemlich große konstante Bedingungen, um mit diesem großen O zu gehen.

Answer 4

Dies kann mit relativ einfachen Code in etwas mehr als O (n log n) Zeit mit einer Version von Radix Sortierung erreicht werden, die eine stabile Sortierung auf jedem der 7 wichtigen Bits von am wenigsten signifikant zu höchst signifikant. Der Vorteil dieser Technik in Bezug auf eine stabile In-Place-Merge-Sortierung ist, dass der Code viel einfacher ist, wenn Sie alles selbst schreiben.

Hier ist die Funktion, um eine stabile In-Place-Sortierung nach einem bestimmten Bit durchzuführen. Hier wird rekursiv der Einfachheit halber geschrieben mit O (lg n) Stapelspeicher (diese Stapel Raumnutzung kann beseitigt werden, wenn Sie mit Hilfe eines for-Schleife wollen die Kluft zu organisieren und erobern Ansatz):

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

Die Funktion isSet testet, ob ein Bit gesetzt ist und reverse führt eine In-Place-Array-Umkehrung durch. Die obige Sortierunterroutine wird an jedem Bit bezeichnet als (wie in Radixsort) folgt:

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

Die Gesamtlaufzeit ist "O (7 * n log n)". Der zusätzliche Faktor von 7 könnte variabel sein, wenn dieser Algorithmus verallgemeinert würde.