Eine Anleitung zum Sliding-Window-Algorithmus und wie man ihn in Go implementiert

Das Ausführen von Operationen an Zahlen- und Zeichenfolgen ist ein entscheidender Aspekt der Programmierung. Der Sliding-Window-Algorithmus ist einer der Standardalgorithmen hierfür.

Es handelt sich um eine elegante und vielseitige Lösung, die in vielen Bereichen Einzug gehalten hat. Von der String-Manipulation über Array-Durchquerungen bis hin zur Leistungsoptimierung kann dieser Algorithmus eine Rolle spielen.

Wie funktioniert also der Sliding-Window-Algorithmus und wie kann man ihn in Go implementieren?

Den Sliding-Window-Algorithmus verstehen

Es gibt viele Top-Algorithmen Das ist für einen Programmierer nützlich, und das Schiebefenster ist eines davon. Dieser Algorithmus basiert auf einem einfachen Konzept der Aufrechterhaltung eines dynamischen Fensters über eine Datensequenz, um Teilmengen dieser Daten effizient zu verarbeiten und zu analysieren.

Sie können den Algorithmus beim Lösen von Rechenproblemen anwenden, die Arrays, Zeichenfolgen oder Datensequenzen umfassen.

Die Kernidee des Sliding-Window-Algorithmus besteht darin, ein Fenster mit fester oder variabler Größe zu definieren und es durch die Eingabedaten zu verschieben. Auf diese Weise können Sie verschiedene Teilmengen der Eingabe untersuchen, ohne redundante Berechnungen durchzuführen, die die Leistung beeinträchtigen können.

Hier ist eine visuelle Darstellung, wie es funktioniert:

Die Grenzen des Fensters können je nach den Anforderungen des spezifischen Problems angepasst werden.

Implementierung des Sliding-Window-Algorithmus in Go

Sie können ein beliebtes Codierungsproblem verwenden, um zu lernen, wie der Schiebefensteralgorithmus funktioniert: Finden der größten Summe eines Unterarrays mit einer bestimmten Länge.

Das Ziel dieser Beispielaufgabe besteht darin, die Größe des Unterarrays zu ermitteln k deren Elemente in der Summe den größten Wert ergeben. Die Lösungsfunktion benötigt zwei Parameter: das Eingabearray und eine positive ganze Zahl, die es darstellt k.

Sei das Beispielarray Zahlen, wie der folgende Code zeigt:

nums := []int{1, 5, 4, 8, 7, 1, 9}

Und sei die Länge des Subarrays k, mit einem Wert von 3:

k := 3

Anschließend können Sie eine Funktion deklarieren, um die maximale Summe von Unterarrays mit der Länge k zu ermitteln:

funcmaximumSubarraySum(nums []int, k int)int {
// body
}

Sie denken vielleicht, dass das Fenster ein Array sein muss, das Kopien der Zielelemente speichert. Das ist zwar eine Option, aber die Leistung ist schlecht.

Stattdessen müssen Sie lediglich die Grenzen des Fensters definieren, um den Überblick zu behalten. In diesem Fall hat das erste Fenster beispielsweise den Startindex 0 und ein Endindex von k-1. Beim Verschieben des Fensters aktualisieren Sie diese Grenzen.

Der erste Schritt zur Lösung dieses Problems besteht darin, die Summe des ersten Unterarrays der Größe k zu ermitteln. Fügen Sie Ihrer Funktion den folgenden Code hinzu:

var windowStart, windowEnd, maxSum, windowSum int
windowStart = 0
for i := 0; i < k; i++ {
 windowSum += nums[i]
}
maxSum = windowSum

Der obige Code deklariert die notwendigen Variablen für den Algorithmus und ermittelt die Summe des ersten Fensters im Array. Anschließend wird es initialisiert maxSumme mit der Summe des ersten Fensters.

Der nächste Schritt besteht darin Schieben Sie das Fenster durch Iterieren durch die Zahlen Array aus Index k bis zum Ende. Bei jedem Schritt des Schiebens des Fensters:

1. Aktualisieren Fenstersumme durch Addieren des aktuellen Elements und Subtrahieren des Elements bei windowStart.
2. Aktualisieren maxSumme wenn der neue Wert von Fenstersumme ist größer als es.

Der folgende Code implementiert das Schiebefenster. Fügen Sie es hinzu MaximumSubarraySum Funktion.

for windowEnd = k; windowEnd < len(nums); windowEnd++ {
 windowSum = windowSum + nums[windowEnd] - nums[windowStart]
if windowSum > maxSum {
 maxSum = windowSum
 }
// slide window forward
 windowStart++
}

Wenn die Schleife abgeschlossen ist, haben Sie die größte Summe maxSumme, die Sie als Ergebnis der Funktion zurückgeben können:

return maxSum

Ihre komplette Funktion sollte so aussehen:

funcmaximumSubarraySum(nums []int, k int)int {
var windowStart, windowEnd, maxSum, windowSum int
 windowStart = 0
for i := 0; i < k; i++ {
 windowSum += nums[i]
 }
 maxSum = windowSum
for windowEnd = k; windowEnd < len(nums); windowEnd++ {
 windowSum = windowSum + nums[windowEnd] - nums[windowStart]
if windowSum > maxSum {
 maxSum = windowSum
 }
// slide window forward
 windowStart++ 
 }
return maxSum
}

Sie können eine Hauptfunktion zum Testen des Algorithmus definieren, indem Sie die Werte von verwenden Zahlen Und k von früher:

funcmain() {
 nums := []int{1, 5, 4, 8, 7, 1, 9}
 k := 3
 fmt.Println(maximumSubarraySum(nums, k))
}

Die Ausgabe wird in diesem Fall sein 19Dies ist die Summe des Unterarrays [4, 8, 7], das das größte ist.

Sie können dieselbe Technik jetzt auf ähnliche Probleme anwenden, sogar in anderen Sprachen, wie z. B. die Behandlung wiederholter Elemente innerhalb eines Fensters mithilfe von a Java-Hash-Map, Zum Beispiel.

Optimale Algorithmen führen zu effizienten Anwendungen

Dieser Algorithmus ist ein Beweis für die Leistungsfähigkeit effizienter Lösungen bei der Problemlösung. Das Schiebefenster maximiert die Leistung und eliminiert unnötige Berechnungen.

Ein solides Verständnis des Sliding-Window-Algorithmus und seiner Implementierung in Go versetzt Sie in die Lage, beim Erstellen von Anwendungen reale Szenarien in Angriff zu nehmen.