So überwachen/zeigen Sie den Fortschritt während einer C++ - Sortierung an

Question

Ich plane, ein interaktives C++ - Geometrieverarbeitungs-Plug-In zu schreiben, das häufig große Datenmengen sortiert. Obwohl vorläufige Hinweise darauf sprechen, dass die Sortierung nur ein oder zwei Sekunden dauern wird, würde ich es vorziehen, während dieser Zeit Fortschritte zu zeigen - d. H. Ich möchte einige Male pro Sekunde eine Fortschrittsanzeige aktualisieren. Dies wäre vorzuziehen, einen Warte-Cursor einzuschalten und den Benutzer mit einem Programm zu belassen, das für eine unbestimmte Zeitdauer einfriert (selbst wenn dies nur ein paar Sekunden ist).

Wenn ich etwas wie std :: sort verwenden würde, könnte ich die Vergleichsfunktion verwenden, um die Fortschrittsanzeige hin und wieder zu aktualisieren, aber ich hätte keine Ahnung von "Prozentsatz abgeschlossen". Ich könnte die Sortierung auch in Untersortierungen unterteilen, den Fortschritt zwischen Untersortierungen aktualisieren und dann zusammenführen. Meine beste Wette könnte sein, eine eigene Sortiermethode zu schreiben, obwohl ich nicht weiß, wie viel Aufwand es erfordert, um eine Leistung zu erhalten, die so gut wie std :: sort ist (und die Korrektheit gewährleistet). In jedem Fall würde diese Sortiermethode gelegentlich einen "Prozentsatz abgeschlossen" an eine Callback-Methode senden.

Ich habe mich gefragt, ob andere Leute dieses Problem entdeckt und gelöst haben - ich hoffe, dass es eine Sortiermethode in einer Standardbibliothek gibt, die das tut, was ich will, oder eine andere Technik, an die ich nicht gedacht habe.

Update: Danke für die tollen Antworten bisher. Es gab ein paar sehr gute Vorschläge, und ich werde die akzeptierte Antwort abwägen, bis ich die Möglichkeit hatte, die Ideen in meinem nächsten Projekt zu testen.

Update 2: Ich habe mein Projekt abgeschlossen, und dies stellte sich als kein Problem heraus (zumindest für den Kunden. Da sie die Software verkaufen werden, können sie immer noch Feedback von ihren Kunden erhalten ihre Gedanken darüber). Die Wahl einer akzeptierten Antwort war schwierig, weil es viele gute Antworten gab, aber am Ende zeigte die, die ich wählte, auf einen Wiki-Artikel über Merge Sort, der eine sehr bewegende Animation hatte. Das wäre die erste Strategie, die ich verfolgt hätte, wenn ich damit hätte weitermachen müssen.

Answer 1

Da std :: sort auf Vorlagen basiert, sollte die Quelle in einem Header verfügbar sein. Sie können eine Kopie davon erstellen und Ihren Fortschrittsrückruf einfügen. Das große Problem wird sein, wie nahe Sie der Fertigstellung sind - die meisten Sortierfunktionen basieren auf Quicksort, das nicht immer die gleiche Anzahl von Vergleichen durchführt.

Schreiben Sie Ihre eigenen Merge sort wäre eine Möglichkeit; Der Algorithmus ist einfach und die Anzahl der Schritte ist gut definiert.

Answer 2

Ich würde Ihre zweite Option empfehlen: Verwenden Sie std::sort oder eine andere Standardsortierfunktion wie qsort, und lassen Sie den Komparator seinen Fortschritt melden. Aber nicht in jedem Vergleich aktualisieren - das wäre unerträglich langsam - stattdessen aktualisieren alle (sagen wir) 100ms.

Answer 3

Verwenden Sie die observer pattern, um dem Elternteil zu signalisieren, wenn jeder Teil abgeschlossen ist. Mit dieser und der Gesamtzahl der Elemente, die sortiert werden müssen, können Sie Ihre Fortschrittsleiste in Echtzeit aktualisieren.

Answer 4

Ich denke, selbst wenn Sie Ihre eigene Art geschrieben haben, müssten Sie eine Menge sorgfältiger Messungen durchführen, wenn Sie die Fortschrittsanzeige genau haben wollten. Wenn Sie nur einen ungefähren Fortschrittsindikator wünschen, können Sie einen Messwert wie "durchschnittliche Entfernung zwischen verglichenen Elementen" oder "Anzahl der Vergleiche im Vergleich zur durchschnittlich erwarteten Zahl für Quicksort" als Messwert verwenden und die bereits erwähnte Vergleichsidee implementieren.

