Ich habe ein Eingabe-Array A
%Vor%Ich möchte die Funktion Max (T, A), die B zurückgibt und den Maximalwert auf A über dem vorherigen bewegten Fenster der Größe T mit
darstellt %Vor%Durch die Verwendung von max heap, um den maximalen Wert der aktuellen sich bewegenden Fenster A [i] bis A [i + T] zu verfolgen, ergibt dieser Algorithmus O (N log (T)) worst case.
Ich würde gerne wissen, gibt es einen besseren Algorithmus? Vielleicht ein O (N) -Algorithmus
es heißt RMQ (Range Minimum Query). Eigentlich habe ich einmal einen Artikel darüber geschrieben (mit C ++ Code). Siehe Ссылка
oder Sie bevorzugen die Wikipedia, Bereich Minimum Query
Nach der Vorbereitung können Sie die maximale Anzahl eines beliebigen Bereichs in O(1)
In der Bildverarbeitung gibt es ein Unterfeld namens Mathematische Morphologie. Die Operation, die Sie implementieren, ist ein Kernkonzept in diesem Feld, die Erweiterung genannt wird. Offensichtlich wurde diese Operation ausführlich untersucht und wir wissen, wie man sie sehr effizient implementiert.
Der effizienteste Algorithmus für dieses Problem wurde 1992 und 1993 unabhängig von van Herk und Gil und Werman vorgeschlagen. Dieser Algorithmus benötigt genau 3 Vergleiche pro Stichprobe, unabhängig von der Größe von T .
Einige Jahre später haben Gil und Kimmel den Algorithmus weiter verfeinert, um nur 2,5 Vergleiche pro Stichprobe zu benötigen. Obwohl die erhöhte Komplexität der Methode die weniger Vergleiche ausgleichen könnte (ich finde, dass komplexerer Code langsamer läuft). Ich habe diese Variante nie implementiert.
Der HGW-Algorithmus, wie er heißt, benötigt zwei Zwischenpuffer gleicher Größe wie die Eingabe. Für lächerlich große Eingaben (Milliarden von Samples) könnten Sie die Daten in Chunks aufteilen und sie chunkweise verarbeiten.
Sie gehen gewissermaßen durch die Daten vorwärts und berechnen das kumulative Maximum über Stücke der Größe T . Du machst das gleiche rückwärts gehen. Jeder von diesen erfordert einen Vergleich pro Probe. Letztendlich ist das Ergebnis das Maximum über einen Wert in jedem dieser zwei temporären Arrays. Für die Datenlokalisierung können Sie die zwei Durchläufe gleichzeitig über die Eingabe ausführen.
Ich schätze, Sie könnten sogar eine laufende Version erstellen, in der die temporären Arrays die Länge 2*T haben, aber das wäre komplizierter zu implementieren.
van Herk, "Ein schneller Algorithmus für lokale minimale und maximale Filter auf rechteckigen und achteckigen Kernen", Pattern Recognition Letters 13 (7): 517-521, 1992 ( doi )
Gil, Werman, "Berechnen von 2-D-Min-, Median- und Max-Filtern", IEEE-Transaktionen zu Musteranalyse und maschineller Intelligenz 15 (5): 504-507, 1993 (doi )
Gil, Kimmel, "Effiziente Dilatations-, Erosions-, Öffnungs- und Schließalgorithmen", IEEE Transactions on Pattern Analysis und Machine Intelligence 24 (12): 1606-1617, 2002 (doi )
(Hinweis: cross-gepostet von diese verwandte Frage zum Code Review .)