Ich verwende stable_sort , um eine große vector zu sortieren.
Die Sortierung dauert einige Sekunden (etwa 5-10 Sekunden), und ich möchte dem Benutzer einen Fortschrittsbalken anzeigen, der zeigt, wie weit die Sortierung bisher erfolgt ist.
Aber (selbst wenn ich meine eigene Sortierroutine schreiben sollte), wie kann ich sagen, wie viel Fortschritt ich gemacht habe und wie viel mehr noch zu tun ist?
Ich brauche es nicht, um genau zu sein, aber ich muss es "vernünftig" (d. h. ziemlich linear, nicht gefälscht, und sicher nicht rückwärts).
Die Standardbibliotheksortierung verwendet eine vom Benutzer bereitgestellte Vergleichsfunktion, sodass Sie einen Vergleichszähler einfügen können. Die Gesamtzahl der Vergleiche für Quicksort / Introsort oder Mergesort liegt sehr nahe bei log 2
Da Sie Mergesort verwenden, ist die Vergleichszahl ein sehr präzises Maß für den Fortschritt. Es kann etwas nichtlinear sein, wenn die Implementierung Zeit benötigt, um den Vektor zwischen Vergleichsläufen zu permutieren, aber ich bezweifle, dass Ihre Benutzer die Nichtlinearität sehen werden (und wir sind sowieso alle dazu gewöhnt, nichtlineare Fortschrittsbalken zu verfälschen :)).
Quicksort / Introsort würde mehr Varianz zeigen, abhängig von der Art der Daten, aber selbst in diesem Fall ist es besser als nichts, und Sie könnten immer einen Fudge-Faktor aufgrund von Erfahrung hinzufügen.
Ein einfacher Zähler in Ihrer Vergleichsklasse kostet Sie praktisch nichts. Persönlich würde ich nicht einmal versuchen, es zu sperren (die Schlösser würden die Leistung beeinträchtigen); Es ist unwahrscheinlich, dass es in einen inkonsistenten Zustand gerät, und der Fortschrittsbalken wird sowieso nicht starten, wenn er Eidechsen ausstrahlt, nur weil er eine inkonsistente Fortschrittszahl erhält.
Teilen Sie den Vektor in mehrere gleiche Abschnitte auf, die Menge hängt von der Granularität der Fortschrittsberichte ab, die Sie wünschen. Sortieren Sie jeden Abschnitt einzeln. Fangen Sie dann an, mit std::merge zu verschmelzen. Sie können Ihren Fortschritt nach dem Sortieren jedes Abschnitts und nach jedem Zusammenführen melden. Sie müssen experimentieren, um festzustellen, wie viel Prozent die Sortierung der Abschnitte im Vergleich zu den Mergings zählen sollte.
Bearbeiten:
Ich habe einige eigene Experimente gemacht und festgestellt, dass die Verschmelzung im Vergleich zur Sortierung unbedeutend ist, und das ist die Funktion, die ich mir ausgedacht habe:
%Vor%Die stabile Sortierung basiert auf merge sort. Wenn Sie Ihre eigene Version von merge sort dann geschrieben haben (Ignorieren einige Beschleunigung Tricks) Sie würden sehen, dass es aus Log N besteht. Jeder Durchgang beginnt mit 2 ^ k sortierten Listen und erzeugt 2 ^ (k-1) Listen, wobei die Sortierung abgeschlossen ist, wenn zwei Listen zu einer zusammengeführt werden. Sie könnten also den Wert von k als Indikator für den Fortschritt verwenden.
Wenn Sie Experimente ausführen wollten, könnten Sie das Vergleichsobjekt instrumentieren, um die Anzahl der durchgeführten Vergleiche zu zählen, und versuchen, festzustellen, ob die Anzahl der vorgenommenen Vergleiche ein einigermaßen vorhersagbares Vielfaches von n log n ist. Dann können Sie den Fortschritt verfolgen, indem Sie die Anzahl der durchgeführten Vergleiche zählen.
(Beachten Sie, dass Sie bei der stabilen C ++ - Sortierung hoffen müssen, dass sie genügend Speicher findet, um eine Kopie der Daten zu speichern. Andernfalls gehen die Kosten von N log N zu vielleicht N (log N) ^ 2 und Ihre Vorhersagen werden viel zu optimistisch sein).
Wählen Sie eine kleine Teilmenge von Indizes und zählen Sie Inversionen. Sie kennen ihren maximalen Wert, und Sie wissen, wenn Sie fertig sind, ist der Wert gleich Null. Sie können diesen Wert also als "Fortschritt" verwenden. Sie können es sich als Maß für die Entropie vorstellen.
Einfachster Weg: Sortieren Sie einen kleinen Vektor und extrapolieren Sie die Zeit unter der Annahme von O (n log n) Komplexität.
t (n) = C · n · log (n) ⇒ t (n1) / t (n2) = n1 / n <2> log (n1) / log (n2)
Wenn das Sortieren von 10 Elementen 1 μs dauert, benötigen 100 Elemente 1 μs * 100/10 * log (100) / log (10) = 20 μs.
Quicksort ist grundsätzlich
Die ganze Arbeit wird im Partitionsschritt erledigt. Sie könnten die äußere Partition direkt machen und dann den Fortschritt melden, wenn der kleinste Teil fertig ist. Es würde also einen zusätzlichen Schritt zwischen 2 und 3 geben.
Hier ist ein Code.
%Vor%