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, wenn Sie einen Wartecursor einschalten und den Benutzer mit einem Programm belassen, das für eine unbestimmte Zeitdauer einfriert (selbst wenn dies nur ein paar Sekunden dauert).
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 angetroffen 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 auf die akzeptierte Antwort warten, 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, erhalten sie möglicherweise noch Feedback von ihren Kunden, die ihre Meinung darüber ändern werden). 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.
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.
Das Schreiben Ihrer eigenen Zusammenführungssortierung wäre eine Möglichkeit; Der Algorithmus ist einfach und die Anzahl der Schritte ist gut definiert.
Ich denke, selbst wenn Sie Ihre eigene Art geschrieben haben, müssten Sie eine Menge sorgfältiger Messungen durchführen, wenn Sie möchten, dass die Fortschrittsanzeige genau ist. Wenn Sie nur einen ungefähren Fortschrittsindikator wünschen, können Sie eine Metrik wie "durchschnittliche Entfernung zwischen verglichenen Elementen" oder "Anzahl der Vergleiche im Vergleich zur durchschnittlich erwarteten Zahl für Quicksort" als Metrik verwenden und die von Ihnen bereits erwähnte Vergleichsidee implementieren / p>
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 damit verbringen, den Fortschritt als das Sortieren anzuzeigen.
Als Beispiel würden Sie im Allgemeinen ungefähr 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 Fortschrittsschätzung angeben.
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 einige Fudge-Faktoren einwerfen, um sie mit dem durchschnittlichen erwarteten Fall in Übereinstimmung 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 Sorte verwendet haben und eine scheinbar präzisere Maßnahme entwickelt haben, würde der Fortschrittsbalken immer noch nicht reibungslos aktualisiert und der Effekt wäre ähnlich. Der einzige Weg, wie Sie sicher wissen, wie lange Ihre Sortierung dauern wird, 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, eine perfekt genaue Fortschrittsanzeige zu erhalten.
Die Vorhersagbarkeit der Teilaufgaben und die 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 Sorte verwenden möchten und Vorhersagbarkeit Ihr höchstes Ziel ist, gehen Sie zu heapsort . Es ist immer noch ein O(n log2 n) sort, 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 eine der langsameren O(n log2 n) Sortierungen, aber immer noch.
Wie einer Ihrer Kommentatoren erwähnt hat, könnten Sie ein Problem lösen, das eigentlich nicht existiert. Führen Sie zuerst einige Experimente durch. Das Problem ist eine lustige intellektuelle Herausforderung, unabhängig von ihrer Nützlichkeit. : -)
Ich würde Ihre zweite Option empfehlen: Verwenden Sie std::sort oder eine andere Standard-Sortierfunktion wie qsort , und lassen Sie den Vergleicher seinen Fortschritt melden. Aber nicht in jedem Vergleich aktualisieren - das wäre unerträglich langsam - stattdessen aktualisieren Sie alle (sagen wir) 100ms.
Ich sehe dein Problem wie folgt:
Meine Vorschläge sind:
Verwenden Sie ein Ladesymbol von etwas wie Ссылка , oder wenn es sich nicht um eine GUI-basierte Umgebung handelt, buchstabieren Sie einfach das Laden. Da das Ereignis weniger als 2 Sekunden dauert, ist dies kein Problem. Aufhängungen werden erwartet, wenn die Wartezeit 10 Sekunden überschreitet.
Das Schreiben Ihrer eigenen Sortiermethode bringt viele Probleme mit der Thread-Sicherheit mit sich, die Probleme verursachen können, wenn Ihr Code Multithreading verwendet oder in Zukunft dazu verpflichtet ist.
3.Eine weitere wichtige Information, die Sie berücksichtigen sollten, wie schlecht die Daten bei jeder Sortierung ausfallen, ist, dass Sie den Grad der Zufälligkeit und die erwartete Anzahl von Berechnungen messen machen. 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. Spiel mit den Daten herum.
Verwenden Sie das Beobachtermuster , um beim Abschluss jedes Teils ein Signal an das übergeordnete Objekt zu senden. Mit dieser und der Gesamtzahl der Elemente, die sortiert werden müssen, können Sie Ihre Fortschrittsleiste in Echtzeit aktualisieren.
Ich empfehle nicht, std :: sort auseinander zu hacken. Dies wird normalerweise mit Introsort implementiert und ist eine extrem schnelle NLogN-Operation. Das Konstruieren des Containers, den Sie sortieren möchten, 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 einiger Ereignisbehandlung, um die Benutzeroberfläche ansprechbar zu halten. Wenn Sie bereit sind, die Daten zu sortieren, feuern Sie einfach einen anderen Thread ab, und führen Sie den Haupt-Thread in eine Warteschleife, bis der Sortier-Thread fertig ist, schlafen 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 zu versuchen, 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-Synchronisierung 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 sich Sorgen um die Effizienz machen, die mit dem Sperren des Fortschrittszählers verbunden ist, verwenden Sie einfach atomare Operationen, um sie zu erhöhen.
Um festzustellen, wie weit der Sortieralgorithmus fortgeschritten ist, gibt es mehrere Möglichkeiten, dies zu tun. 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. Making Prädikate mit Staat ist im Allgemeinen verpönt, aber es ist weniger böse als zu versuchen, Ihre eigenen Introsort, nur weil Sie einen Fortschrittszähler wollen.
Auch wenn Ihr Introsort so lange braucht, muss ich mich wundern, speichert Ihr Container diese dreieckigen Objekte oder Zeiger auf sie? Wenn das erste, sollten Sie letzteres betrachten, da es die Dinge dramatisch beschleunigen sollte.
Tags und Links algorithm c++ sorting progress-bar