In-Place-Radix-Sortierung

200

Dies ist ein langer Text. Bitte bei mir tragen. Die Frage lautet: Gibt es einen funktionsfähigen Radix-Sortieralgorithmus an Ort und Stelle ?


Vorläufig

Ich habe eine große Anzahl kleiner Zeichenfolgen mit fester Länge , die nur die Buchstaben "A", "C", "G" und "T" (ja, Sie haben es erraten: DNA ) verwenden, die ich sortieren möchte.

Im Moment benutze ich std::sortdie verwendet Introsort in allen gängigen Implementierungen des STL . Das funktioniert ganz gut. Ich bin jedoch davon überzeugt, dass die Radix-Sortierung perfekt zu meinem Problem passt und in der Praxis viel besser funktionieren sollte .

Einzelheiten

Ich habe diese Annahme mit einer sehr naiven Implementierung getestet und für relativ kleine Eingaben (in der Größenordnung von 10.000) war dies wahr (zumindest mehr als doppelt so schnell). Die Laufzeit verschlechtert sich jedoch miserabel, wenn das Problem größer wird ( N > 5.000.000).

Der Grund liegt auf der Hand: Radix-Sortierung erfordert das Kopieren der gesamten Daten (tatsächlich mehr als einmal in meiner naiven Implementierung). Dies bedeutet, dass ich ~ 4 GiB in meinen Hauptspeicher gesteckt habe, was offensichtlich die Leistung beeinträchtigt. Selbst wenn dies nicht der Fall wäre, kann ich es mir nicht leisten, so viel Speicher zu verwenden, da die Problemgrößen sogar noch größer werden.

Anwendungsfälle

Idealerweise sollte dieser Algorithmus mit jeder Zeichenfolgenlänge zwischen 2 und 100 sowohl für DNA als auch für DNA5 (die ein zusätzliches Platzhalterzeichen „N“ zulässt) oder sogar für DNA mit IUPAC- Mehrdeutigkeitscodes (was zu 16 unterschiedlichen Werten führt) funktionieren . Mir ist jedoch klar, dass all diese Fälle nicht abgedeckt werden können, und ich bin mit jeder Geschwindigkeitsverbesserung zufrieden, die ich bekomme. Der Code kann dynamisch entscheiden, an welchen Algorithmus gesendet werden soll.

Forschung

Leider ist der Wikipedia-Artikel über Radix-Sortierung nutzlos. Der Abschnitt über eine In-Place-Variante ist völliger Müll. Der Abschnitt NIST-DADS zur Radix-Sortierung ist so gut wie nicht vorhanden. Es gibt ein vielversprechend klingendes Papier namens Efficient Adaptive In-Place Radix Sorting, das den Algorithmus „MSL“ beschreibt. Leider ist auch dieses Papier enttäuschend.

Insbesondere gibt es die folgenden Dinge.

Erstens enthält der Algorithmus mehrere Fehler und lässt vieles ungeklärt. Insbesondere wird der Rekursionsaufruf nicht detailliert beschrieben (ich gehe einfach davon aus, dass er einen Zeiger erhöht oder reduziert, um die aktuellen Verschiebungs- und Maskenwerte zu berechnen). Außerdem werden die Funktionen verwendet dest_groupund dest_addresskeine Definitionen angegeben. Ich sehe nicht ein, wie ich diese effizient implementieren kann (dh in O (1); zumindest dest_addressnicht trivial).

Last but not least erreicht der Algorithmus die In-Place-Funktion, indem Array-Indizes mit Elementen innerhalb des Eingabearrays ausgetauscht werden. Dies funktioniert offensichtlich nur bei numerischen Arrays. Ich muss es für Saiten verwenden. Natürlich könnte ich einfach stark tippen und davon ausgehen, dass der Speicher es toleriert, einen Index dort zu speichern, wo er nicht hingehört. Dies funktioniert jedoch nur, solange ich meine Zeichenfolgen in 32 Bit Speicher komprimieren kann (unter der Annahme von 32-Bit-Ganzzahlen). Das sind nur 16 Zeichen (ignorieren wir für den Moment, dass 16> log (5.000.000)).

Ein anderes Papier eines der Autoren gibt überhaupt keine genaue Beschreibung, aber es gibt die Laufzeit von MSL als sublinear an, was absolut falsch ist.

