Problem

Angenommen, ich habe ein großes Array von Bytes (denken Sie an bis zu 4 GB), das einige Daten enthält. Diese Bytes entsprechen so unterschiedlichen Objekten, dass jeders Bytes (denkes bis zu 32) bilden ein einzelnes Objekt. Eine wichtige Tatsache ist, dass diese Größes ist für alle Objekte gleich, die nicht in den Objekten selbst gespeichert sind und zum Zeitpunkt der Kompilierung nicht bekannt sind.

Im Moment sind diese Objekte nur logische Entitäten, keine Objekte in der Programmiersprache. Ich habe einen Vergleich für diese Objekte, der aus einem lexikografischen Vergleich der meisten Objektdaten besteht, mit einigen unterschiedlichen Funktionen, um die Bindungen unter Verwendung der verbleibenden Daten zu lösen. Jetzt möchte ich diese Objekte sortiereneffizient (Dies wird wirklich ein Engpass der Anwendung sein).

Ideen soweit

Ich habe über verschiedene Möglichkeiten nachgedacht, um dies zu erreichen, aber jede davon scheint einige unglückliche Konsequenzen zu haben. Sie müssen nicht unbedingt alles lesen.Ich habe versucht, die zentrale Frage jedes Ansatzes fett zu drucken. Ob Sie werden einen dieser Ansätze vorschlagen,dann Ihre Antwort sollte auch auf die entsprechenden Fragen antworten.

1. C Quicksort

Natürlich ist der C-Quicksort-Algorithmus auch in C ++ - Anwendungen verfügbar. Die Signatur passt fast perfekt zu meinen Anforderungen. Die Tatsache, dass die Verwendung dieser Funktion das Inlining der Vergleichsfunktion verhindert, bedeutet jedoch, dass jeder Vergleich einen Funktionsaufruf-Overhead mit sich bringt. Ich hatte auf einen Weg gehofft, das zu vermeiden.Irgendeine Erfahrung darüber, wie Cqsort_r Im Vergleich zu STL in Bezug auf die Leistung wäre sehr zu begrüßen.

2. Indirektion mit Objekten, die auf Daten zeigen

Es wäre einfach, eine Reihe von Objekten zu schreiben, die Zeiger auf ihre jeweiligen Daten enthalten. Dann könnte man diese sortieren. Hierbei sind zwei Aspekte zu berücksichtigen. Einerseits würde das Bewegen von Zeigern anstelle aller Daten weniger Speicheroperationen bedeuten. Andererseits würde ein Nichtverschieben der Objekte wahrscheinlich die Speicherlokalität und damit die Cache-Leistung beeinträchtigen. Die Wahrscheinlichkeit, dass die tieferen Ebenen der Rekursion von Schnellsortierungen tatsächlich über einige Cacheseiten auf alle ihre Daten zugreifen könnten, würde fast vollständig verschwinden. Stattdessen würde jede zwischengespeicherte Speicherseite nur sehr wenige verwendbare Datenelemente liefern, bevor sie ersetzt wird.Wenn jemand etwas über den Kompromiss zwischen Kopieren und Speicherort erfahren könnte, wäre ich sehr froh.

3. Benutzerdefinierte Iterator-, Referenz- und Wertobjekte

Ich habe eine Klasse geschrieben, die als Iterator über den Speicherbereich dient. Das Dereferenzieren dieses Iterators ergibt keine Referenz, sondern ein neu konstruiertes Objekt, um den Zeiger auf die Daten und die Größe zu haltens die bei der Konstruktion des Iterators gegeben ist. So können diese Objekte verglichen werden, und ich habe sogar eine Implementierung vonstd::swap für diese. Leider sieht es so ausstd::swap ist nicht genug fürstd::sort. In einigen Teilen des Prozesses verwendet meine gcc - Implementierung die Einfügesortierung (wie in implementiert)__insertion_sort im Ordnerstl_alog.h), der einen Wert aus der Sequenz verschiebt, eine Zahl um einen Schritt verschiebt und dann den ersten Wert an der entsprechenden Position in die Sequenz zurückschiebt:

          typename iterator_traits<_RandomAccessIterator>::value_type
            __val = _GLIBCXX_MOVE(*__i);
          _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
          *__first = _GLIBCXX_MOVE(__val);

Kennen Sie eine Standardsortierungsimplementierung, die keinen Werttyp erfordert, aber nur mit Swaps arbeiten kann?

Ich bräuchte also nicht nur meine Klasse, die als Referenz dient, sondern auch eine Klasse, die einen temporären Wert enthält. Und da die Größe meiner Objekte dynamisch ist, müsste ich sie auf dem Heap zuweisen, was bedeutet, dass die Speicherzuweisungen genau in den Blättern des Wiederherstellungsbaums erfolgen. Vielleicht wäre eine Alternative ein vaue-Typ mit einer statischen Größe, die groß genug sein sollte, um Objekte der Größen aufzunehmen, die ich derzeit unterstützen möchte. Aber das würde bedeuten, dass die Beziehung zwischen den beiden noch härter wirdreference_type und dasvalue_type der Iteratorklasse. Und es würde bedeuten, dass ich diese Größe für meine Anwendung aktualisieren müsste, um eines Tages größere Objekte zu unterstützen. Hässlich.

Wenn Sie sich einen sauberen Weg vorstellen können, um den obigen Code zum Manipulieren meiner Daten zu erhalten, ohne Speicher dynamisch zuweisen zu müssen, wäre dies eine großartige Lösung. Ich verwende bereits C ++ 11-Funktionen, daher ist die Verwendung von Verschiebungssemantik oder Ähnlichem kein Problem.

4. Benutzerdefinierte Sortierung

Ich dachte sogar darüber nach, QuickSort neu zu implementieren. Vielleicht könnte ich die Tatsache ausnutzen, dass mein Vergleich größtenteils ein lexikografischer Vergleich ist, d. H. Ich könnte Sequenzen nach dem ersten Byte sortieren und nur zum nächsten Byte wechseln, wenn das erste Byte für alle Elemente gleich ist. Die Details dazu habe ich noch nicht ausgearbeitet, aberWenn jemand eine Referenz, eine Implementierung oder sogar einen kanonischen Namen als Schlüsselwort für eine solche byteweise lexikografische Sortierung vorschlagen kann, würde ich mich sehr freuen. Ich bin immer noch nicht davon überzeugt, dass ich mit vertretbarem Aufwand die Leistung der STL-Template-Implementierung übertreffen könnte.

5. Völlig anderer Algorithmus

Ich weiß, dass es gibtviele viele Arten von Sortieralgorithmen gibt. Einige von ihnen passen vielleicht besser zu meinem Problem.Radix Art fällt mir zuerst ein, aber ich habe das noch nicht wirklich durchdacht.Wenn Sie einen Sortieralgorithmus vorschlagen können, der besser zu meinem Problem passt, tun Sie dies bitte. Am liebsten mit Umsetzung, aber auch ohne.

Frage

Meine Frage lautet also im Grunde:
"Wie würden Sie Objekte mit dynamischer Größe im Heapspeicher effizient sortieren?"

Jede Antwort auf diese Frage, die auf meine Situation zutrifft, ist gut, unabhängig davon, ob sie mit meinen eigenen Ideen zusammenhängt oder nicht. Antworten auf die fett markierten Einzelfragen oder andere Erkenntnisse, die mir bei der Entscheidung zwischen meinen Alternativen helfen könnten, wären ebenfalls hilfreich, insbesondere wenn keine eindeutige Antwort auf einen einzelnen Ansatz gefunden wird.