Und ja, ich nehme an, dass Sie kein kompletter Idiot sind und nicht planen, den Fortschrittsindikator bei jedem Vergleich zu aktualisieren. Wenn Sie das tun würden, würden Sie viel mehr Zeit mit dem Fortschritt verbringen als mit dem Sortieren.

Als Beispiel würden Sie im Allgemeinen etwa n log2 n Operationen für Quicksort erwarten. Die Analyse, wie viele Vergleiche beteiligt sind, ist detaillierter und kann genauer sein als diese allgemeine Messung, aber für die Zwecke dieses Beispiels nehmen wir einfach an. So können Sie Vergleiche zählen und number_of_comparisons/(n log2 n) als Ihre Schätzung des Fortschritts melden.

Da dies nur ein durchschnittlicher Indikator ist, würde ich ein paar Experimente durchführen und sehen, wie weit Ihre Schätzung aus ist, und werfen einige Fudge-Faktoren, um es mit dem durchschnittlichen erwarteten Fall in Einklang zu bringen. Du könntest auch einen Fortschrittsbalken haben, der auf die Ungewissheit hinweist, indem du eine Art "Das ist, wo ich denke, dass ich fertig werde" habe. Indikator und etwas Platz nach dem Indikator.

Auch wenn Sie Ihre eigene Sortierung verwendet haben und ein scheinbar präziseres Maß entwickelt haben, wird der Fortschrittsbalken immer noch nicht korrekt aktualisiert und der Effekt wäre ähnlich. Der einzige Weg, wie Sie sicher wissen, wie lange Ihre Sortierung dauert, ist, wenn Sie eine etwas langsamere, aber wirklich vorhersehbare Art verwenden. In diesem Fall können Sie vorhersagen, wie lange es von der Anzahl der Elemente dauern wird Sortierung, die in bestimmten Fällen weniger vorhersagbares Verhalten aufweist. In diesem Fall gibt es keinen wirklichen Weg, um eine perfekt genaue Fortschrittsanzeige zu erhalten.

Vorhersagbarkeit der Teilaufgaben und Vorhersagbarkeit der Gesamtzahl der Vergleiche sind eng miteinander verknüpft. Also glaube ich wirklich nicht, dass Teilaufgaben ein besseres Maß als die Gesamtzahl der Vergleiche machen.

Wenn Sie Ihre eigene Art und Vorhersagbarkeit verwenden möchten, ist Ihr höchstes Ziel, gehen Sie für heapsort. Es ist immer noch eine O(n log2 n) Sorte, und es ist nahe daran, eine Mindestvergleichssorte zu sein (oder so erinnere ich mich an Knuth). Es benötigt auch eine sehr vorhersagbare Menge an Zeit, um unabhängig von dem gefütterten Datensatz abgeschlossen zu werden. Es ist eines der langsameren O(n log2 n) Sorten, aber immer noch.

Wie einer Ihrer Kommentatoren erwähnt, lösen Sie möglicherweise ein Problem, das nicht wirklich existiert. Führen Sie zuerst einige Experimente durch. Das Problem ist eine lustige intellektuelle Herausforderung, unabhängig von ihrer Nützlichkeit. :-)

Answer 5

Ich sehe dein Problem wie folgt:

1. Sie wollen diskrete Ereignisse während eines einzigen kontinuierlichen Verfahren entlassen werden.
2. Diese Unterteilung dient nur dazu, dem Benutzer zu sagen, dass die Dinge in Arbeit sind.

Meine Vorschläge sind:

1. ein Ladesymbol von etwas verwenden wie http://ajaxload.info/, oder wenn es nicht eine GUI-basierten Umgebung, nur Laden buchstabieren. Da das Ereignis weniger als 2 Sekunden dauert, ist dies kein Problem. Aufhänge werden erwartet, wenn die Wartezeit 10 Sekunden überschreitet.

2. Das Schreiben einer eigenen Sortiermethode bringt viele Probleme mit der Thread-Sicherheit mit sich, die zu Problemen führen können, wenn Ihr Code Multithreading verwendet oder dies in Zukunft tun wird.

3.Another wichtige Informationen, die Sie berücksichtigen sollten, wie schlecht aus sein, um die Daten jedes Mal wenn Sie sortieren wollen, so in der Tat werden Sie den Grad der Zufälligkeit vorhanden sein messen, und die erwartete Anzahl von Berechnungen das müssen Sie tun. Sie können diese Informationen als Indikator dafür verwenden, wie viele Swaps erforderlich sind, auf die wiederum bei der Iteration durch die Sortierung zurückgegriffen werden kann. Spielen Sie mit den Daten herum.

