Heute habe ich mich gefragt, was der kürzest mögliche Code sein könnte, um alle Werte in einem sortierten Vektor std::vector<double> zu erhalten, die größer oder gleich a und kleiner oder gleich b sind.
Mein erster Ansatz war etwas wie das Folgende:
%Vor%Mein zweiter Gedanke war etwas sehr einfaches wie das folgende:
%Vor%Wenn man jedoch den Fall betrachtet, dass nur kleine Teile von einem sehr großen Vektor entfernt werden, kann dies zu Effizienzproblemen führen.
Nun frage ich mich, ob es da noch bessere Möglichkeiten gibt?
Nicht kürzer, aber im Allgemeinen effizienter: Verwenden Sie std::lower_bound , um den Anfang des "interessanten" Intervalls zu finden, und kopieren Sie weiter, solange die Elemente unter dem maximalen Wert liegen. Auf diese Weise finden Sie schnell (O (log N)) den Start selbst für große Vektoren und Sie verschwenden keine Zeit mit einer binären Suche wieder auf der Suche nach dem Ende des Intervalls - Sie werden es tun finde es trotzdem während der Kopierschleife.
Die möglichen zusätzlichen Vergleiche sind sowieso praktisch frei, da sich double im Vergleich extrem billig sind, die Verzweigung ist gut vorhergesagt (es ist immer die gleiche bis zum Ende der Kopie) und hängt von bereits im Cache befindlichen Daten ab; Vergleichen Sie mit einer zusätzlichen binären Suche, die im Speicher "herumspringt" (schlechtere Cache-Lokalität) und weniger vorhersagbare Verzweigungen aufweist.
Dies kann ähnlich wie bei% code% mithilfe von STL-Algorithmen beschrieben werden, aber ich bin mir nicht sicher, ob es sich um eine Verbesserung handelt.
%Vor%Sie könnten Ihre Funktion STL-Stil schreiben und es mit jedem Container beliebigen Typs (und es wird eleganter imho) arbeiten.
%Vor% %Vor%Hinweis: Beispiele verwenden C ++ 17 Template-Argument Abzug für Klassenvorlagen und strukturierte Bindungen .
Sobald Sie wissen, wo Ihr Intervall beginnt, müssen Sie nicht erneut durch den Lochvektor suchen, um den End-Iterator zu finden. Beginnen Sie mit der Suche nach start_iterator anstelle von
Andere Optimierungen wären inhaltsabhängig. Z.B. Wenn Sie wissen, dass das letzte Element in Ihrem Intervall eher am Ende des Vektors liegt, wäre es sinnvoller, es rückwärts zu durchlaufen.
Sie sollten auch das Intervall zuerst prüfen, um unnötige Ausführung zu verhindern, wenn a größer oder gleich b ist.