Um es noch einmal zusammenzufassen : Gibt es Hoffnung, eine funktionierende Referenzimplementierung oder zumindest einen guten Pseudocode / eine gute Beschreibung einer funktionierenden Radix-Sorte zu finden, die an DNA-Strings funktioniert?

Konrad Rudolph
quelle
65
Das ist eine hervorragend geschriebene Frage.
JustinT
1
Wie klein sind die kleinen Saiten mit fester Länge?
EvilTeach
1
@ EvilTeach: Ich habe die Anwendungsfälle hinzugefügt.
Konrad Rudolph
2
@Stephan: das ist alles in Ordnung und gut. Aber im Falle von Kopier- / Cache-Fehlern bekomme ich nur eine Verzögerung. Im Falle des Gedächtnisses habe ich eine physikalische Grenze erreicht. Dies ist einfach nicht verhandelbar. All diese ausgefallenen Techniken zum Speichern von Teilen der Daten auf der Festplatte sind definitiv langsamer als die aktuelle QuickSort-Lösung.
Konrad Rudolph
2
(cont ') dsimchas Lösung ist dagegen für einige Eingaben definitiv schneller als Quicksort. Die Anzahl der Züge mag hoch und die Cache-Lokalität klein sein, aber in der realen Welt ist es immer noch gut. Ich habe die Lösung auch leicht angepasst, um die Anzahl der Swaps zu reduzieren, die ich durchführen muss.
Konrad Rudolph

Antworten:

61

Nun, hier ist eine einfache Implementierung einer MSD-Radix-Sorte für DNA. Es ist in D geschrieben, weil dies die Sprache ist, die ich am häufigsten benutze und daher am wenigsten dumme Fehler mache, aber es könnte leicht in eine andere Sprache übersetzt werden. Es ist vorhanden, erfordert jedoch 2 * seq.lengthDurchgänge durch das Array.

void radixSort(string[] seqs, size_t base = 0) {
    if(seqs.length == 0)
        return;

    size_t TPos = seqs.length, APos = 0;
    size_t i = 0;
    while(i < TPos) {
        if(seqs[i][base] == 'A') {
             swap(seqs[i], seqs[APos++]);
             i++;
        }
        else if(seqs[i][base] == 'T') {
            swap(seqs[i], seqs[--TPos]);
        } else i++;
    }

    i = APos;
    size_t CPos = APos;
    while(i < TPos) {
        if(seqs[i][base] == 'C') {
            swap(seqs[i], seqs[CPos++]);
        }
        i++;
    }
    if(base < seqs[0].length - 1) {
        radixSort(seqs[0..APos], base + 1);
        radixSort(seqs[APos..CPos], base + 1);
        radixSort(seqs[CPos..TPos], base + 1);
        radixSort(seqs[TPos..seqs.length], base + 1);
   }
}

Offensichtlich ist dies eher spezifisch für die DNA als allgemein, aber es sollte schnell gehen.

Bearbeiten:

Ich wurde neugierig, ob dieser Code tatsächlich funktioniert, und habe ihn getestet / debuggt, während ich darauf gewartet habe, dass mein eigener Bioinformatik-Code ausgeführt wird. Die obige Version ist jetzt tatsächlich getestet und funktioniert. Für 10 Millionen Sequenzen mit jeweils 5 Basen ist es ungefähr 3x schneller als ein optimierter Introsort.

Dsimcha
quelle
9
Wenn Sie mit einem 2x-Pass-Ansatz leben können, erstreckt sich dies auf Radix-N: Pass 1 = Gehen Sie einfach durch und zählen Sie, wie viele von jeder der N Ziffern vorhanden sind. Wenn Sie dann das Array partitionieren, erfahren Sie, wo jede Ziffer beginnt. Pass 2 wechselt an die entsprechende Position im Array.
Jason S
(z. B. für N = 4, wenn 90000 A, 80000 G, 100 C, 100000 T vorhanden sind, erstellen Sie ein Array, das auf die kumulativen Summen = [0, 90000, 170000, 170100] initialisiert ist, die anstelle Ihrer APos verwendet werden. CPos usw. als Cursor dafür, wo das nächste Element für jede Ziffer ausgetauscht werden soll.)
Jason S
Ich bin mir nicht sicher, wie die Beziehung zwischen der binären Darstellung und dieser Zeichenfolgendarstellung aussehen wird, abgesehen davon, dass mindestens viermal so viel Speicher wie nötig verwendet wird
Stephan Eggermont
Wie ist die Geschwindigkeit bei längeren Sequenzen? Sie haben nicht genug verschiedene mit einer Länge von 5
Stephan Eggermont
4
Diese Radix-Sorte scheint ein Sonderfall der American Flag-Sorte zu sein - eine bekannte Radix-Sortiervariante an Ort und Stelle.
Edward KMETT
21

Ich habe noch nie eine In-Place-Radix-Sortierung gesehen, und aufgrund der Art der Radix-Sortierung bezweifle ich, dass sie viel schneller ist als eine Out-of-Place-Sortierung, solange das temporäre Array in den Speicher passt.

Grund:

Die Sortierung führt einen linearen Lesevorgang für das Eingabearray durch, aber alle Schreibvorgänge sind nahezu zufällig. Ab einem bestimmten N führt dies zu einem Cache-Fehler pro Schreibvorgang. Dieser Cache-Fehler verlangsamt Ihren Algorithmus. Ob es vorhanden ist oder nicht, ändert diesen Effekt nicht.

Ich weiß, dass dies Ihre Frage nicht direkt beantwortet, aber wenn das Sortieren ein Engpass ist, sollten Sie sich als Vorverarbeitungsschritt die Sortieralgorithmen ansehen (die Wiki-Seite auf dem Soft-Heap kann Ihnen den Einstieg erleichtern).

Das könnte einen sehr schönen Cache-Lokalitätsschub geben. Eine fehl am Platz befindliche Radix-Sortierung für Lehrbücher ist dann besser. Die Schreibvorgänge werden immer noch nahezu zufällig sein, aber zumindest werden sie sich um dieselben Speicherblöcke gruppieren und als solche die Cache-Trefferquote erhöhen.

Ich habe keine Ahnung, ob es in der Praxis funktioniert.

Übrigens: Wenn Sie nur mit DNA-Strings arbeiten: Sie können ein Zeichen in zwei Bits komprimieren und Ihre Daten ziemlich oft packen. Dies reduziert den Speicherbedarf gegenüber einer naiiven Darstellung um den Faktor vier. Die Adressierung wird komplexer, aber die ALU Ihrer CPU hat ohnehin viel Zeit für alle Cache-Fehler.

Nils Pipenbrinck
quelle
2
Zwei gute Punkte; Fast Sortieren ist für mich ein neues Konzept, darüber muss ich lesen. Cache Misses ist eine weitere Überlegung, die meine Träume verfolgt. ;-) Ich muss mich darum kümmern.
Konrad Rudolph
Es ist auch für mich neu (ein paar Monate), aber sobald Sie das Konzept haben, sehen Sie Möglichkeiten zur Leistungsverbesserung.
Nils Pipenbrinck
Die Schreibvorgänge sind alles andere als zufällig, es sei denn, Ihr Radix ist sehr groß. Angenommen, Sie sortieren jeweils ein Zeichen (eine Radix-4-Sortierung), werden alle Schreibvorgänge in einen von 4 linear wachsenden Buckets ausgeführt. Dies ist sowohl Cache- als auch Prefetch-freundlich. Natürlich möchten Sie vielleicht einen größeren Radix verwenden, und an einem bestimmten Punkt treffen Sie einen Kompromiss zwischen Cache- und Prefetch-Freundlichkeit und Radix-Größe. Sie können die Gewinnschwelle mithilfe von Software-Prefetching oder einem Kratzbereich für Ihre Eimer in Richtung größerer Radices verschieben, indem Sie regelmäßig zu den "echten" Eimern spülen.
BeeOnRope
8

