Gibt es einen einfachen Weg, dies ohne eine for-Schleife oder viele ifs und elses zu tun.
Also zum Beispiel ..
%Vor% Muss ich eine verschachtelte Schleife von -5 bis +5 setzen? Oder kann ich std::any_of vielleicht
Trotz der Beschreibung der Beschreibung ist die Komplexität linear , da die innere Schleife (falls vorhanden) eine konstante Anzahl von Malen wiederholt (und nicht von der Anzahl der Daten abhängt).
Da Sie vorschlagen, dass Ihre Daten eine Array-Form haben (zusammenhängend und zufällig indexierbar) und die Verwendung von verschachtelten Schleifen ist in der Tat die einfachste und direkteste Möglichkeit, von allen Optimierungsmöglichkeiten und Prozessor-Caching zu profitieren. Was auch immer "dynamisch sortierte" Containerschweller aufgrund der verteilten Natur der Daten schlecht ausführen.
Ich werde höchstwahrscheinlich
tun %Vor%Die innere Schleife wird vollständig mit zwischengespeicherten Daten ausgeführt (und hängt nicht von N ab, also trägt sie nicht zur Komplexität bei). Mit der heutigen CPU klappt es wahrscheinlich schneller, die Daten im Set-ähnlichen Container (mit nicht zusammenhängendem Speicher) irgendwie zu sortieren.
Trotz der Eleganz vieler Anfangs- / Endanflüge gewinnt die alte KISS-Indexierung.
Sie können das Prädikat array[j]==value sowie 5 (und 10 == 2 * 5) ohne Kosten parametrisieren (eine Template-Funktion wird inline), was dies noch allgemeiner macht.
Wenn Sie die innere Schleife nicht verzweigen wollen, können Sie sie sogar schneller machen mit
%Vor% Wo die Schleife mit 11 Elementen in zwei Hälften geteilt wird (um zu vermeiden, nach j == i zu suchen) und das Inkrement auf good wird funktionell "ohne Verzweigungen" berechnet. Dies wird auch zu einer schnelleren Ausführung bei vorhersagenden Rohrleitungs-Prozessoren führen.
BEARBEITEN
Sieht so aus, als hätte ich nicht verstanden, dass nur ein gleicher Wert ausreicht (nicht alle).
Wenn das der Fall ist, können Sie nach good!=0 suchen, aber Sie können sogar eine Abkürzung machen:
Dadurch werden die Schleifen unterbrochen, sobald eine Übereinstimmung gefunden wird, aber die Schleife wird nicht mehr rollbar.
Wenn Sie && !good entfernen, werden die Schleifen nicht abgeschnitten, aber sie können ausgeführt werden, bis das Ende schneller ist als die Prüfung zum Ausschneiden oder nicht.
Wenn Sie die Schleifen abkürzen, können Sie = anstelle von |= verwenden, wenn Sie keine Abkürzung verwenden, hat die Verwendung von bool keinen Vorteil: |= von einem Compiler-Standpunkt ist komplizierter als +=
In Bezug auf Lesbarkeit bevorzuge ich die doppelten for -Schleifen.
Im Hinblick auf Leistung würde ich Folgendes verwenden, das die minimum n+5 Iterationen (für scope = 5) ohne zusätzliche Datenstrukturen ausführt. stark>.
Alles in allem O(n) Komplexität und O(1) Speicher.
hat für diesen main gut funktioniert:
%Vor% Sie könnten wahrscheinlich std::any_of verwenden, aber dann müssten Sie
Schließen Sie den Wert aus, in dem Sie sich befinden (oder es wird übereinstimmen)
benötigen wahrscheinlich zwei Aufrufe von std::any_of . Ich würde wahrscheinlich einfach
Verwende std::count_if :
Die Verwendung von std::max und std::min soll sicherstellen, dass Sie dies nicht tun
geh raus. Alternativ könnten Sie bei begin()
+ 5 beginnen und bei end() - 5 enden (nachdem sichergestellt wurde, dass das Array vorhanden war)
mindestens 10 Elemente), und sorgen Sie sich nicht darum. In der Tat, wenn Sie
tu das:
Stellen Sie sicher, dass das Array zuerst groß genug ist.
Das obige würde tun, was Sie sagten, Sie wollen, die Sequenz genau zweimal durchlaufen (einmal für das Testen, zweimal für die Bereitstellung eines Iterators).
Wenn Sie wirklich einen Index anstelle eines Iterators wollen, bleibt das dem Leser als Übung überlassen.
Dies ist effizienter, wenn die Fenstergröße variieren kann (nicht nur ein fester +/- 5 Offset).
Für die feste kleine Fenstergröße in dieser Frage ist es wahrscheinlich viel weniger effizient als ein einfacher sequentieller Scan, wie zum Beispiel die Verwendung von count_if wie in James 'Antwort.
Hilfsfunktionen:
%Vor%Sie können den Segmentbaum für diese Art von Problem und die Komplexität viel weniger verwenden.
Tags und Links c++