Answer 6

Einsatz brutaler Gewalt :)

int elem_num = raw_data.size(); 
int percentage_delta = 100/(elem_num/20); 
int percentage = 0; 
int i = 0; 
std::multiset<Elem*> sorted_data(&compareElemFunc); 
foreach(Elem& elem, raw_data) 
{ 
    sorted_data.insert(&elem); 
    if(i%20) 
    { 
     updateProgressBar(percentage); 
     percentage += percentage_delta; 
    } 
    i++; 
} 
//now, your data is perfectly sorted, iterate through sorted_data 

(falls Sie nicht wollen, Ihr eigenes std :: sort() implementieren, und da ich komplett Anforderungen fehlt bin)

Answer 7

I don‘ t empfehlen zu versuchen, std :: sort auseinander zu hacken. Dies wird normalerweise mit Introsort implementiert und ist eine extrem schnelle NLogN-Operation. Das Konstruieren des zu sortierenden Containers ist normalerweise teurer als das Sortieren der Daten.

Wenn Sie jedoch einen Fortschrittsbalken implementieren möchten, empfehle ich Ihnen, die Sortierung in einen separaten Thread einzufügen. Normalerweise sind Multithread-Anwendungen schwieriger zu schreiben und zu verwalten als Singlethread-Anwendungen, aber Sie können es auf eine Art und Weise tun, in der es nicht für diesen Fortschrittsbalkenfall ist. Ihre Anwendung kann immer noch überwiegend single-threaded sein, ohne dass gleichzeitige Operationen ausgeführt werden, mit Ausnahme dieser Fortschrittsanzeige und wahrscheinlich einer Ereignisbehandlung, um die Benutzeroberfläche ansprechbar zu halten. Wenn Sie bereit sind, die Daten zu sortieren, feuern Sie einfach einen anderen Thread ab und legen Sie den Haupt-Thread in eine Warteschleife, bis der Sortier-Thread fertig ist, schlafen Sie hier und da und aktualisieren Sie den Fortschrittsbalken in der Zwischenzeit.

Sie können diesen nicht-intrusiven Ansatz für jede Art von zeitraubendem Betrieb verallgemeinern, ohne die Aufrufe von update_progress_bar() in Ihren Code zu streuen oder in die Implementierungen von std :: sort zu graben oder Räder neu zu erfinden. Da sich der Hauptthread in einem Warte-/Aktualisierungsstatus befindet und daher in gewisser Weise blockiert, bis der Arbeitsthread beendet ist, haben Sie keine Probleme im Zusammenhang mit Multithreading (die Thread-Synchronisation muss auf freigegebene Ressourcen in Ihrem gesamten Thread zugreifen) Anwendung mit Ausnahme des Fortschrittszählers, Race Conditions, Dead Locks, etc). Es ist auch der reibungsloseste Fortschrittszähler, den Sie implementieren können, da er gleichzeitig aktualisiert wird.

Wenn Sie über die Effizienz beim Sperren des Fortschrittszählers besorgt sind, verwenden Sie einfach atomare Operationen, um sie zu erhöhen.

Um festzustellen, wie weit der Sortieralgorithmus fortgeschritten ist, gibt es mehrere Möglichkeiten. Einer davon ist, dass er einmal mit der Größe der Daten ausgeführt wird, die Sie haben, und versuchen Sie, die Zeit vorherzusagen, die es für nachfolgende Durchläufe benötigen würde. Das ist zwar völlig nicht aufdringlich, aber ein wenig schwierig, aber wenn es richtig gemacht wird, wird es den Fortschritt genauer überwachen, als einen Zähler in regelmäßigen Intervallen zu erhöhen (was die Tatsache auslässt, dass Intervalle nicht einmal einen bestimmten Zeitbetrag benötigen). Der zweite Ansatz, der einfacher, aber ein bisschen böser ist, besteht darin, das Vergleichsprädikat zu modifizieren, um einen Fortschrittszähler zu erhöhen. Prädikate mit Staat zu machen ist im Allgemeinen verpönt, aber es ist weniger böse als zu versuchen, einen eigenen Introsort zu implementieren, nur weil man einen Fortschrittszähler haben möchte.

Auch wenn Ihr Introsort so lange dauert, muss ich mich fragen, speichert Ihr Container diese Dreiecksobjekte oder Zeiger auf sie? Wenn der erste, sollten Sie letzteres betrachten, da es die Dinge dramatisch beschleunigen sollte.