Sie können den Speicherbedarf sicherlich verringern, indem Sie die Sequenz in Bits codieren. Sie betrachten Permutationen für Länge 2 mit "ACGT", das sind 16 Zustände oder 4 Bits. Für Länge 3 sind das 64 Zustände, die in 6 Bit codiert werden können. Es sieht also aus wie 2 Bits für jeden Buchstaben in der Sequenz oder ungefähr 32 Bits für 16 Zeichen, wie Sie sagten.

Wenn es eine Möglichkeit gibt, die Anzahl der gültigen "Wörter" zu verringern, ist möglicherweise eine weitere Komprimierung möglich.

Für Sequenzen der Länge 3 könnte man also 64 Buckets erstellen, vielleicht mit der Größe uint32 oder uint64. Initialisieren Sie sie auf Null. Durchlaufen Sie Ihre sehr sehr große Liste von 3 Zeichenfolgen und codieren Sie sie wie oben. Verwenden Sie dies als Index und erhöhen Sie diesen Bucket.
Wiederholen Sie diesen Vorgang, bis alle Ihre Sequenzen verarbeitet wurden.

Als nächstes regenerieren Sie Ihre Liste.

Durchlaufen Sie die 64 Buckets, um für die in diesem Bucket gefundene Anzahl so viele Instanzen der durch diesen Bucket dargestellten Sequenz zu generieren.
Wenn alle Buckets iteriert wurden, haben Sie Ihr sortiertes Array.

