Bester Algorithmus zur Prüfung, ob ein Vektor sortiert ist

Question

Wie kann man am besten überprüfen, ob ein std::vector sortiert ist? Gibt es etwas Schnelleres als eine Schleife, die prüft, ob v[i]<=v[i+1] ? Ist es schneller/sauberer mit Iteratoren? Oder ist es tatsächlich besser, einfach die sort jedes Mal (obwohl der Fall "v ist bereits sortiert" recht häufig vorkommt)?

Wir können sicher davon ausgehen, dass der Vektor nur PODs enthält, in der Regel float s und manchmal double s und int s.

Die Größe des Vektors ist nicht trivial (in der Regel einige tausend Elemente), aber nicht extrem (keine Gigabyte-Größe).

• In einigen Fällen sortieren wir den Vektor unmittelbar danach, in anderen Fällen jedoch nicht (das ist ein Fehlerfall unseres Algorithmus).
• wir verwenden bereits ein Flag "IsSorted", wann immer dies möglich ist.

Answer 1

Gibt es etwas Schnelleres als eine Schleife die überprüft, ob v[i]<=v[i+1] ist?

Nein.

Wenn Sie dies häufig überprüfen möchten, sollten Sie eine Wrapper-Klasse erstellen, die ein Flag "sortiert" enthält, das zunächst auf False gesetzt wird, sobald ein Element hinzugefügt wird, und eine Member-Funktion sort() hinzufügen, die das Flag nach dem Sortieren auf True setzt.

Answer 2

Der beste Weg ist die Verwendung von std::is_sorted :

is_sorted(v.begin(), v.end())

:-)

Answer 3

Mehrere Cpu-Kerne in Betracht ziehen

Dies hängt von Ihrer Plattform und der Anzahl der Elemente im Vektor ab. Sie müssen einen Benchmark durchführen, um das Beste herauszufinden.

Es ist nicht möglich, darauf zu antworten: Gibt es etwas Schnelleres als eine Schleife, die überprüft, ob v[i]<=v[i+1] ist?
Mit: Nein.

Weil... Computer heutzutage mehrere Prozessoren/Kerne/Hyperthreading haben. Es kann also sehr viel schneller sein, den Paralellismus im Computer auszunutzen, indem man die Arbeit der Überprüfung auf mehrere Threads aufteilt, so dass jede CPU einen kleinen Bereich parallel überprüfen kann.

Es ist wahrscheinlich am besten, dies über eine Bibliotheksfunktion zu tun, anstatt es selbst zu implementieren. Neue Versionen von Bibliotheken werden den Parallismus ausnutzen. Wenn Sie sich also für std::sort entscheiden, werden Sie wahrscheinlich feststellen, dass neuere Implementierungen der STL die Operation parallel für Sie durchführen, ohne dass Sie sich darum kümmern müssen. Ich weiß nicht, ob es bereits verfügbare Versionen der STL gibt, die dies tun, aber es lohnt sich, an den Bibliotheksfunktionen festzuhalten, so dass diese Optimierung für Sie da ist, wenn Sie auf eine Version aktualisieren, die dies tut, ohne dass Sie irgendwelche Änderungen vornehmen müssen.

Answer 4

std::adjacent_find(v.begin(), v.end(), std::greater<type>()) == v.end()

Answer 5

Natürlich kenne ich Ihre Problemdomäne nicht, also ignorieren Sie mich bitte, wenn das, was ich sage, nicht relevant ist, aber es scheint mir, dass, wenn ich verlange, dass eine Sammlung immer sortiert ist, wenn ich auf sie zugreife, eine natürlich unsortierte Sammlung wie eine vector<T> ist vielleicht nicht die beste Wahl.