Eine Folge von 4 addiert 2 Bits, so dass 256 Eimer vorhanden wären. Eine Folge von 5 addiert 2 Bits, so dass es 1024 Buckets geben würde.

Irgendwann nähert sich die Anzahl der Eimer Ihren Grenzen. Wenn Sie die Sequenzen aus einer Datei lesen, anstatt sie im Speicher zu belassen, steht mehr Speicher für Buckets zur Verfügung.

Ich denke, dies wäre schneller als die Sortierung vor Ort, da die Eimer wahrscheinlich in Ihren Arbeitssatz passen.

Hier ist ein Hack, der die Technik zeigt

#include <iostream>
#include <iomanip>

#include <math.h>

using namespace std;

const int width = 3;
const int bucketCount = exp(width * log(4)) + 1;
      int *bucket = NULL;

const char charMap[4] = {'A', 'C', 'G', 'T'};

void setup
(
    void
)
{
    bucket = new int[bucketCount];
    memset(bucket, '\0', bucketCount * sizeof(bucket[0]));
}

void teardown
(
    void
)
{
    delete[] bucket;
}

void show
(
    int encoded
)
{
    int z;
    int y;
    int j;
    for (z = width - 1; z >= 0; z--)
    {
        int n = 1;
        for (y = 0; y < z; y++)
            n *= 4;

        j = encoded % n;
        encoded -= j;
        encoded /= n;
        cout << charMap[encoded];
        encoded = j;
    }

    cout << endl;
}

int main(void)
{
    // Sort this sequence
    const char *testSequence = "CAGCCCAAAGGGTTTAGACTTGGTGCGCAGCAGTTAAGATTGTTT";

    size_t testSequenceLength = strlen(testSequence);

    setup();


    // load the sequences into the buckets
    size_t z;
    for (z = 0; z < testSequenceLength; z += width)
    {
        int encoding = 0;

        size_t y;
        for (y = 0; y < width; y++)
        {
            encoding *= 4;

            switch (*(testSequence + z + y))
            {
                case 'A' : encoding += 0; break;
                case 'C' : encoding += 1; break;
                case 'G' : encoding += 2; break;
                case 'T' : encoding += 3; break;
                default  : abort();
            };
        }

        bucket[encoding]++;
    }

    /* show the sorted sequences */ 
    for (z = 0; z < bucketCount; z++)
    {
        while (bucket[z] > 0)
        {
            show(z);
            bucket[z]--;
        }
    }

    teardown();

    return 0;
}
EvilTeach
quelle
Warum vergleichen, wenn Sie eh hash können?
Wowest
1
Verdammt richtig. Die Leistung ist im Allgemeinen ein Problem bei jeder DNA-Verarbeitung.
EvilTeach
6

Wenn Ihr Datensatz so groß ist, würde ich denken, dass ein festplattenbasierter Pufferansatz am besten ist:

sort(List<string> elements, int prefix)
    if (elements.Count < THRESHOLD)
         return InMemoryRadixSort(elements, prefix)
    else
         return DiskBackedRadixSort(elements, prefix)

DiskBackedRadixSort(elements, prefix)
    DiskBackedBuffer<string>[] buckets
    foreach (element in elements)
        buckets[element.MSB(prefix)].Add(element);

    List<string> ret
    foreach (bucket in buckets)
        ret.Add(sort(bucket, prefix + 1))

    return ret

Ich würde auch experimentieren, um eine größere Anzahl von Buckets zu gruppieren, zum Beispiel wenn Ihre Zeichenfolge wäre:

GATTACA

Der erste MSB-Aufruf würde den Bucket für GATT zurückgeben (insgesamt 256 Buckets). Auf diese Weise erstellen Sie weniger Verzweigungen des festplattenbasierten Puffers. Dies kann die Leistung verbessern oder nicht. Experimentieren Sie also damit.

FryGuy
quelle
Für einige Anwendungen verwenden wir speicherabgebildete Dateien. Im Allgemeinen gehen wir jedoch davon aus, dass der Computer gerade noch genügend RAM bereitstellt, um keine explizite Festplattenunterstützung zu erfordern (natürlich findet immer noch ein Austausch statt). Aber wir entwickeln bereits einen Mechanismus für automatische festplattengestützte Arrays
Konrad Rudolph
6

Ich werde mich auf die Probe stellen und vorschlagen, dass Sie zu einer Heap / Heapsort- Implementierung wechseln . Dieser Vorschlag geht mit einigen Annahmen einher:

  1. Sie steuern das Lesen der Daten
  2. Sie können mit den sortierten Daten etwas Sinnvolles tun, sobald Sie anfangen, sie zu sortieren.

Das Schöne an Heap / Heap-Sort ist, dass Sie den Heap erstellen können, während Sie die Daten lesen, und dass Sie sofort Ergebnisse erzielen können, wenn Sie den Heap erstellt haben.

Lass uns zurücktreten. Wenn Sie das Glück haben, dass Sie die Daten asynchron lesen können (dh Sie können eine Art Leseanforderung senden und benachrichtigt werden, wenn einige Daten bereit sind), können Sie einen Teil des Heaps erstellen, während Sie auf die Daten warten nächster Datenblock - sogar von der Festplatte. Oft kann dieser Ansatz den größten Teil der Kosten für die Hälfte Ihrer Sortierung hinter der Zeit begraben, die Sie für das Abrufen der Daten aufgewendet haben.

Sobald Sie die Daten gelesen haben, ist das erste Element bereits verfügbar. Je nachdem, wohin Sie die Daten senden, kann dies sehr hilfreich sein. Wenn Sie es an einen anderen asynchronen Leser oder ein paralleles Ereignismodell oder eine Benutzeroberfläche senden, können Sie Chunks und Chunks unterwegs senden.

Das heißt, wenn Sie keine Kontrolle darüber haben, wie die Daten gelesen werden, und sie synchron gelesen werden und Sie die sortierten Daten erst dann verwenden können, wenn sie vollständig ausgeschrieben sind, ignorieren Sie dies alles. :((

Siehe die Wikipedia-Artikel:

Joe
quelle
1
Guter Vorschlag. Ich habe dies jedoch bereits versucht und in meinem speziellen Fall ist der Aufwand für die Verwaltung eines Heaps größer als nur das Sammeln der Daten in einem Vektor und das Sortieren, sobald alle Daten angekommen sind.
Konrad Rudolph
5

" Radix-Sortierung ohne zusätzlichen Platz " ist ein Papier, das sich mit Ihrem Problem befasst.

eig
quelle
Sieht vielversprechend aus, obwohl das Problem tatsächlich bereits gelöst wurde. Dies geht jedoch in meine Referenzbibliothek.
Konrad Rudolph
4

In Bezug auf die Leistung sollten Sie sich allgemeinere Sortieralgorithmen für den String-Vergleich ansehen.

Momentan berührst du jedes Element jeder Saite, aber du kannst es besser machen!

Insbesondere eine Burst-Sortierung passt sehr gut in diesen Fall. Da Burstsort auf Versuchen basiert, funktioniert es als Bonus lächerlich gut für die kleinen Alphabetgrößen, die in DNA / RNA verwendet werden, da Sie keine Art von ternärem Suchknoten, Hash oder anderem Trie-Node-Komprimierungsschema in das integrieren müssen Implementierung versuchen. Die Versuche können auch für Ihr Suffix-Array-ähnliches Endziel nützlich sein.

Eine anständige Allzweckimplementierung von Burstsort ist in Source Forge unter http://sourceforge.net/projects/burstsort/ verfügbar - sie ist jedoch nicht vorhanden.

Zu Vergleichszwecken wird die unter http://www.cs.mu.oz.au/~rsinha/papers/SinhaRingZobel-2006.pdf beschriebene C-Burstsort-Implementierung für einige typische Workloads 4-5-mal schneller als QuickSort- und Radix-Sortierungen durchgeführt.

Edward KMETT
quelle
Ich muss mir auf jeden Fall Burst-Sortierung ansehen - obwohl ich im Moment nicht sehe, wie der Trie an Ort und Stelle gebaut werden könnte. Im Allgemeinen haben Suffix-Arrays Suffix-Bäume (und damit Versuche) in der Bioinformatik aufgrund überlegener Leistungseigenschaften in praktischen Anwendungen so gut wie ersetzt.
Konrad Rudolph
4

Sie sollten einen Blick auf die groß angelegte Genomsequenzverarbeitung von Dr. Kasahara und Morishita.

Zeichenfolgen, die aus den vier Nukleotidbuchstaben A, C, G und T bestehen, können für eine viel schnellere Verarbeitung speziell in Ganzzahlen codiert werden. Die Radix-Sortierung gehört zu den vielen im Buch diskutierten Algorithmen. Sie sollten in der Lage sein, die akzeptierte Antwort auf diese Frage anzupassen und eine große Leistungsverbesserung zu sehen.

Rüdiger
quelle
Die in diesem Buch vorgestellte Radix-Sortierung ist nicht vorhanden und kann daher nicht für diesen Zweck verwendet werden. Was die String-Komprimierung betrifft, mache ich das (natürlich) bereits. Meine (mehr oder weniger) endgültige Lösung (siehe unten) zeigt dies nicht, da ich sie in der Bibliothek wie normale Zeichenfolgen behandeln kann - aber der verwendete RADIXWert kann (und wird) natürlich an größere Werte angepasst werden.
Konrad Rudolph
3

Sie könnten versuchen , eine mit trie . Beim Sortieren der Daten wird der Datensatz einfach durchlaufen und eingefügt. Die Struktur ist natürlich sortiert, und Sie können sich vorstellen, dass sie einem B-Baum ähnelt (außer dass Sie anstelle von Vergleichen immer Zeiger-Indirektionen verwenden).

Das Caching-Verhalten bevorzugt alle internen Knoten, sodass Sie dies wahrscheinlich nicht verbessern werden. Sie können aber auch mit dem Verzweigungsfaktor Ihres Tries herumspielen (stellen Sie sicher, dass jeder Knoten in eine einzelne Cache-Zeile passt, ordnen Sie Trie-Knoten ähnlich einem Heap als zusammenhängendes Array zu, das eine Durchquerung der Ebene darstellt). Da Versuche auch digitale Strukturen sind (O (k) Einfügen / Suchen / Löschen für Elemente der Länge k), sollten Sie eine wettbewerbsfähige Leistung für eine Radix-Sortierung haben.

Tom
quelle
Der Versuch hat das gleiche Problem wie meine naive Implementierung: Er benötigt O (n) zusätzlichen Speicher, der einfach zu viel ist.
Konrad Rudolph
3

Ich würde eine gepackte Bit-Darstellung der Strings sortieren . Es wird behauptet, dass Burstsort eine viel bessere Lokalität als Radix-Sorten aufweist, wodurch die zusätzliche Speicherplatznutzung bei Burst-Versuchen anstelle von klassischen Versuchen gering gehalten wird. Das Originalpapier hat Maße.

Darius Bacon
quelle
2

Radix-Sort ist nicht cache-bewusst und nicht der schnellste Sortieralgorithmus für große Mengen. Sie können sehen:

Sie können auch die Komprimierung verwenden und jeden Buchstaben Ihrer DNA in 2 Bits codieren, bevor Sie ihn im Sortierarray speichern.

Rechnung
quelle
bill: Können Sie erklären, welche Vorteile diese qsortFunktion gegenüber der std::sortvon C ++ bereitgestellten Funktion hat ? Letzteres implementiert insbesondere ein hochentwickeltes Introsort in modernen Bibliotheken und erweitert die Vergleichsoperation. Ich kaufe nicht die Behauptung, dass es in den meisten Fällen in O (n) funktioniert, da dies einen Grad an Selbstbeobachtung erfordern würde, der im allgemeinen Fall nicht verfügbar ist (zumindest nicht ohne viel Aufwand).
Konrad Rudolph
Ich verwende kein c ++, aber in meinen Tests kann der Inline-QSORT dreimal schneller sein als der qsort in stdlib. Der ti7qsort ist die schnellste Sortierung für Ganzzahlen (schneller als Inline-QSORT). Sie können es auch verwenden, um kleine Daten mit fester Größe zu sortieren. Sie müssen die Tests mit Ihren Daten durchführen.
Rechnung
1

Die MSB-Radix-Sortierung von dsimcha sieht gut aus, aber Nils kommt dem Problem mit der Beobachtung näher, dass die Cache-Lokalität Sie bei großen Problemgrößen umbringt.

Ich schlage einen sehr einfachen Ansatz vor:

  1. Schätzen Sie empirisch die größte Größe, mfür die eine Radix-Sortierung effizient ist.
  2. Lesen Sie Blöcke von m Elementen, sortieren Sie sie mit Radix und schreiben Sie sie aus (in einen Speicherpuffer, wenn Sie über genügend Speicher verfügen, ansonsten aber in Dateien), bis Sie Ihre Eingabe erschöpft haben.
  3. Führen Sie die resultierenden sortierten Blöcke zusammen.

Mergesort ist der cachefreundlichste Sortieralgorithmus, den ich kenne: "Lesen Sie das nächste Element aus Array A oder B und schreiben Sie dann ein Element in den Ausgabepuffer." Es läuft effizient auf Bandlaufwerken . 2nZum Sortieren ist Platz erforderlichn Elementen , aber ich wette, dass die stark verbesserte Cache-Lokalität dies unwichtig macht - und wenn Sie eine nicht vorhandene Radix-Sortierung verwenden, benötigen Sie diesen zusätzlichen Speicherplatz trotzdem.

Bitte beachten Sie abschließend, dass Mergesort ohne Rekursion implementiert werden kann. Auf diese Weise wird das wahre lineare Speicherzugriffsmuster deutlich.

j_random_hacker
quelle
1

Es sieht so aus, als hätten Sie das Problem gelöst, aber für den Datensatz scheint es, dass eine Version einer funktionsfähigen Radix-Sortierung die "American Flag Sort" ist. Es wird hier beschrieben: Engineering Radix Sort . Die allgemeine Idee ist, 2 Durchgänge für jedes Zeichen durchzuführen - zählen Sie zuerst, wie viele von jedem Sie haben, damit Sie das Eingabearray in Bins unterteilen können. Gehen Sie dann erneut durch und tauschen Sie jedes Element in den richtigen Behälter aus. Sortieren Sie nun rekursiv jeden Behälter an der nächsten Zeichenposition.

AShelly
quelle
Tatsächlich ist die von mir verwendete Lösung sehr eng mit dem Flag-Sortieralgorithmus verbunden. Ich weiß nicht, ob es einen relevanten Unterschied gibt.
Konrad Rudolph
2
Ich habe noch nie von der American Flag Sort gehört, aber anscheinend habe ich sie so codiert: coliru.stacked-crooked.com/a/94eb75fbecc39066 Sie ist derzeit überdurchschnittlich gut std::sort, und ich bin sicher, dass ein mehrstelliger Digitalisierer noch schneller arbeiten könnte, aber meine Testsuite verfügt über Speicher Probleme (nicht der Algorithmus, die Testsuite selbst)
Mooing Duck
@KonradRudolph: Der große Unterschied zwischen der Flag-Sorte und anderen Radix-Sorten ist der Zählpass. Sie haben Recht, dass alle Radix-Sorten sehr eng miteinander verwandt sind, aber ich würde Ihre nicht als Flag-Sorte betrachten.
Mooing Duck
@MooingDuck: Ich habe mich nur von Ihrer Probe inspirieren lassen - ich steckte in meiner eigenen unabhängigen Implementierung fest, und Ihre hat mir geholfen, wieder auf Kurs zu kommen. Vielen Dank! Eine mögliche Optimierung - Ich bin hier noch nicht weit genug gekommen, um zu sehen, ob es sich noch lohnt: Wenn das Element an der Position, gegen die Sie tauschen, bereits dort ist, wo es sein muss, möchten Sie dies möglicherweise überspringen und zu einem solchen Element übergehen ist nicht. Um dies zu erkennen, ist natürlich zusätzliche Logik und möglicherweise auch zusätzlicher Speicher erforderlich. Da Swaps jedoch im Vergleich zu Vergleichen teuer sind, kann es sich lohnen, dies zu tun.
500 - Interner Serverfehler
1

Denken Sie zunächst an die Kodierung Ihres Problems. Entfernen Sie die Zeichenfolgen und ersetzen Sie sie durch eine binäre Darstellung. Verwenden Sie das erste Byte, um Länge + Codierung anzugeben. Alternativ können Sie eine Darstellung mit fester Länge an einer Vier-Byte-Grenze verwenden. Dann wird die Radix-Sortierung viel einfacher. Für eine Radix-Sortierung ist es am wichtigsten, keine Ausnahmebehandlung am Hotspot der inneren Schleife durchzuführen.

OK, ich habe ein bisschen mehr über das 4-Nary-Problem nachgedacht. Sie möchten eine Lösung wie einen Judy-Baum dafür. Die nächste Lösung kann Zeichenfolgen mit variabler Länge verarbeiten. Bei fester Länge entfernen Sie einfach die Längenbits, was es tatsächlich einfacher macht.

Ordnen Sie Blöcke mit 16 Zeigern zu. Das niedrigstwertige Bit der Zeiger kann wiederverwendet werden, da Ihre Blöcke immer ausgerichtet sind. Möglicherweise möchten Sie einen speziellen Speicherzuweiser dafür (Aufteilen des großen Speichers in kleinere Blöcke). Es gibt verschiedene Arten von Blöcken:

  • Codierung mit 7 Längenbits von Zeichenfolgen variabler Länge. Wenn sie voll sind, ersetzen Sie sie durch:
  • Die Position codiert die nächsten zwei Zeichen. Sie haben 16 Zeiger auf die nächsten Blöcke und enden mit:
  • Bitmap-Codierung der letzten drei Zeichen einer Zeichenfolge.

Für jede Art von Block müssen Sie unterschiedliche Informationen in den LSBs speichern. Da Sie Zeichenfolgen mit variabler Länge haben, müssen Sie auch das Ende der Zeichenfolge speichern, und die letzte Art von Block kann nur für die längsten Zeichenfolgen verwendet werden. Die 7 Längenbits sollten durch weniger ersetzt werden, wenn Sie tiefer in die Struktur eindringen.

Dies bietet Ihnen eine relativ schnelle und sehr speichereffiziente Speicherung sortierter Zeichenfolgen. Es wird sich etwas wie ein Versuch verhalten . Stellen Sie sicher, dass Sie genügend Komponententests erstellen, damit dies funktioniert. Sie möchten alle Blockübergänge abdecken. Sie möchten nur mit der zweiten Art von Block beginnen.

Für noch mehr Leistung möchten Sie möglicherweise verschiedene Blocktypen und eine größere Blockgröße hinzufügen. Wenn die Blöcke immer gleich groß und groß genug sind, können Sie noch weniger Bits für die Zeiger verwenden. Mit einer Blockgröße von 16 Zeigern haben Sie bereits ein Byte frei in einem 32-Bit-Adressraum. In der Judy-Baumdokumentation finden Sie interessante Blocktypen. Grundsätzlich fügen Sie Code und Engineering-Zeit für einen Kompromiss zwischen Speicherplatz (und Laufzeit) hinzu

Sie möchten wahrscheinlich mit einem 256 breiten direkten Radix für die ersten vier Zeichen beginnen. Das bietet einen anständigen Kompromiss zwischen Raum und Zeit. In dieser Implementierung erhalten Sie viel weniger Speicheraufwand als bei einem einfachen Versuch. es ist ungefähr dreimal kleiner (ich habe nicht gemessen). O (n) ist kein Problem, wenn die Konstante niedrig genug ist, wie Sie beim Vergleich mit dem Quicksort O (n log n) festgestellt haben.

Interessieren Sie sich für den Umgang mit Doppel? Mit kurzen Sequenzen wird es geben. Das Anpassen der Blöcke an die Anzahl der Zählungen ist schwierig, kann jedoch sehr platzsparend sein.

Stephan Eggermont
quelle
Ich sehe nicht, wie die Radix-Sortierung in meinem Fall einfacher wird, wenn ich eine bitreiche Darstellung verwende. Übrigens bietet das von mir verwendete Framework tatsächlich die Möglichkeit, eine bitreiche Darstellung zu verwenden, aber dies ist für mich als Benutzer der Benutzeroberfläche völlig transparent.
Konrad Rudolph
Nicht wenn du auf deine Stoppuhr schaust :)
Stephan Eggermont
Ich werde mir auf jeden Fall Judy Bäume ansehen. Vanilla-Versuche bringen jedoch nicht wirklich viel auf den Tisch, da sie sich im Grunde genommen wie eine normale MSD-Radix-Sortierung mit weniger Durchläufen über die Elemente verhalten, aber zusätzlichen Speicherplatz erfordern.
Konrad Rudolph